Given an array A of integers, there exists at least one positive integer p such that A[i] == A[j] for all i and j for which i % p == j % p == 0. Find the smallest p.

Examples:

  • Input array: [1, _, 1, _, 1, _, 1, _, 1]. Output: 2
  • Input array: [1, _, _, 1, _, _, 1, _, _]. Output: 3.
  • Input array: [1, _, _, _, 1, _, _, _, 1]. Output: 4

closed as unclear what you're asking by xnor, O.O.Balance, Peter Taylor, Ian Miller, Post Left Garf Hunter Nov 23 at 17:33

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 6
    Since the only problem is the lack of objective winning criterion, this seems like a good fit for the code-golf tag. – lirtosiast Nov 20 at 17:59
  • 3
    wha are the _? – Jonah Nov 20 at 19:14
  • 1
    I take it that _ stands for any entry that isn't 1? And that the array is zero-indexed? – xnor Nov 23 at 3:57
  • 1
    I was really hopeful that it would be i % p == j % p == N instead, which I think would have been a more interesting challenge – Sparr Nov 23 at 5:31
  • 1
    This could use more clarity on the quantifiers: I assume that "for all i and j for which" should be "for all i and j which are valid indexes into A and for which". The examples are missing some important corner cases: the empty array, a one-element array, an array of more than one element without repeats. But most importantly, and the reason that I'm voting to close as unclear, either the test suite or the spec is wrong for languages with 1-based indexing. – Peter Taylor Nov 23 at 13:40

Python 3, 47 bytes

f=lambda l,d=1:f(l,d+1)if~-len({*l[::d]})else d

Try It Online

Python 3, 43 bytes

f=lambda l,n=1:2>len({*l[::n]})or-~f(l,n+1)

Try it online!

Assumes the list is non-empy. Outputs True as 1, though for 1 byte this can be fixed by changing 2> to 1//.

44 bytes:

f=lambda l,n=1:{l[0]}=={*l[::n]}or-~f(l,n+1)

Try it online!

f=lambda l,n=1:l[:-n:n]==l[n::n]or-~f(l,n+1)

Try it online!

Jelly, 6 bytes

Assuming this is meant to be for now.

mJE€TḢ

Try it online!

  • Or mJE€i1. Does posting before the question is clarifed get you the win for tiebreaking purposes? I was hesitant to. – lirtosiast Nov 20 at 19:18
  • 4
    For me it just means I got to post from a computer rather than a mobile. Most wont upvote until the winning criteria is given anyway. – Jonathan Allan Nov 20 at 19:57

Pyth, 7 bytes

f!t{%TQ

Try it here. Pyth is at a disadvantage because it uses only printable ASCII; optimally encoded this would be \$7 * \log_{256} 95 = 5.749\$ bytes.

f             Find the first positive integer T such that
 !t           there is only one element in
   {          the list obtained by taking unique elements
    %TQ       of every Tth element of the input.

Java 8, 85 bytes

A lambda from a primitive array type to int.

l->{for(int d=0,i;;)for(i=++d;;i+=d){if(i>=l.length)return d;if(l[i]!=l[i-d])break;}}

Try It Online

Ungolfed

l -> {
    for (int d = 0, i; ;)
        for (i = ++d; ; i += d) {
            if (i >= l.length)
                return d;
            if (l[i] != l[i - d])
                break;
        }
}

Japt, 10 bytes

@ëX â ÊÉ}f

Try it online!

Explanation:

@       }f    :Get the first integer X which returns 0 from:
 ëX           : Get every Xth item in the input
    â         : Get the unique values of that list
      Ê       : Count how many there are
       É      : Subtract 1

Powershell, 82 bytes

(($a=$args)|%{($i++)}|?{"$a"-match"^(\d+)(( -?\d+){$_} \1)*( -?\d+){0,$_}$"})[0]+1

Test script:

$f = {

(($a=$args)|%{($i++)}|?{"$a"-match"^(\d+)(( -?\d+){$_} \1)*( -?\d+){0,$_}$"})[0]+1

}

@(
    ,(1 , 1,1,1,1,1)
    ,(2 , 1,-2,1,3,1,-4,1,5)
    ,(2 , 1,-2,1,3,1,-4,1,5,1)
    ,(3 , 1,-2,1,1,3, 4,1,5,1)  # 1 may be in place '_'
    ,(4 , 1,-2,3,4,1, 5,1,6,1)
    ,(5 , 1,2,3,4,5,1)
) | % {
    $expected, $a = $_
    $result = &$f @a
    "$($result-eq$expected): $result"

}

Explanation:

Regexp match on array.toString() which equivalent array.join(' ').

Python 3, 64 Bytes

A recursive approach.

f=lambda x,s=1:s if x[::s].count(x[0])==len(x[::s])else f(x,s+1)

Try it Online

Python 3, 82 81 Bytes

-1 byte thanks to Jakob!

lambda x:[x[::i].count(x[0])==len(x[::i])for i in range(1,len(x)+1)].index(1>0)+1

Try it Online!

  • How about 1>0 instead of True? – Jakob Nov 23 at 4:13
  • 1
    For the recursive approach, you need to initialize s=1 as an optional argument so that the function runs without taking an extra input. – xnor Nov 23 at 5:38

Japt, 6 bytes

I think this is right, the spec isn't all that clear. Assumes, as the spec would seem to suggest, that the number we're looking for will always appear first in the array and the _s must all be different from that number.

ð¶Ug)æ

Try it

           :Implicit input of array U
ð          :0-based indices of elements
 ¥         :  Equal to
  Ug       :  First element of U
    )      :End indexing
     æ     :First truthy (non-zero) element

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