# Question
Title: Calculate the longest series of 1's in an integer's binary value
## Goal

Given a non-negative integer, create a function that returns the starting position of number of largest consecutive 1's in that integer's binary value.

When given an input `0`, return `0`.

If the number has multiple streaks of equal length, you must return the position of the last streak.

## Input

An integer greater than **or equal to** 0.

## Output

An integer calculated as explained below.

## Rules

* This is code-golf, so the shortest code in bytes in each language wins.
* Standard loopholes are forbidden.

---

## Examples and Test Cases

### Example 1

* Your function is passed the integer 142
* 142 is equal to 10001110 in binary
* Longest streak is "111" (a streak of three ones)
* The streak starts at the 2^1 position
* **Your function returns 1 as the result**

### Example 2

* Your function is passed the integer 48
* 48 is equal to 110000 in binary
* Longest streak is "11" (a streak of two ones)
* The streak starts at the 2^4 position
* **Your function returns 4 as the result**

### Example 3

* Your function is passed the integer 750
* 750 is equal to 1011101110 in binary
* Longest streak is "111" (a streak of three ones)
* Since there are two streaks of equal length, we return the later streak.
* The later streak starts at the 2^5 position
* **Your function returns 5 as the result**

# Answer
> 22 votes
# Jelly, ~~10~~ 8 bytes

```
Ba\ÐƤṀċ¬

```

Try it online!

### How it works

```
Ba\ÐƤṀċ¬  Main link. Argument: n

B         Binary; convert n to base 2.

   ÐƤ     Apply the link to the left to all postfixes of the binary array.
 a\         Cumulatively reduce by logical AND.

          For example, the array

          [1, 0, 1, 1, 1, 0, 1, 1, 1, 0]

          becomes the following array of arrays.

          [1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
             [0, 0, 0, 0, 0, 0, 0, 0, 0]
                [1, 1, 1, 0, 0, 0, 0, 0]
                   [1, 1, 0, 0, 0, 0, 0]
                      [1, 0, 0, 0, 0, 0]
                         [0, 0, 0, 0, 0]
                            [1, 1, 1, 0]
                               [1, 1, 0]
                                  [1, 0]
                                     [0]

     Ṁ    Take the lexicographical maximum, i.e., the array with the most 1's at
          the beginning, breaking ties by length.

       ¬  Yield the logical NOT of n, i.e., 0 if n > 0 and 1 if n = 0.

      ċ   Count the occurrences of the result to the right in the one to the left.

```

# Answer
> 25 votes
# JavaScript (ES6),  ~~33~~  32 bytes

```
f=x=>x&(k=x>>1)?f(x&k):k&&1+f(k)

```

Try it online!

---

# JavaScript (ES6),  ~~41 40 36~~  34 bytes

*Saved 4 bytes thanks to @ThePirateBay*

```
f=x=>(k=x&x/2)?f(k):Math.log2(x)|0

```

Try it online!

### How?

**General case x \> 0**

We recursively AND the input ***x*** with ***x / 2*** which progressively reduces the patterns of consecutive set bits until only the rightmost bit of the sequence remains. We keep a copy of the last non-zero value and determine the position of its most significant bit by floor-rounding its base-2 logarithm.

Below are the steps we go through for ***x = 750*** (***1011101110*** in binary).

```
    1011101110 --.
,----------------'
'-> 1011101110
AND 0101110111
    ----------
=   0001100110 --.
,----------------'
'-> 0001100110
AND 0000110011
    ----------
=   0000100010 --.  --> output = position of MSB = 5  (0000100010)
,----------------'                                         ^
'-> 0000100010
AND 0000010001
    ----------
=   0000000000

```

**Edge case x = 0**

The special case `x = 0` immediately leads to `Math.log2(0) | 0`. The logarithm of `0` evaluates to `-Infinity` and the binary bitwise OR forces a coercion to a 32-bit integer. In compliance with the specification of the abstract operation **ToInt32**, this gives the expected `0`:

> If *number* is **NaN**, **+0**, **−0**, **+∞**, or **−∞**, return **+0**

# Answer
> 13 votes
# x86/x86-64 machine code, 14 bytes

(TODO: 13 bytes with input in EAX, return value in EDX).

Using @Arnauld's algorithm of `x &= x>>1` and taking the highest set bit position in the step before `x` becomes `0`.

Callable from C/C++ with signature `unsigned longest_set(unsigned edi);` in the x86-64 System V ABI. The same machine-code bytes will decode the same way in 32-bit mode, but the standard 32-bit calling conventions don't put the first arg in `edi`. (Changing the input register to `ecx` or `edx` for Windows `_fastcall` / `_vectorcall` or `gcc -mregparm` could be done without breaking anything.)

```
   address   machine-code
             bytes
                         global longest_set
 1                       longest_set:
 2 00000000 31C0             xor  eax, eax    ; 0 for input = 0
 3
 4                       .loop:               ; do{
 5 00000002 0FBDC7           bsr  eax, edi    ;  eax = position of highest set bit
 6                           ;; bsr leaves output unmodified when input = 0 (and sets ZF)
 7                           ;; AMD documents this; Intel manuals say unspecified but Intel CPUs implement it
 8 00000005 89F9             mov  ecx, edi
 9 00000007 D1E9             shr  ecx, 1
10 00000009 21CF             and  edi, ecx
11 0000000B 75F5             jnz .loop        ; } while (x &= x>>1);
12
13 0000000D C3               ret

```

x86's `BSR` instruction (Bit Scan Reverse) is perfect for this, giving us the bit-index directly, rather than counting leading zeros. (`bsr` doesn't directly produce 0 for input=0 like `32-lzcnt(x)` would, but we need bsr=31-lzcnt for non-zero inputs, so `lzcnt` wouldn't even save instructions, let alone byte count. Zeroing eax before the loop works because of `bsr`'s semi-official behaviour of leaving the destination unmodified when the input is zero.)

This would be even shorter if we could return the MSB position of the longest run. In that case, `lea ecx, [rdi+rdi]` (3 bytes) would copy + *left*-shift instead of `mov` \+ `shr` (4 bytes).

See this TIO link for an asm caller that does `exit(longest_set(argc-1));`

Testing with a shell loop:

```
l=(); for ((i=0;i<1025;i++));do
    ./longest-set-bitrun "${l[@]}";   # number of args = $i
    printf "$i %#x: $?\n" $i;
    l+=($i);
done | m

0 0: 0
1 0x1: 0
2 0x2: 1
3 0x3: 0
4 0x4: 2
5 0x5: 2
6 0x6: 1
7 0x7: 0
8 0x8: 3
9 0x9: 3
10 0xa: 3
11 0xb: 0
12 0xc: 2
13 0xd: 2
14 0xe: 1
15 0xf: 0
16 0x10: 4
17 0x11: 4
18 0x12: 4
19 0x13: 0
20 0x14: 4
21 0x15: 4

...

747 0x2eb: 5
748 0x2ec: 5
749 0x2ed: 5
750 0x2ee: 5
751 0x2ef: 0
752 0x2f0: 4
753 0x2f1: 4
754 0x2f2: 4

```

---

## 13 bytes with a custom calling convention

We could save a byte by taking the arg in EAX and returning in EDX: then we could use `cdq` (1 byte) to zero the return value in the case where input = 0 (so `bsr` leaves it unmodified). The value in other cases doesn't matter, overwritten by `bsr`.

So `cdq` replaces `xor eax, eax`, saving a byte.

We do need a `0` in a different register to (not) overwrite; in the non-zero case we can't let `bsr` replace the input value with its log2. So we can't avoid the instruction entirely, and taking input + returning in EAX (like GCC regparm) would mean we'd need to start with `mov edx, eax` or something to copy it somewhere else, while leaving the return value 0 for the input=0 case.

# Answer
> 6 votes
# Python 2, 45 bytes

```
f=lambda x:f(x&x/2)if x&x/2else len(bin(x))-3

```

Try it online!

*Saved plenty of bytes thanks to Dennis! (The heads up for `len(bin(...))-3` instead of `math.frexp`)*

*Thanks to @xnor for finding a bug, which fortunately was easily fixable!*

# Answer
> 5 votes
# Jelly, ~~19~~  ~~17~~ 11 bytes

```
HÐĿ&\ḟ0ṪBL’

```

Try it online!

*-6 (!) bytes thanks to @Dennis's keen observations*

**How it Works**

```
HÐĿ&\ḟ0ṪBL’
HÐĿ         - halve repeatedly until reaching 0 due to rounding
   &\       - cumulative AND
     ḟ0Ṫ    - final non-zero, or 0 if all elements are 0
        BL  - length of binary representation (log base 2). 0->[0]->1
          ’ - decrement

```

# Answer
> 4 votes
# Perl 6, ~~45~~ 35 bytes

*This highly improved version is courtesy of @nwellnhof.*

```
{.msb+1-(.base(2)~~m:g/1+/).max.to}

```

Try it online!

# Answer
> 4 votes
# 05AB1E, ~~14~~ ~~12~~ 11 bytes

```
bDγàŠrkrJgα

```

Try it online! or run test cases.

## Explanation

```
bDγàŠrkrJgα  Implicit input (ex: 750)
bD           Convert input to binary string and duplicate
                 '1011101110', '1011101110'
  γ          Split into groups of 1s or 0s
                 '1011101110', ['1', '0', '111', '0', '111', '0']
   à         Pull out max, parsing each as an integer
                 '1011101110', ['1', '0', '0', '111', '0'], '111'
    Šrk      Rearrange stack and get first index of max run of ones
                 ['1', '0', '0', '111', '0'], 2
       rJg   Reverse stack, join the array to a string, and get its length
                 2, 7
          α  Get absolute difference
                 5

```

# Answer
> 3 votes
# Python 2, ~~89~~ 78 bytes

```
m=t=i=j=0
for c in bin(input()):
 t=-~t*(c>'0');i+=1
 if t>m:j=i;m=t
print i-j

```

Try it online!

EDIT: Saved 11 bytes thanks to Mr. Xcoder.

# Answer
> 3 votes
# , ~~18~~ 17 bytes

```
(#-0{#\\:#.~\)@#:

```

Try it online!

## Explanation

```
(#-0{#\\:#.~\)@#:  Input: integer n
               #:  Binary
     #\            Length of each prefix
       \:          Sorted down using
         #.~\      Mixed base conversion on each prefix
   0{              Get the value at index 0
  -                Subtract from
 #                 Length

```

# Answer
> 3 votes
# C# (.NET Core), 64 60 bytes

```
T=a=>(a&a/2)>0?T(a&a/2):Math.Log(a,2)<0?0:(int)Math.Log(a,2)

```

Try it online!

A C# version of @Arnauld's answer

### Acknowledgements

4 bytes saved thanks to Kevin Cruijssen.

# C# (.NET Core), 131 123+18=141 bytes

```
a=>{string s=Convert.ToString(a,2),t=s.Split('0').OrderBy(x=>x.Length).Last();return a<1?0:s.Length-s.IndexOf(t)-t.Length;}

```

Try it online!

+18 bytes for `using System.Linq;`

### Acknowledgements

8 bytes saved thanks to Grzegorz Puławski.

### Degolfed

```
a=>{
    string s=Convert.ToString(a,2),      // Convert to binary
    t=s.Split('0')                       // get largest group of 1's
       .OrderBy(x=>x.Length)
       .Last();
    return
        a<1?0:                          // handle 0 case
        s.Length-s.IndexOf(t)-t.Length; // get position in reversed string
}

```

# C# (.NET Core), 164 161 bytes

```
a=>{var s=Convert.ToString(a,2);int c=0,l=0,p=0,k=0,j=s.Length-1,i=j;for(;i>=0;i--){if(s[i]>'0'){if(i==j||s[i+1]<'1'){p=i;c=0;}if(++c>=l){l=c;k=p;}}}return j-k;}

```

Try it online!

A non-`Linq` solution, which I'm sure could be improved, though nothing is immediately apparent.

### Degolfed

```
a=>{
    var s=Convert.ToString(a,2); // Convert to binary
    int c=0,l=0,p=0,k=0,j=s.Length-1,i=j;
    for(;i>=0;i--)               // Loop from end of string
    {
        if(s[i]>'0')             // if '1'
        {
            if(i==j||s[i+1]<'1') // if first digit or previous digit was '0'
            {
                p=i;             // set the position of the current group
                c=0;             // reset the count
            }
            if(++c>=l)           // if count is equal or greater than current largest count
            {
                l=c;             // update largest count
                k=p;             // store position for this group
            }
        }
    }
    return j-k;                  // as the string is reversed, return string length minus position of largest group
}

```

# Answer
> 3 votes
# Python 3, 46 bytes

```
f=lambda x:x&x>>1and f(x&x>>1)or len(bin(x))-3

```

Try it online!

# Answer
> 2 votes
# Jelly, 19 bytes

```
BŒgḄṀB
BwÇɓÇL+ɓBL_‘

```

Try it online!

Thanks to Jonathan Allan for saving  ~~4~~  6 bytes!

I've worked too much to just abandon this, although it is kind of long. I really wanted to add a solution that literally searches for the longest substring of `1`s in the binary representation...

# Explanation

```
BŒgḄṀB  - Monadic helper link. Will be used with Ç in the next link.

B       - Binary representation.
 Œg     - Group runs of consecutive equal elements.
   Ḅ    - Convert from binary to integer.
    Ṁ   - Maximum value.
     B  - Convert from integer to binary.

BwÇɓÇL+ɓBL_‘  - Main link.

B             - Binary representation (of the input).
  Ç           - Last link as a monad. Takes the input integer.
 w            - First sublist index.
   ɓ          - Start a separate dyadic chain. Reverses the arguments.
    Ç         - Last link as a monad.
     L        - Length.
      +       - Addition
       ɓ      - Start a separate dyadic chain. Reverses the arguments.
        B     - Binary.
         L    - Length.
          _‘  - Subtract and increment the result (because Jelly uses 1-indexing).
              - Implicitly output.

```

# Answer
> 2 votes
# Haskell, ~~101~~ ~~98~~ ~~96~~ 75 bytes

```
snd.maximum.(`zip`[0..]).c
c 0=[0]
c n|r<-c$div n 2=sum[r!!0+1|mod n 2>0]:r

```

Try it online! Usage: `snd.maximum.(`zip`[0..]).c $ 142` yields `1`.

### Explanation:

* `c` converts the input into binary while at the same time counting the length of streaks of one, collecting the results in a list. `r<-c$div n 2` recursively computes the rest `r` of this list, while `sum[r!!0+1|mod n 2>0]:r` adds the current length of the streak to `r`. The list comprehension checks if `mod n 2>0`, that is whether the current binary digit is a one, and if so, takes the length of the previous streak (the first element of `r`) and adds one. Otherwise the list comprehension is empty, and `sum[]` yields `0`. For the example input, `c 142` yields the list `[0,3,2,1,0,0,0,1,0]`.
* `(`zip`[0..])` adds the position to each element of the previous list as the second component of a tuple. For the example this gives `[(0,0),(3,1),(2,2),(1,3),(0,4),(0,5),(0,6),(1,7),(0,8)]`.
* `maximum` finds the lexicographically maximal tuple in this list, that is the streak lengths are considered first as they are the first component, and in the event of a tie the second component, namely the larger index, decides. This yields `(3,1)` in the example, and `snd` returns the second component of the tuple.

# Answer
> 2 votes
# Jelly,  ~~14 13 12~~  11 bytes

```
Bµṣ0Ṫ$ƤMḢạL

```

A monadic link taking and returning non-negative integers.

**Try it online!** or see the test-suite.

### How?

```
Bµṣ0Ṫ$ƤMḢạL - Main link: number, n                   e.g. 750
B           - convert to a binary list                    [1,0,1,1,1,0,1,1,1,0]
 µ          - monadic chain separation, call that b
      Ƥ     - map over prefixes:  (i.e. for [1], [1,0], [1,0,1], [1,0,1,1],...)
     $      -   last two links as a monad:                e.g.: [1,0,1,1,1,0,1,1]
   0        -     literal zero                                   0
  ṣ         -     split (prefix) at occurrences of (0)           [[1],[1,1,1],[1,1]]
    Ṫ       -     tail                                                        [1,1]
       M    - maximal indices                             [5,9]
        Ḣ   - head                                        5
          L - length (of b)                               10
         ạ  - absolute difference                         5

```

# Answer
> 2 votes
# Husk, 12 bytes

```
→S§-€¤≠Lo▲gḋ

```

Try it online!

### Explanation

```
                 Implicit input, e.g                           750
           ḋ     Convert to binary                             [1,0,1,1,1,0,1,1,1,0]
          g      Group equal elements                          [[1],[0],[1,1,1],[0],[1,1,1],[0]]
        o▲       Maximum                                       [1,1,1]
    €            Index of that substring in the binary number  3
     ¤≠L         Absolute difference of lengths                abs (3 - 10) = 7
 S§-             Subtract the two                              7 - 3 = 4
→                Increment                                     5

```

# Answer
> 2 votes
# Kotlin, 77 bytes

```
{val b=it.toString(2)
b.reversed().lastIndexOf(b.split(Regex("0+")).max()!!)}

```

## Beautified

```
{
    val b = it.toString(2)
    // Find the left position of the first instance of
    b.reversed().lastIndexOf(
            // The largest group of 1s
            b.split(Regex("0+")).max()!!)
}

```

## Test

```
var s:(Int)->Int =
{val b=it.toString(2)
b.reversed().lastIndexOf(b.split(Regex("0+")).max()!!)}
fun main(args: Array<String>) {
    r(0, 0)
    r(142, 1)
    r(48, 4)
    r(750, 5)
}

fun r(i: Int, i1: Int) {
    var v = s(i)
    println("$i -> $v [$i1] ${i1 == v}")
}

```

# Answer
> 2 votes
# C (gcc), ~~81~~ 80 bytes

```
i,l,c,r;f(n){for(i=l=c=r=0;n;n/=2,i++)c=n&1?c+1:c>=l?r=i-(l=c),0:0;n=c<l?r:i-c;}

```

Try it online!

# C (gcc), 43 bytes

A C version of @Arnauld's answer

```
k;f(n){n=(k=n&n/2)?f(k):(k=log2(n))<0?0:k;}

```

Try it online!

# Answer
> 2 votes
# Google Sheets, 94 bytes

```
=Len(Dec2Bin(A1))-Find(MAX(Split(Dec2Bin(A1),0)),Dec2Bin(A1))-Len(MAX(Split(Dec2Bin(A1),0)))+1

```

No, it's not very pretty. It'd be real nice to be able to store `Dec2Bin(A1)` as a variable for reference.

Key point: Like Excel, the `Dec2Bin` function has a max input value of `511`. Anything larger than that returns an error, as seen below.

# Answer
> 2 votes
# APL (Dyalog Unicode), 21 bytes (SBCS)

−1 thanks to rabbitgrowth.

Requires `⎕IO←0` which is default on many systems.

```
⊃⌽⍸b⍷⍨∨⌿↑⊆⍨b←⌽2⊥⍣¯1⊢⎕

```

Try it online!

prompt for input

yield that (separates `¯1` from )

`2⊥⍣¯1` convert to base-2, using as many positions as needed

reverse

`b←` store as `b` (for **b**inary)

`⊆⍨b` self-partition `b` (i.e. the 1-streaks of `b`)

mix (make list of lists into matrix, padding with zeros)

`∨⌿` vertical OR reduction (yields longest streak)

`b⍷⍨` mark the start positions of that in `b`

**ɩ**ndices of those starting positions

reverse

pick the first one (yields zero if none available)

# Answer
> 2 votes
# MS SQL Server, 437 426 407 398 bytes

SQL Fiddle

I'm sure that I could remove line breaks, etc, but this is as compact as I was willing to make it:

```
create function j(@ int)
returns int
as BEGIN
declare @a varchar(max)='',@b int,@c int=0,@d int=0,@e int=0,@f int=0,@g int=0,@h int=0
while @>0 BEGIN SELECT @a=cast(@%2 as char(1))+@a,@=@/2
END
SET @b=len(@a)
while @<@b
BEGIN
select @c=@d,@d=cast(substring(@a,@b-@,1)as int)
IF @d=1
BEGIN IF @c=0
SELECT @e=@,@g=1
else SET @g+=1 END
IF @g>=@h BEGIN select @h=@g,@f=@e END
SET @+=1
END
return @f
END

```

Here's a more readable version:

```
create function BinaryString(@id int)
returns int
as BEGIN
  declare @bin varchar(max)
  declare @binLen int
  declare @pVal int = 0
  declare @Val int = 0
  declare @stC int = 0 --start of current string of 1s
  declare @stB int = 0 --start of biggest string of 1s
  declare @lenC int = 0 --length of current string of 1s
  declare @lenB int = 0 --length of biggest string of 1s

  set @bin = ''

    while @id>0
      BEGIN
        SET @bin = cast(@id%2 as varchar(1)) + @bin
        SET @id = @id/2
      END

    SET @binLen = len(@bin)

    while @id<@binLen
      BEGIN
        set @pVal = @Val
        set @Val = cast(substring(@bin,@binLen-@id,1) as int)
        IF @Val = 1 and @pVal = 0
          BEGIN
            SET @stC = @id
            SET @lenC = 1
          END
        IF @Val = 1 and @pVal = 1
          BEGIN
            SET @lenC = @lenC + 1
          END
        IF @lenC >= @lenB
          BEGIN
            set @lenB = @lenC
            set @StB = @StC
          END

        SET @id = @id + 1
      END

  return @StB
END

```

The real trick is that as far as I could find, there is no native SQL functionality to convert a number from decimal to binary. As a result, I had to code the conversion to binary manually, then I could compare that as a string, one character at a time until I found the right number.

I'm sure there's a better way to do this, but I didn't see a(n) SQL answer, so I figured I'd throw it out there.

# Answer
> 1 votes
# MATL, 15 bytes

```
`tt2/kZ&t]xBnq&

```

Try it online!

Uses the half and AND idea. The `k` is necessary only to make it terminate for `1` \- for some reason, 1 AND 0.5 returns 1, causing an infinite loop.

(alternate solution: `BtnwY'tYswb*&X>)-` by converting to binary and run-length encoding)

# Answer
> 1 votes
# APL (Dyalog Classic), ~~24~~ 21 bytes

```
63|-⊃⍒+/×\↑,⍨\⎕⊤⍨64⍴2

```

Try it online!

# Answer
> 1 votes
# Excel VBA, <sub>~~54~~</sub> 44 Bytes

-10 Bytes thanks to @EngineerToast

Anonymous VBE immediate window function that takes input from range `[A1]` and outputs to the VBE immediate window

```
?Instr(1,StrReverse([Dec2Bin(A1)]),1)+[A1>0]

```

# Answer
> 1 votes
# R, 117 Bytes

```
z=rev(Reduce(function(x,y)ifelse(y==1,x+y,y),strtoi(intToBits(scan())),,,T));ifelse(!sum(z),0,33-which.max(z)-max(z))

```

# Answer
> 0 votes
# Retina, ~~52~~ 43 bytes

Convert to binary, then replace with the length of what follows the largest string of ones.

```
.*
$*
+`(1+)\1
$+0
01
1

$'¶
O`
A-3`
^1+

.

```

**Try it online** \- all test cases

*Saved 9 bytes thanks to Martin.*

# Answer
> 0 votes
# Pyth, 17 bytes

This is a recursive function. The link includes `y` in order to call the function on the given input.

```
L|&K.&b/b2yKsl|b1

```

**Verify all test cases.**

# Pyth, 20 bytes

```
-lK.B|Q1+xKJeScK\0lJ

```

**Verify all test cases.**

# Answer
> 0 votes
# R, 66 Bytes

```
function(i){a=rle(intToBits(i));max(0,a[[1]][which(a[[2]]==1)])}

```

Explanation:

```
function(i){
  a = rle(                  # Run-length encode
    intToBits(i)            # The bits in i
  );                        # And assign it to a.
  max(0,                    # Return the maximum of zero and
      a[[1]][               # The lengths of a,
        which(a[[2]]==1)    # But only those where the repeated bit is 1
        ])
}

```

# Answer
> 0 votes
# Javascript, 54 chars

```
f=i=>i.toString(2).split(0).sort().reverse()[0].length

```
* `i.toString(2)` gets the binary string for the integer.
* The `.split(0)` gets each sequential ones part in an array element.
* `.sort().reverse()` gets us the highest value as first.
* The `[0].length` gives us the length of that first value.

# Answer
> 0 votes
# Python 2, 41 bytes

```
f=lambda n:n/2and(n&n/2<1)+f(n&n/2or n/2)

```

Try it online!

Based on this solution by Mr. Xcoder.

# Answer
> 0 votes
# Objective-C, 96 chars

```
for(int h=0,c=0,l=0,p=0;;x/=2,p++){if(x%2==0){if(c<=h){h=c;l=p;}c=0;if(x==0){return p;}}else{c++;}}

```
* If `x` is even the highest count is checked and count resets
* If `x` is also 0 then return the highest count
* If `x` isn't even, then the last digit is 1 and count increments
* `x` is divided by two

# Answer
> 0 votes
# Perl 5, 45 + 1 (-p)

```
(sprintf"%b",$_)=~/(1+)(?!.*1\1)/;$_=length$'

```

If you write this out on the command line of most shells, you may have to type this as:

```
perl -pE'(sprintf"%b",$_)=~/(1+)(?!.*1\1)/;$_=length$'"'"

```

The dance of the quotes at the end is just to get perl see a `'`, which would otherwise be consumed by the shell.

# Answer
> 0 votes
# Java 8, 81 bytes

```
int c(int n){int x=(int)(Math.log(n)/Math.log(2));return(n&=n/2)>0?c(n):x<0?0:x;}

```

Port of *@Arnauld*'s JavaScript answer.

Try it here.

# Answer
> 0 votes
# Javascript, 71 bytes

I was thinking about regular expressions and...

```
x=>+x.toString(2).replace(/.*?0?(1*)(?!.*\1[1])(.*)/,(x,m,a)=>a.length)

```

<sup>Regex101 link</sup>

# Answer
> 0 votes
# Python 3, 83 bytes

```
len(bin(num)[2:].split('1'*(max(list(map(len,bin(num)[2:].split('0'))))))[1])

```

Try it online!

It does not support the condition that two or more arrays of `1`s are longest.

# Answer
> 0 votes
# Mathematica, 44 bytes

I feel like I can trim off a few more bytes, though I'm not sure how yet.

We save space by using an assignment within `If`, using `#0` for pure function recursion, and using infix notation when possible.

```
If[(k=BitAnd[#,#/2])>0,#0@k,Log2@#~BitOr~0]&

```

Try it online!

# Answer
> 0 votes
# Zsh, 53 bytes

```
b=$[[##2]$1];set ${(Ons:0:)b};<<<$[$#b-${(SE)b#$1}+1]

```

Try it online! ~~<sub>58b</sub>~~ ~~<sub>60b</sub>~~

`b` is argument `$1` in binary. Then we `set` `$1` again, to the longest sequence of `1`s in `b`.
`${(SE)b#$1` finds the first occurrence (from the left) of `$1` in `b`, and returns the index+1 of the last matching char. However since the question is counting by powers of 2 we do a subtraction from the length of `b`.

Other approaches reverse `b`, but that took more bytes.

---
Tags: code-golf, binary, bitwise
---


title: Find the first duplicated element

text:
# Question
Title: Find the first duplicated element
Given an array a that contains only numbers in the range from 1 to a.length, find the first duplicate number for which the second occurrence has the minimal index. In other words, if there are more than 1 duplicated numbers, return the number for which the second occurrence has a smaller index than the second occurrence of the other number does. If there are no such elements, your program / function may result in undefined behaviour.

Example:

For `a = [2, 3, 3, 1, 5, 2]`, the output should be `firstDuplicate(a) = 3`.

There are 2 duplicates: numbers 2 and 3. The second occurrence of 3 has a smaller index than the second occurrence of 2 does, so the answer is 3.

For `a = [2, 4, 3, 5, 1]`, the output should be `firstDuplicate(a) = -1`.

This is , so shortest answer in bytes wins.

BONUS: Can you solve it in O(n) time complexity and O(1) additional space complexity?

# Answer
# Python 2, 34 bytes

*O(n2) time, O(n) space*

Saved 3 bytes thanks to @vaultah, and 3 more from @xnor!

```
lambda l:l[map(l.remove,set(l))<0]

```

Try it online!
> 17 votes

# Answer
## JavaScript (ES6), ~~47~~ ~~36~~ ~~31~~ 25 bytes

*Saved 6 bytes thanks to ThePirateBay*

Returns `undefined` if no solution exists.

Time complexity: *O*(n) :-)
Space complexity: *O*(n) :-(

```
a=>a.find(c=>!(a[-c]^=1))

```

### How?

We keep track of already encountered values by saving them as new *properties* of the original array ***a*** by using negative numbers. This way, they can't possibly interfere with the original entries.

### Demo

```
let f =

a=>a.find(c=>!(a[-c]^=1))

console.log(f([2, 3, 3, 1, 5, 2]))
console.log(f([2, 4, 3, 5, 1]))
console.log(f([1, 2, 3, 4, 1]))
```
> 15 votes

# Answer
# Mathematica, 24 bytes

```
#/.{h=___,a_,h,a_,h}:>a&

```

Mathematica's pattern matching capability is so cool!

Returns the original `List` for invalid input.

### Explanation

```
#/.

```

In the input, replace...

```
{h=___,a_,h,a_,h}

```

A `List` with a duplicate element, with 0 or more elements before, between, and after the duplicates...

```
... :>a

```

With the duplicate element.
> 6 votes

# Answer
# Jelly, 5 bytes

```
Ṛœ-QṪ

```

Try it online!

### How it works

```
Ṛœ-QṪ  Main link. Argument: A (array)

Ṛ      Yield A, reversed.
   Q   Unique; yield A, deduplicated.
 œ-    Perform multiset subtraction.
       This removes the rightmost occurrence of each unique element from reversed
       A, which corresponds to the leftmost occurrence in A.
    Ṫ  Take; take the rightmost remaining element, i.e., the first duplicate of A.

```
> 6 votes

# Answer
# Pyth, 5 bytes

```
h.-Q{

```

Test suite

Remove from Q the first appearance of every element in Q, then return the first element.
> 5 votes

# Answer
# Haskell, 35 bytes

```
f s(h:t)|h`elem`s=h|1<2=f(h:s)t
f[]

```

Try it online! Crashes if no duplicate is found.
> 5 votes

# Answer
# Vyxal, 4 bytes

```
UÞ⊍h

```

Try it Online!

Takes the multi-set symmetric difference, which outputs the duplicate values in order that they occur. Outputs `0` if nothing is found.
> 5 votes

# Answer
# Dyalog APL, ~~27~~ ~~24~~ ~~20~~ ~~19~~ ~~13~~ ~~12~~ 11 bytes

```
⊢⊃⍨0⍳⍨⊢=⍴↑∪

```

Now modified to not depend on v16! Try it online!

# How? (With input **N**)

* `⊢⊃⍨...` \- **N** at this index:
    + `⍴↑∪` \- **N** with duplicates removed, right-padded with `0` to fit **N**
    + `⊢=` \- Element-wise equality with **N**
    + `0⍳⍨` \- Index of the first `0`. \`
> 4 votes

# Answer
# Jelly, 6 bytes

```
xŒQ¬$Ḣ

```

Try it online!

Returns the first duplicate, or 0 if there is no duplicate.

## Explanation

```
xŒQ¬$Ḣ  Input: array M
    $   Operate on M
 ŒQ       Distinct sieve - Returns a boolean mask where an index is truthy
          for the first occurrence of an element
   ¬      Logical NOT
x       Copy each value in M that many times
     Ḣ  Head

```
> 4 votes

# Answer
# Japt, 7 bytes

```
æ@bX ¦Y

```

Test it online!

### Explanation

```
 æ@   bX ¦ Y
UæXY{UbX !=Y}  Ungolfed
               Implicit: U = input array
UæXY{       }  Return the first item X (at index Y) in U where
     UbX         the first index of X in U
         !=Y     is not equal to Y.
               In other words, find the first item which has already occured.
               Implicit: output result of last expression

```

---

Alternatively:

```
æ@¯Y øX

```

Test it online!

### Explanation

```
 æ@   ¯ Y øX
UæXY{Us0Y øX}  Ungolfed
               Implicit: U = input array
UæXY{       }  Return the first item X (at index Y) in U where
     Us0Y        the first Y items of U (literally U.slice(0, Y))
          øX     contains X.
               In other words, find the first item which has already occured.
               Implicit: output result of last expression

```
> 4 votes

# Answer
# Brachylog, 5 bytes

```
a⊇=bh

```

Try it online!

## Explanation

```
a⊇=bh  Input is a list.
a      There is an adfix (prefix or suffix) of the input
 ⊇     and a subsequence of that adfix
  =    whose elements are all equal.
   b   Drop its first element
    h  and output the first element of the rest.

```

The adfix built-in `a` lists first all prefixes in increasing order of length, then suffixes in decreasing order of length. Thus the output is produced by the shortest prefix that allows it, if any. If a prefix has no duplicates, the rest of the program fails for it, since every subsequence of equal elements has length 1, and the first element of its tail doesn't exist. If a prefix has a repeated element, we can choose the length-2 subsequence containing both, and the program returns the latter.
> 4 votes

# Answer
# Retina, ~~26~~ 24 bytes

```
1!`\b(\d+)\b(?<=\b\1 .*)

```

Try it online! Explanation: `\b(\d+)\b` matches each number in turn, and then the lookbehind looks to see whether the number is a duplicate; if it is the `1`st match is `!` output, rather than the count of matches. Unfortunately putting the lookbehind first doesn't seem to work, otherwise it would save several bytes. Edit: ~~Added 7 bytes to comply with the `-1` return value on no match.~~ Saved 2 bytes thanks to @MartinEnder.
> 3 votes

# Answer
# Python 3, ~~94~~ 92 bytes

O(n) time and O(1) extra memory.

```
def f(a):
 r=-1
 for i in range(len(a)):t=abs(a[i])-1;r=[r,i+1][a[t]<0>r];a[t]*=-1
 return r

```

Try it online!

Source of the algorithm.

### Explanation

The basic idea of the algorithm is to run through each element from left to right, keep track of the numbers that have appeared, and returning the number upon reaching a number that has already appeared, and return -1 after traversing each element.

However, it uses a clever way to store the numbers that have appeared without using extra memory: to store them as the sign of the element indexed by the number. For example, I can represent the fact that `2` and `3` has already appeared by having `a[2]` and `a[3]` negative, if the array is 1-indexed.
> 3 votes

# Answer
# APL (Dyalog), 20 bytes

```
⊃n/⍨(,≢∪)¨,\n←⎕,2⍴¯1

```

Try it online!

`2⍴¯1` negative one **r**eshaped into a length-two list

`⎕,` get input (mnemonic: console box) and prepend to that

`n←` store that in *n*

`,\` prefixes of *n* (lit. cumulative concatenation)

`(` apply the following tacit function to each prefix

`,` \[is\] the ravel (just ensures that the prefix is a list)

different from

the unique elements\[?\] (i.e. is does the prefix have duplicates?)

`n/⍨` use that to filter *n* (removes all elements until the first for which a duplicate was found)

pick the first element from that
> 3 votes

# Answer
# Perl 6, 13 bytes

```
*.repeated[0]

```

Try it

---

## Explanation

* The `*` is in a Term position so the whole statement is a WhateverCode lambda.
* The `.repeated` is a method that results in every value except for the first time each value was seen.

```
say [2, 3, 3, 3, 1, 5, 2, 3].repeated.perl; # (3, 3, 2, 3).Seq
#   (      3, 3,       2, 3).Seq

```
* `[0]` just returns the first value in the Seq.
If there is no value Nil is returned.
(Nil is the base of the Failure types, and all types are their own undefined value, so Nil different than an undefined value in most other languages)

---

Note that since the implementation of `.repeated` generates a Seq that means it doesn't start doing any work until you ask for a value, and it only does enough work to generate what you ask for.
So it would be easy to argue this has at worst *O(n)* time complexity, and at best *O(2)* time complexity if the second value is a repeat of the first.
Similar can probably be said of memory complexity.
> 3 votes

# Answer
# , 12 bytes

```
,&_1{~~:i.0:

```

Try it online!

## Explanation

```
,&_1{~~:i.0:  Input: array M
      ~:      Nub-sieve
          0:  The constant 0
        i.    Find the index of the first occurrence of 0 (the first duplicate)
,&_1          Append -1 to M
    {~        Select the value from the previous at the index of the first duplicate

```
> 3 votes

# Answer
## APL, 15

```
{⊃⍵[(⍳⍴⍵)~⍵⍳⍵]}

```

Seems like we can return 0 instead of -1 when there are no duplicates, (thanks Adám for the comment). So 3 bytes less.

A bit of description:

```
⍵⍳⍵         search the argument in itself: returns for  each element the index of it's first occurrence
(⍳⍴⍵)~⍵⍳⍵   create a list of all indexes, remove those found in ⍵⍳⍵; i.e. remove all first elements
⊃⍵[...]     of all remaining elements, take the first. If the array is empty, APL returns zero

```

For reference, old solution added -1 to the list at the end, so if the list ended up empty, it would contain -1 instead and the first element would be -1.

```
{⊃⍵[(⍳⍴⍵)~⍵⍳⍵],¯1}

```

Try it on tryapl.org
> 3 votes

# Answer
# PHP, ~~56 44 38~~ 32 bytes

```
for(;!${$argv[++$x]}++;);echo$x;

```

Run like this:

```
php -nr 'for(;!${$argv[++$x]}++;);echo$x;' -- 2 3 3 1 5 2;echo
> 3

```

# Explanation

```
for(
  ;
  !${                 // Loop until current value as a variable is truthy
    $argv[++$x]       // The item to check for is the next item from input
  }++;                // Post increment, the var is now truthy
);
echo $x;              // Echo the index of the duplicate.

```

# Tweaks

* Saved 12 bytes by using variables instead of an array
* Saved 6 bytes by making use of the "undefined behavior" rule for when there is no match.
* Saved 6 bytes by using post-increment instead of setting to 1 after each loop

# Complexity

As can be seen from the commented version of the code, the time complexity is linear `O(n)`. In terms of memory, a maximum of `n+1` variables will be assigned. So that's `O(n)`.
> 3 votes

# Answer
# APL (Dyalog), 11 bytes

As per the new rules, throws an error if no duplicates exist.

```
⊢⊃⍨⍬⍴⍳∘≢~⍳⍨

```

Try it online!

`⍳⍨` the indices of the first occurrence of each element

`~` removed from

`⍳∘≢` of all the indices

`⍬⍴` reshape that into a scalar (gives zero if no data is available)

`⊃⍨` use that to pick from (gives error on zero)

the argument
> 3 votes

# Answer
# K (ngn/k), 11 bytes

```
*(~':?',\)#

```

Try it online!

```
*(~':?',\)#
 (       )#   keep the elements where the left function returns true
              (when applied to the whole array):
       ,\       prefixes
     ?'         uniquify each
  ~':           is it the same as previous?
*             first element

```
> 3 votes

# Answer
# MATL, 8 bytes

```
&=Rsqf1)

```

Gives an error (without output) if no duplicate exists.

Try at **MATL Online!**

### Explanation

```
&=   % Implict input. Matrix of all pairwise equality comparisons
R    % Keep the upper triangular part (i.e. set lower part to false)
s    % Sum of each column
q    % Subtract 1
f    % Indices of nonzero values
1)   % Get first. Gives an error is there is none. Implictly display

```
> 2 votes

# Answer
# J, ~~17~~ 16 bytes

```
(*/{_1,~i.&0)@~:

```

### How?

```
(*/{_1,~i.&0)@~:

             @~: returns the nub sieve which is a vector with 1 for the first occurrence of an element in the argument and 0 otherwise

        i.&0     returns the first index of duplication

    _1,~         appends _1 to the index

 */              returns 0 with duplicates (product across nub sieve)

     {           select _1 if no duplicates, otherwise return the index

```
> 2 votes

# Answer
# , 28 bytes

```
(x=scan())[duplicated(x)][1]

```

Try it online!
> 2 votes

# Answer
# R, 34 bytes

```
c((x=scan())[duplicated(x)],-1)[1]

```

Cut a few characters off the answer from @djhurio, don't have enough reputation to comment though.
> 2 votes

# Answer
# Java 8, 82 78 76 bytes No longer viable, 75 67 64 bytes below in edit

As a lambda function:

```
a->{Set<Long>s=new HashSet<>();for(long i:a)if(!s.add(i))return i;return-1;}

```

Probably can be made much smaller, this was very quick.

### Explanation:

```
a->{                                //New lambda function with 'a' as input
    Set<Long>s=new HashSet<>();     //New set
    for(long i:a)                   //Iterate over a
        if(!s.add(i))               //If can't add to s, already exists
            return i;               //Return current value
        return-1;                   //No dupes, return -1
}

```

# \*Edit\*

75 67 64 bytes using the negation strategy:

```
a->{int i=0,j;while((a[j=Math.abs(a[i++])-1]*=-1)<0);return++j;}

```

Try it online!

(-3 bytes thanks to @Nevay)

### Explanation:

```
a->{                                         //New lambda expression with 'a' as input
    int i=0,j;                               //Initialise i and declare j
    while((a[j=Math.abs(a[i++])-1]*=-1)<0);  //Negate to keep track of current val until a negative is found
    return++j;                               //Return value
}

```

Loops over the array, negating to keep track. If no dupes, just runs over and throws an error.

Both of these work on O(n) time and O(n) space complexity.
> 2 votes

# Answer
## Dyalog APL Classic, 18 chars

Only works in `⎕IO←0`.

```
     w[⊃(⍳∘≢~⍳⍨)w←¯1,⎕]

```

Remove from the list of indices of the elements of the argument with a prepended "-1" the list indices of its nub and then pick the first of what's left. If after the removal there only remains an empty vector, its first element is by definition 0 which is used to index the extended argument producing the desired -1.
> 2 votes

# Answer
# Ruby, ~~28~~ 36 bytes

Misunderstood the challenge the first time. `O(n)` time, `O(n)` space.

```
->a{d={};a.find{|e|b=d[e];d[e]=1;b}}

```

Try it online!
> 2 votes

# Answer
# Java (OpenJDK 8), ~~65~~ ~~117~~ 109 bytes

Previous 65 byte solution:

```
r->{for(int a,b=0,z,i=0;;b=a)if((a=b|1<<(z=r[i++]))==b)return z;}

```

New solution. 19 bytes are included for `import java.math.*;`

*-8 bytes thanks to @Nevay*

```
r->{int z,i=0;for(BigInteger c=BigInteger.ZERO;c.min(c=c.setBit(z=r[i++]))!=c;);return z;}

```

Try it online!

# Edit

The algorithm in my original program was fine, but the static size of the datatype used meant that it broke fairly quickly once the size went above a certain threshold.

I have changed the datatype used in the calculation to increase the memory limit of the program to accommodate this (using `BigInteger` for arbitrary precision instead of `int` or `long`). However, this makes it debatable whether or not this counts as `O(1)` space complexity.

I will leave my explanation below intact, but I wish to add that I now believe it is impossible to achieve `O(1)` space complexity without making some assumptions.

# Proof

Define `N` as an integer such that `2 <= N` .

Let `S` be a list representing a series of random integers `[x{1}, ..., x{N}]`, where `x{i}` has the constraint `1 <= x{i} <= N`.

The time complexity (in Big-O notation) required to iterate through this list exactly once per element is `O(n)`

The challenge given is to find the first duplicated value in the list. More specifically, we are searching for the first value in `S` that is a duplicate of a previous item on the list.

Let `p` and `q` be the positions of two elements in the list such that `p < q` and `x{p} == x{q}`. Our challenge becomes finding the smallest `q` that satisfies those conditions.

The obvious approach to this problem is to iterate through S and check if our `x{i}` exists in another list `T`: If `x{i}` does not exist in `T`, we store it in `T`. If `x{i}` does exist in `T`, it is the first duplicate value and therefore the smallest `q`, and as such we return it. This space efficiency is `O(n)`.

In order to achieve `O(1)` space complexity while maintaining `O(n)` time complexity, we have to store unique information about each object in the list in a finite amount of space. Because of this, the only way any algorithm could perform at `O(1)` space complexity is if: 1. N is given an upper bound corresponding to the memory required to store the maximum number of possible values for a particular finite datatype. 2. The re-assignment of a single immutable variable is not counted against the complexity, only the number of variables (a list being multiple variables). 3. (Based on other answers) The list is (or at least, the elements of the list are) mutable, and the datatype of the list is preset as a signed integer, allowing for changes to be made to elements further in the list without using additional memory.

1 and 3 both require assumptions and specifications about the datatype, while 2 requires that only the number of variables be considered for the calculation of space complexity, rather than the size of those variables. If none of these assumptions are accepted, it would be impossible to achieve both `O(n)` time complexity and `O(1)` space complexity.

# Explanation

Whoo boy, this one took ~~an embarrassingly long time to think up~~ a bit of brain power.

So, going for the bonus is difficult. We need both to operate over the entire list exactly once **and** track which values we've already iterated over without additional space complexity.

Bit manipulation solves those problems. We initialize our `O(1)` 'storage', a pair of integers, then iterate through the list, OR-ing the ith bit in our first integer and storing that result to the second.

For instance, if we have `1101`, and we perform an OR operation with `10`, we get `1111`. If we do another OR with `10`, we still have `1101`.

Ergo, once we perform the OR operation and end up with the same number, we've found our duplicate. No duplicates in the array causes the program to run over and throw an exception.
> 2 votes

# Answer
# Husk, 4 bytes

```
←Ṡ-u

```

Returns `0` if no input contains no duplicate, try it online!

### Explanation

```
←Ṡ-u  -- takes a list X as input & returns 0 or first duplicate
 Ṡ-   -- compute X - ...
   u  --       ...   deduplicate X
←     -- get first element or 0 if empty

```
> 2 votes

# Answer
# Haskell, 34 bytes

```
import Data.List
f x=head$x\\nub x

```

Try it online! For an input `x = [2,3,3,1,5,2]`, `nub x` removes duplicates `[2,3,1,5]` and `x\\nub x` removes the elements of `nub x` from x, thus keeping the duplicates `[3,2]`. `head` returns the first element of hat list.

---

Point-free is the same byte count: `head.((\\)<*>nub)`.
> 2 votes

# Answer
# Nekomata \+ `-1`, 4 bytes

```
pƆᵗf

```

Attempt This Online!

```
pƆᵗf
p       Find a prefix of the input
 Ɔ      Split it into the last element and the rest
  ᵗf    Check if the last element is in the rest, and return it if it is

```

`-1` prints the first possible result, or nothing if there is no result.
> 2 votes

# Answer
# 05AB1E, 5 bytes

```
.ΔkNÊ

```

Outputs `-1` if there are no duplicated items, like in the challenge examples.

Try it online or verify both test cases.

**Explanation:**

```
.Δ     # Find the first element in the (implicit) input-list where the following is
       # truthy, or -1 if none are truthy:
  k    #  Get the first index of the current integer in the (implicit) input-list
   NÊ  #  Check whether it's NOT equal to the current find_first index
       # (after which the result is output implicitly as result)

```
> 2 votes

# Answer
# C#, 145 bytes

```
using System.Linq;a=>{var d=a.Where(n=>a.Count(t=>t==n)>1);return d.Select((n,i)=>new{n,i}).FirstOrDefault(o=>d.Take(o.i).Contains(o.n))?.n??-1;}

```

Probably a lot shorter way to do this in C# with a simple loop but I wanted to try it with Linq.

Try it online!

Full/Formatted version:

```
namespace System.Linq
{
    class P
    {
        static void Main()
        {
            Func<int[], int> f = a =>
            {
                var d = a.Where(n => a.Count(t => t == n) > 1);
                return d.Select((n, i) => new { n, i }).FirstOrDefault(o => d.Take(o.i).Contains(o.n))?.n ?? -1;
            };

            Console.WriteLine(f(new[] { 2, 3, 3, 1, 5, 2 }));
            Console.WriteLine(f(new[] { 2, 4, 3, 5, 1 }));

            Console.ReadLine();
        }
    }
}

```
> 1 votes

# Answer
# Haskell, ~~78~~ 69 bytes

```
 fst.foldl(\(i,a)(j,x)->(last$i:[j|i<0,elem x a],x:a))(-1,[]).zip[1..]

```

Try it online!

*Saved 9 bytes thanks to @nimi*

A basic path through the list. If the current element has not yet been seen (`i<0`) and is in the accumulator list (`elem x a`) then store the current index. Else, keep the index -1. In any case, add the current element to the accumulator list.

**EDIT**: I did not read the question carefully enough: this code outputs the index of the second element of a duplicate element.
> 1 votes

# Answer
# PROLOG (SWI), 54 + 3 = 57 bytes

```
f([H|_],L,H):-member(H,L).
f([H|T],L,X):-f(T,[H|L],X).

```

+3 bytes because it requires an empty list as its second argument:

```
f([5,3,2,1,2,3,5],[],X)

```

will unify X to the first duplicate value in the list.

Try it online!

Here's the basic algorithm: we have the list to parse, and an accumulator list that starts empty. For each element in the list: pop that element. If it is in the accumulator, return the element. Else, put it in the accumulator.
> 1 votes

# Answer
# Python 2, 71 65 bytes

Returns `None` if there is no duplicate element

**Edit:** -6 bytes thanks to @musicman523

```
def f(n):
 for a in n:
	u=-abs(a)
	if n[u]<0:return-u
	n[u]=-n[u]
```

Try it online!

**O(n)** time complexity, **O(n)** space complexity, **O(1)** auxiliary space.

As the input list uses **O(n)** space, the space complexity is bound by this. Meaning we cannot have a lower space complexity than **O(n)**

Does modify the original list, if this is not allowed we could do it in the same complexity with 129 bytes

# Explanation

Since every element is greater than 0 and less than or equal to the size of the list, the list has for each element a, an element on index a - 1 (0 indexed). We exploit this by saying that if the element at index i is negative, we have seen it before.

For each element a in the list n, we let u be negative the absolute value of a. *(We let it be negative since python can index lists with negative indices, and we would otherwise need to do* `u=abs(a)-1`) If the element at index u in the list is negative, we have seen it before and can therefore return -u *(to get the absolute value of a, as all elements are positive)*. Else we set the element at index u to be negative, to remember that we have seen an element of value a before.
> 1 votes

# Answer
# Jelly, 4 bytes

```
ŒQi0

```

Try it online!

In case that all elements are unique, this returns `0` (undefined behavior).
> 1 votes

# Answer
# K4, 12 bytes

**Solution:**

```
*<0W^*:'1_'=

```

**Example:**

```
*<0W^*:'1_'=2 3 3 1 5 2
3

```

**Explanation:**

Returns first item in the list for unique lists otherwise returns first dupe:

```
*<0W^*:'1_'= / the solution
           = / group the list, e.g. 2 3 1 5!(0 5;1 2;,3;,4)
        1_'  / drop first from each value, e.g. 2 3 1 5!(,5;,2;`long$();`long$())
     *:'     / first (*:) each ('), e.g. 2 3 1 5!5 2 0N 0N
  0W^        / fill (^) nulls with infinity (0W), e.g. 2 3 1 5!5 2 0W 0W
 <           / sort keys based on values, e.g. 3 2 1 5
*            / take the first, e.g. 3

```
> 1 votes

# Answer
## Alice, 21 bytes

```
/o/
\iHQ@/w].(?~!&WK?

```

Try it online!

### Explanation

The main idea is to store each value we've encountered on the tape and then use the search command to check whether the current value has already been written to the tape. It's important here that the tape is initially completely filled with `-1`s.

```
/      Switch to Ordinal mode.
i      Read all input as a string.
/      Switch back to Cardinal mode.
H      Take the absolute value of the top stack element. This doesn't really do
       anything to the numbers, because they're all positive anyway, but
       it forces Alice to convert the input string to individual integer
       values it contains, thus splitting the string.
/      Switch to Ordinal mode.
Q      Reverse the stack so that the first input is on top.
/      Switch back to Cardinal mode.
w      Push the current IP position onto the return address stack. This marks
       the beginning of the main loop.
         Call the current value on top of the stack X.
  ]      Advance the tape head (unnecessary on the first iteration, but
         we need to do it between iterations).
  .      Duplicate X.
  (      Search left of the tape head for X. If X isn't found nothing happens
         and we remain on a -1. Otherwise, the tape head jumps to that
         earlier occurrence.
  ?      Retrieve the value under the tape head. If X is new, this will be
         -1. Otherwise, it will be X. Call this value Y.
  ~!     Store X in the current cell.
  &W     Discard Y values from the return address stack. If Y is negative,
         this does nothing, otherwise it discards the one return address we
         have there, terminating the loop.
$K     If the return address is still there, jump back to the w to process
       the next element. Otherwise continue.
?      Retrieve X.
\      Switch to Ordinal mode.
o      Output the result.
H      Trim, does nothing.
@      Terminate the program.

```

I've got an alternative solution at the same byte count:

```
/o/
\iHQ@/w.!(]?h$WK[?

```

I also had a solution where I used the tape as a lookup table, storing at each index `X` whether `X` had already been seen in the sequence, but it ended up being a byte longer (it's conceptually easier, but moving the tape head to position `X` from an arbitrary positive position requires five bytes with `q&[&]`).
> 1 votes

# Answer
# x86-16 machine code, 22 bytes

```
00000000: 33c0 9992 d792 d7d7 3bc2 75f7 33c0 d792  3.......;.u.3...
00000010: d73b c275 f9c3                           .;.u..

```

Listing:

```
33 C0       XOR  AX, AX         ; AL = 0, starting hare position
99          CWD                 ; DL = 0, starting tortoise position
        L1:
92          XCHG AX, DX         ; swap t/h in AL
D7          XLAT                ; tortoise crawl to next
92          XCHG AX, DX         ; swap t/h in AL
D7          XLAT                ; hare hops
D7          XLAT                ; hare hops again
3B C2       CMP  AX, DX         ; did they land on same element?
75 F7       JNZ  L1             ; loop if not
33 C0       XOR  AX, AX         ; start tortoise at beginning to find first index match
        L2:
D7          XLAT                ; tortoise crawls
92          XCHG AX, DX         ; swap t/h in AL
D7          XLAT                ; hare hops
3B C2       CMP  AX, DX         ; did they land on same element?
75 F9       JNZ  L2             ; loop if not
C3          RET                 ; return to caller

```

The old Tortoise and Hare (cycle detection) algorithm... using as many 1 byte opcodes as possible.

* Time complexity: O(2n), linear
* Space complexity: O(1) (uses no additional memory - all work done in CPU registers)

As a callable function, input pointer to list at `[BX]`, output index in `AL`.

Test results using DOS DEBUG:
> 1 votes

# Answer
# Factor, 21 bytes

```
[ duplicates ?first ]

```

Try it online!

Returns `f` in case the input has no duplicates. This is idiomatic for Factor rather than `-1`. Let me know if that's not allowed and I can fix it (i.e. make it much longer).

* `duplicates` Return only the elements that repeat in a sequence (in order).
* `?first` Return the first element of a sequence or `f` if the sequence is empty.
> 1 votes

# Answer
# TI-Basic, 39 bytes

```
Prompt A
ʟA
Ans(1+sum(not(cumSum(seq(I≠1+sum(not(cumSum(Ans=Ans(I)))),I,1,dim(Ans

```

Output is stored in `Ans` and is displayed at the end. Throws an error if there are no duplicates.
> 1 votes

# Answer
# Gema, 46 characters

```
<N>=@cmpn{${$0;};;;;$0@end}@set{$0;1}
?=
\Z=-1

```

Sample run:

```
bash-5.1$ gema '<N>=@cmpn{${$0;};;;;$0@end}@set{$0;1};?=;\Z=-1' <<< '[2, 3, 3, 1, 5, 2]'
3

bash-5.1$ gema '<N>=@cmpn{${$0;};;;;$0@end}@set{$0;1};?=;\Z=-1' <<< '[2, 4, 3, 5, 1]'
-1

```

Try it online!
> 1 votes

# Answer
# K (ngn/k), 18 bytes

```
{x@({+/y=x}':x)?1}

```

Try it online!

A little bit lengthy, but works nonetheless. I still can't fully understand how this even works (especially the counting duplicates section) and I'm on mobile, so explanations will be edited later.
> 1 votes

# Answer
# Zsh, 48 bytes

```
for n;A+=($@[(in:2:)$n]);<<<$@[`printf ${(o)A}`]

```

Try it online!

Input is via argument array `$@`.
`A` is an array of indexes of secondary duplicates.
`printf ${(o)A}` sorts `A` leaving only the lowest index.
`<<<$@[ ]` prints the argument at that index.
> 1 votes

# Answer
# Nibbles, 3 bytes (6 nibbles)

```
/-$`$$

```

Attempt This Online!

Outputs `0` if there are no duplicated elements.

```
/-$`$$
 -      # remove
   `$   # unique elements of
     $  # input
  $     # from the input
        # (this leaves only duplicated elements,
        # in their original order);
/       # get the first element
        # (actually, fold returning left-hand element at each step,
        # but result is to return left-most element)

```

5 bytes to instead return `-1` when there are no duplicated elements, as in the example and initial spec: `/:-$`$$-1`
> 1 votes

# Answer
# Axiom 96, bytes

```
g(a:List INT):INT==(for i in 2..#a repeat(for j in 1..i-1 repeat if a.i=a.j then return a.i);-1)

```

it is O(n^2)
> 0 votes

# Answer
# Javascript, 54 bytes

```
a=>(b=[],a.find(e=>b.includes(e)?e:(b.push(e),0))||-1)

```

Uses another array to keep track of the already encountered values.
> 0 votes

# Answer
# C#, ~~65~~ 67 bytes

With thanks to LiefdeWen for the 89 bytes base code here, here's an further shortened version of that

```
a=>{for(int p=0,q=0;;q++)for(p=0;p<q;)if(a[q]==a[p++])return a[q];}

```

We can dispense with the return -1 and length check as it's apparently OK to throw an exception if not found, so we just let the outer loop run off the end of the array. Some other whitespace changes, and jigging the declarations around to reduce the number of times we write "int" etc..
> 0 votes

# Answer
# Python 2, ~~115~~ 113 bytes

```
a,i,k=input(),0,[]
while 1:
	if i==len(a):print-1;break
	elif a[i]not in k:k+=[a[i]]
	else:print a[i];break
	i+=1

```

Try it online!
> 0 votes

# Answer
# 05AB1E, 16 bytes

```
ε¹SsQƶ0K1è}W<¹sè

```

Try it online!
> 0 votes

# Answer
# Perl 5, 36 + 2 (-ap) = 38 bytes

Runs in O(n) time.

```
$s{$_}=1while!$s{$_=shift@F};$_||=-1

```

Try it online!

Takes the input list space separated.
> 0 votes

# Answer
# Python 2, 59 bytes, O(n) time, O(n) memory

```
a=input()
i=0
for x in a:
 if i&1<<x:print x;break
 i^=1<<x

```

Try it online!

This does one pass of the list. Thus is **O(n)** For memory it stores a integer `i`, which has bits representing which numbers have already been visited. If a number has already been visited we output, otherwise we turn the bit on. If no matches are found we do nothing.

This makes a slight improvement over the naïve way which requires copying the list at the cost of **O(n log n)** memory.
> 0 votes

# Answer
# C (gcc), 98 bytes

**0-indexed**

Takes a space separated list of integers. returns `i < n` on a successful match and `i == n` on failure.

time complexity is O(n^2) yuck!

space complexity is O(1)

```
program-name.exe 58 77 57 7 75 44 29 97 92 59 36 52 95 87 44 24 47 18 34 22
Returns 14  (the two 44s)

```

Golfed

```
i=1,j;main(int c,char**v){for(;i<c;i++)for(j=i-1;j;j--)if(!strcmp(v[i],v[j]))goto f;f:return i-1;}

```

Try it online!

Ungolfed

```
i=1,j;
main(int c, char**v){
    for(;i < c; i++)
        for(j=i-1; j; j--)
            if(!strcmp(v[i], v[j]))
                goto f;
    f:
    return i-1;
}

```
> 0 votes

# Answer
# PowerShell, 93 bytes

```
$c=0..$a.Count;$i=0;$r=($a|%{$i++;if($c[$_]++ -ne $_){$i}});if($r.Count -gt 0){$r[0]}else{-1}

```

Try it online!
> 0 votes

# Answer
# JavaScript (Node.js), 81 bytes

Time complexity is O(n) !!!!

Space complexity is O(1) !!!!

```
a=>a.reduce((r,e,i)=>r?r:(a[(e<0?~e:e)-1]>0?((a[(e<0?~e:e)-1]^=-1)?0:0):i+2),0)-1

```

Try it online!

Strategy

This algorithm leverages the fact that indexes are positive but numbers in javascript are signed. Also, zeros are not allowed input. As long as the array is not longer than 2^31, this solution will work. I double the use of the original array as my lookup array -- marking a visited number by switching the value at that index with its 2's compliment.
> 0 votes

# Answer
# APL NARS 52 char 104 bytes

```
f←{1≠⍴⍴⍵:¯1⋄v←(⍵⍳⍵)-⍳⍴⍵⋄m←v⍳(v<0)/v⋄m≡⍬:¯1⋄(1⌷m)⌷⍵}

```

comments (for me f could return results even for vectors of characters that here seems to be the old strings)

```
1≠⍴⍴⍵:¯1     if ⍵ has rank different from 1 than it is not a vector so return -1
v←(⍵⍳⍵)-⍳⍴⍵   v is 0 0 0...0 only if there are not repetitions, else there is some value <0
m←v⍳(v<0)/v   m return the indices j of v where v[j]<0, and so ⍵[j] are all the duplicates
m≡⍬:¯1       if m is void than that index not exist, so no duplicate and return -1
(1⌷m)⌷⍵      else return the value in ⍵ of the first element of m

```

results

```
  f 1
¯1
  f 1,2,3,4
¯1
  f 1 2 3 3
3
  f 2 3 3 1 5 2
3
  f ,1
¯1

```
> 0 votes

# Answer
# Python 3, 47 bytes

```
f=lambda l,i=0:l[i]if l[i]in l[:i]else f(l,i+1)

```

Try it online!
> 0 votes

# Answer
# Add++, 69 bytes

```
D,k,@@*,BF€=B]ßEB*MVcGA$p
D,w,@@,BF€=s1<
D,l,@~,$
L~,AÞwB]dVbUG€k»lbU

```

Try it online!

## How it works

Oddly enough, despite Add++ having a deduplicate command, this doesn't use it. This exits with an error code of **1** when there is no duplicated element.

We start by removing any elements without more than one occurrence, in order to leave the stack with an array containing the original array, preserving order, without any elements which only occur once. This is done by the use of filtering by the dyadic function **w**:

```
D,w,@@,BF€=s1<
L~,AÞw

```

Here, the lambda is implicitly called with the argument. The `~` tells it to unpack its argument to the stack beforehand, then the `A` pushes the argument to the stack. Thesefore, if the input looks like `[a b c a c]`, the stack would look like

```
[a b c a c [a b c a c]]

```

We want this structure, called **dyad-binding**, due to the way the **filter-keep** quick, `Þ`, works in regard to non-monadic arguments. Here, its functional argument is **w**, a dyadic (two argument) function. This means that, instead of filtering over each element in the stack using **w**, it pops the top element of the stack, the list `[a b c a c]` in this case, and uses that as the right argument when filtering every other element.

So, for one iteration of **w**, the stack may look like this at the start of execution:

```
[[a b c a c] a]

```

Then `BF` flattens the stack, and then we come to another dyadic quick: . Again, the popping behaviour is simulated, and `a` is used as the left argument to the succeeding function, the equality operator in this case. This compares `a` with the elements of `[a b c a c]`, yielding an array of **1**s and **0**s. By now, the stack looks something like this

```
[1 0 0 1 0]

```

Finally, `s` takes the sum, and `1<` asserts that it is greater than **1**. This essentailly counts the occurences of each element of the input in the input itself, and removes them if the count is only **1** i.e. the element isn't duplicated at some point.

After applying `Þw` to the input, the stack results in

```
[a c a c]

```

We'll call this array **A**. The rest of the code is determining which of these remaining elements occurs for the second time first i.e. the actual task in the challenge.

Next, we want to perform **k** over the remaining list. In order to do this, with **k** being dyadic and taking **A** as its left argument. Again, we want to create the dyad-binding structure, but using the elements of **A** instead of the arguments. In a general case, if the stack looks like `[a b c d e]`, where `a - e` are arbitrary pieces of data, the following code will convert that into a dyad-binding structure:

```
B]dVbUG

```

So, this makes our stack look like `[a c a c [a c a c]]`, before calling **k** over ach of the elements, using the array as the left argument.

```
D,k,@@*,BF€=B]ßEB*MVcGA$p

```

**k** is our main function to isolate the first deduplicated element. Here, we have our two arguments, **I**, the element in the array being iterated over, and **A**, our array containing the elements that occur more than once. The first part of the code, `BF€=`, identifies which elements of **A** are equal to **I**. Now, we generate the *truthy* indices - the indices of elements in **A** that are equal to **I**. There is a bug in `ßE`, causing it to start from **0** (corrected after the challenge was posted). However, as this means the first occurence if **I** will always be set to **0** because of this bug, and the offset of **1** doesn't change between elements, this means that we can avoid the lengthier `dbLBc` which is bug free. Let's use `a` as an example value for **I**. Now, our stack resembles

```
[[0 1] [1 0] [2 1] [3 0]]

```

The first element is the 0-based index **i**, the second whether or not **I = A\[i\]**. Next, we remove the indexes where **I ≠ A\[i\]**, by taking the product of each pair with `B*`, then taking the maximum value with `MVcG`. Finally, we push **I** to the stack and pair them as a list. With **I** as `a`, the final value returned is:

```
[2 a]

```

This process happens over each element of **A**, eventually leading to a series of paired lists of the highest index of the element of **A** in **A** itself. Finally we want to find the element which has the *lowest* first element, the element whose duplcicate appears first. Here, as Add++ doesn't have a builtin to get the first or last element of a list, we use our third helper function **l**:

```
D,l,@~,$
L~,…»l…

```

While Add++ doesn't have a builtin for head of an array, it does have a **minimum-by** quick, `»`. We take the list which has the minimum return value when passed through the function **l**. This helper function unpacks its argument to the stack before performing any commands with the `~` command, then `$` swaps them, so the index comes first and is the value returned. Essentially, we return the element with the smallest duplicated element.

Unfortunately, this returns the entire array, both the index and the element, rather than just the element, so we append a `bU` to unpack this array to the stack, returning only the last element of the pair - the first duplicated element.
> 0 votes

# Answer
# C (gcc), 50 bytes

```
g;main(i){scanf("%d",&i);return i[&g]++?i:main();}

```

Try it online!

# C (gcc), 51 bytes

```
g;main(i){for(;scanf("%d",&i),i[&g]^=1;);return i;}

```

Try it online!

# C (gcc), 56 bytes

```
g;main(i){scanf("%d",&i);i[&g]++?printf("%d",i):main();}

```

Try it online!
> 0 votes

# Answer
# Japt , 5 bytes

```
VaWbU

```

Try it
> 0 votes

# Answer
# Pip, 13 bytes

```
Tg@iNgHiUig@i

```

Takes the numbers as separate command-line arguments. Try it here! Or, here's a 15-byte equivalent in Pip Classic: Try it online!

### Explanation

```
               g is list of cmdline args; i is 0 (implicit)
T              Loop till
 g@i           the i'th element of g (0-indexed)
    N          is in
     gHi       the first i elements of g:
        Ui      Increment i
          g@i  Return the i'th element of g

```

This outputs the first duplicate or, if there are no duplicates, the first number in the list (because the indexing wraps around).
> 0 votes

# Answer
# TI-Basic, 32 bytes

```
Prompt A
Repeat 2=Ans(I
I+1→I
cumSum(ʟA=ʟA(I
End
ʟA(I

```

needs a fresh interpreter or `I` initialized to `0`. Will error if there is no duplicates
> 0 votes

# Answer
# JavaScript (Node.js), 29 bytes

```
x=>x.find(z=>(x[~z]+={})[25])

```

Try it online!

No effort on bonus at all

-1 from SuperStormer
> 0 votes

# Answer
# Go, 97 bytes, \\$O(n)\\$ time, \\$O(n)\\$ space

```
func (l[]int)int{m:=make(map[int]int)
for i,e:=range l{if _,o:=m[e];o{return e}
m[e]=i}
return-1}

```

Attempt This Online!

Goes over the input slice exactly once per element. The map stores a pair per element, meaning \\$O(n)\\$ space as well.
> 0 votes

# Answer
# C#, 48 bytes

```
x=>x.Where((_,i)=>x[..i].Contains(x[i])).First()

```

Try it online!

### Alternative without LINQ, 58 bytes

```
x=>{for(int i=0;;)if(x[..++i].Contains(x[i]))return x[i];}

```

Try it online!
> 0 votes

# Answer
# Arturo, 38 bytes

```
$->a[0-1select.n:1a=>[in?&take a<=1+]]

```

Try it!

```
$->a[              ; a function taking an arg a
    0-1            ; push -1
    select.n:1a=>[ ; select the first elt in a that
        in?&       ; is the current elt in
        <=1+       ; increment stack and duplicate
        take a     ; take that many of the first elts in a
    ]              ; end select
]                  ; end function

```
> 0 votes

---
Tags: code-golf, array
---