37
\$\begingroup\$

Input a non-empty array with \$n\$ positive integers. Test if the input array contains every integer in \$1\cdots n\$.

In case you prefer 0-indexed numbers, you may choose to input an array of non-negative integers, and test if the input array contains every integer in \$0\cdots (n-1)\$ instead. All testcases and formula listed below use 1-index. You may need to adjust them if you choose this option.

Input / Output

Input is an array \$A\$ with \$n\$ positive integers:

$$ A = \left[A_1,\dots,A_n\right] $$ $$ \forall i \in \left[1,\dots,n\right]: A_i>0 $$

Output if input \$A\$ satisfies:

$$ \forall i \in \left[1,\dots,n\right]: i \in A $$

Output would be two distinct values, or truthy vs falsy values (swap meaning of truthy / falsy is allowed).

Rules

  • This is , shortest code wins. And since this is code-golf, don't worry about time / memory complexity of your code. You may even timeout on TIO as long as your program works when giving it more time to run.

Testcases

Truthy

1
1,2
2,1
1,3,2
3,1,2
1,2,3,4,5,6,7,8,9,10,11,12
12,11,10,9,8,7,6,5,4,3,2,1
6,3,8,12,1,10,4,2,7,9,5,11
16,37,14,15,23,8,29,35,21,6,5,34,38,9,36,26,24,32,28,7,20,33,39,12,30,27,40,22,11,41,42,1,10,19,2,25,17,13,3,18,31,4

Falsy

2
12
1,1
1,3
2,3
3,3
2,1,3,2
1,4,3,1
4,1,2,4
1,2,2,5,5
1,3,3,3,5
8,7,5,3,4,1,6
5,7,1,4,6,1,8,3
6,3,5,4,7,1,8,1,2
6,5,3,8,2,7,9,4
1,1,1,1,1,1,1,1
1,5,9,13,11,7,3
14,6,12,4,10,8,16,2
34,33,38,17,35,11,36,31,28,14,6,15,18,2,19,40,29,41,9,1,27,23,20,32,26,25,37,8,13,30,39,7,5,3,21,4,11,16,10,22,12,24
38,27,20,23,31,6,2,24,21,31,33,7,26,12,14,17,3,2,28,31,5,23,28,27,37,32,7,39,22,6,35,42,19,3,35,17,35,40,22,13,27,7
\$\endgroup\$
10
  • 1
    \$\begingroup\$ is empty list falsy? \$\endgroup\$
    – Razetime
    Jun 24, 2021 at 6:45
  • 8
    \$\begingroup\$ @Razetime IMO, empty list should be truthy. But anyway, empty list is excluded from testcases, and it is undefined behavior to your program. \$\endgroup\$
    – tsh
    Jun 24, 2021 at 6:48
  • \$\begingroup\$ How do you feel about restricting to n<10? It would make the elements to check finite and all single digit. And that would allow lots of wacky tarpits to solve it and not require as high a computational class! I think the spirit would still be preserved, and I can’t think of any way it could be used to hardcode or “cheat” that wouldn’t just be longer than doing it “right,” for the languages that can do it. \$\endgroup\$
    – AviFS
    Jun 24, 2021 at 8:20
  • 4
    \$\begingroup\$ @AviFS If your language doesn't support decimal number I/O, you can use character value I/O. If it doesn't support that either, you can take it in binary or unary. Computational class is not a problem; taking lots of time or memory is allowed by default (even if it can't be run to completion realistically on any machine). You're even allowed to handwave the inputs exceeding the limit of the built-in integer representation. So I don't see any extra benefit of restricting the input size to <10. \$\endgroup\$
    – Bubbler
    Jun 24, 2021 at 9:13
  • 1
    \$\begingroup\$ Would outputting 0 for one result or any other integer for the other be acceptable? \$\endgroup\$
    – Shaggy
    Jun 24, 2021 at 14:03

65 Answers 65

1 2
3
1
\$\begingroup\$

C (clang), 47 bytes

Input is a null-terminated array of positive integers

i;f(*a){return!a[i++]?i=0,1:!wcschr(a,i)<f(a);}

Try it online!


C (gcc) -m32, 35 bytes

Requires that you also pass the length

f(a,n){n=!n||wcschr(a,n)*f(a,n-1);}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Swift 5.9, 50 bytes

var p={(a:[Int])in a.sorted()==Array(1...a.count)}
\$\endgroup\$
0
\$\begingroup\$

RAD, 5 bytes

<≡⍳∘⍴

Try it online!

 ≡       - Check equality between ...
<        - ... the input vector ...
  ⍳∘     - ... and 1 through ...
   ⍴     - ... the length of the input vector.
   
\$\endgroup\$
0
\$\begingroup\$

Arturo, 22 bytes

$[a][=sort a 1..max a]

Try it

Checks whether the input sorted is equal to \$[1..\mathrm{max}(input)]\$.

\$\endgroup\$
0
\$\begingroup\$

Kamilalisp, 28 bytes

[≡ $(+ 1)∘⍳∘⍴ ⊼]

Determines whether the sorted vector is equal to the range [1, length(input)].

Attempt This Online!

Kamilalisp, 24 bytes

[≡ #0 ⍋@⍋]@$(^- 1)

A port of the APL answer.

Attempt This Online!

\$\endgroup\$
1 2
3

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.