49
\$\begingroup\$

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?

\$\endgroup\$
1
  • \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. \$\endgroup\$ Commented Sep 3, 2017 at 13:12

67 Answers 67

2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
3
  • \$\begingroup\$ What was wrong with the original "Outputs an empty string if there are no duplicates" 4-byte version? \$\endgroup\$ Commented Jul 28, 2023 at 11:52
  • 1
    \$\begingroup\$ @DominicvanEssen It outputs the first integer that occurs more than once, instead of the first result that occurred before. So for the first test case ([2,3,3,1,5,2]) it would incorrectly result in 2 instead of 3. \$\endgroup\$ Commented Jul 28, 2023 at 12:12
  • \$\begingroup\$ Ah, thanks for clarifying. (Not that I ought to have been skulking around in the edit history...) \$\endgroup\$ Commented Jul 28, 2023 at 12:13
1
\$\begingroup\$

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();
        }
    }
}
\$\endgroup\$
3
  • \$\begingroup\$ Here is the simple loop version. But I like the Linq version much more. \$\endgroup\$
    – LiefdeWen
    Commented Jul 31, 2017 at 13:13
  • \$\begingroup\$ @LiefdeWen Post it as an answer :) Though I do usually like Linq better too :) Might be able to get it shorter with Linq too but I'm now sure. \$\endgroup\$ Commented Jul 31, 2017 at 13:16
  • \$\begingroup\$ Nah, this question is overpopulated and I would rather you get the up-votes for this question. \$\endgroup\$
    – LiefdeWen
    Commented Jul 31, 2017 at 13:17
1
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ You can use the "Shorter Conditional" from our "Tips for golfing in Haskell": \ ... ->(last$i:[j|i<0,elem x a],x:a). Also: no need for the f=, because unnamed functions are allowed. \$\endgroup\$
    – nimi
    Commented Jul 31, 2017 at 14:44
  • \$\begingroup\$ @nimi thanks for the tip! \$\endgroup\$
    – jferard
    Commented Jul 31, 2017 at 20:16
1
\$\begingroup\$

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.

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

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.

\$\endgroup\$
6
  • \$\begingroup\$ Nice job! 65 bytes \$\endgroup\$ Commented Aug 10, 2017 at 5:50
  • \$\begingroup\$ Are you sure this is O(1) in memory? You are still using n bits of memory to store what numbers have already been visited, even though the bits are in the sign. It seems to me that this is O(n) in disguise \$\endgroup\$
    – Wheat Wizard
    Commented Aug 10, 2017 at 7:06
  • \$\begingroup\$ Technically this uses O(n) space - the n sign bits. If the array can only hold values between 1 and n, like how it was given, then it obviously doesn't work. \$\endgroup\$
    – Oliver Ni
    Commented Aug 10, 2017 at 7:36
  • \$\begingroup\$ This really just comes down to the representation you choose for the numbers. If unsigned numbers are used, then this is O(n) auxiliary space. If signed numbers are used, then the sign bit is already there, meaning O(1) auxiliary space. \$\endgroup\$ Commented Aug 10, 2017 at 7:52
  • \$\begingroup\$ I agree with you there. I personally would let you slide using signed integers as long as you didn't use the sign bit, it should be about the algorithm not the technicalities of the system. That being said I do think if you are going to use the sign bits you have to count them. I think this answer is pretty clever. If I any votes left today I would upvote it to counteract the downvote. \$\endgroup\$
    – Wheat Wizard
    Commented Aug 10, 2017 at 14:32
1
\$\begingroup\$

Jelly, 4 bytes

ŒQi0

Try it online!

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

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

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
\$\endgroup\$
1
\$\begingroup\$

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 -1s.

/      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&[&]).

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

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.
\$\endgroup\$
1
\$\begingroup\$

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.

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

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:

enter image description here

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

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!

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

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.

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

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.

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

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

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

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)

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

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.

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

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..

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Pretty sure you can cut 1 char by making the second loop a while. a=>{for(int p=0,q=0;;q++)while(p++<q)if(a[q]==a[p])return a[q];} \$\endgroup\$
    – Broom
    Commented Aug 3, 2017 at 15:08
  • \$\begingroup\$ I checked, and it turns out, alas, it doesnt work out.. Doing p++<q means that although p is indeed incremented after the check of p<q, it is incremented before the inner loop code of if(a[p]==a[q]).. this has the undesirable effect of comparing a[1]==a[1] on the second iteration (q=1) which breaks the program. Still a useful comment though as it allowed me to chase down a bug (missing p=0 on inner loop), that unfortunately added 3 bytes but I was able to save 1 by moving p++ to the if, thanks to your suggestion \$\endgroup\$
    – Caius Jard
    Commented Aug 3, 2017 at 15:36
0
\$\begingroup\$

05AB1E, 16 bytes

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

Try it online!

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

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.

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

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.

\$\endgroup\$
3
  • \$\begingroup\$ i needs to have n bits, so I think it should be O(n) memory. (i can take values up to 2**n - 2 even if there is a duplicate.) \$\endgroup\$
    – tehtmi
    Commented Aug 10, 2017 at 6:57
  • \$\begingroup\$ However, it is better than a copy of the list, as a copy of the list in general needs log(n)*n bits if we are equally as strict (log(n) bits per item times n items). \$\endgroup\$
    – tehtmi
    Commented Aug 10, 2017 at 7:02
  • \$\begingroup\$ @tehtmi Fixed now, thanks for that. I have trouble with space complexity. \$\endgroup\$
    – Wheat Wizard
    Commented Aug 10, 2017 at 7:05
0
\$\begingroup\$

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;
}
\$\endgroup\$
3
  • \$\begingroup\$ Time complexity is related to looping. A loop that touches every slot of an array with size n is said to have time complexity O(n). Since you have a for loop inside another one, and each one is on the order O(n) (since they aren't always a constant range), your program has time complexity O(n^2). For more info about Big O Notation, check out this Wikipedia page. \$\endgroup\$ Commented Aug 11, 2017 at 15:44
  • \$\begingroup\$ I see, thanks for the info. I updated my answer. \$\endgroup\$
    – Marcos
    Commented Aug 11, 2017 at 15:51
  • \$\begingroup\$ The time complexity should be O(n^2 log m), where n is how many numbers there are, and m is the largest number given. This is because strcmp takes linear time with respect to the number of characters in each string \$\endgroup\$ Commented Aug 13, 2017 at 16:58
0
\$\begingroup\$

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!

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

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.

\$\endgroup\$
4
  • \$\begingroup\$ We've had this discussion on another answer using a similar algorithm. Although it may appear that this is O(1) you are actually using O(n) memory. Since you use the sign bit of each number you are actually using 1 bit per number. The fact that the bits are already allocated by Javascript is just a trick to make it appear as if you are using less memory. \$\endgroup\$
    – Wheat Wizard
    Commented Aug 13, 2017 at 4:30
  • \$\begingroup\$ I don't think you are being intentionally deceitful here, the concept of additional memory that seems to be embedded in the question is rather flawed. O(n) memory is required just to store the array already unless you are using a stream so any algorithm that stores the entire list in memory at any point is truly O(n log n) anyway (log n because each number takes at most log n bits to store). \$\endgroup\$
    – Wheat Wizard
    Commented Aug 13, 2017 at 4:31
  • \$\begingroup\$ @WheatWizard Wouldn't it be O(n log m) since n (the number of inputs) and m (the largest integer) are independent of one another? Though I usually assume integers are a fixed width (more background in Java/C++/C than Python/Javascript) which means their storage is O(1) \$\endgroup\$ Commented Aug 13, 2017 at 16:55
  • \$\begingroup\$ @WheatWizard, I see your point. Like you said, the question wording is a bit open. However, I think this is a legitimate solution. No other solution makes any attempt to use fewer bits to store each number. The parameters were for O(1) additional space complexity and the array can only contain numbers between 1 and a.len. It is worded like a homework question begging for such a solution. You are correct about O(n log n) initial space complexity if you assume that storage space per number is not fixed. This is seldom an assumption and I don't think it was implied in this competition. \$\endgroup\$ Commented Aug 13, 2017 at 17:00
0
\$\begingroup\$

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!

\$\endgroup\$
10
  • 1
    \$\begingroup\$ I might be wrong, but doesn't the fact that your list k can have up to n elements make this a O(n) space complexity solution? \$\endgroup\$
    – Value Ink
    Commented Aug 4, 2017 at 7:47
  • \$\begingroup\$ Not to mention the fact that check a[i] in k may take O(n) (unless Python arrays is special) \$\endgroup\$
    – DELETE_ME
    Commented Aug 4, 2017 at 7:55
  • \$\begingroup\$ @ValueInk you are correct. my bad. \$\endgroup\$ Commented Aug 7, 2017 at 19:36
  • \$\begingroup\$ This is actually O(n log n) in space complexity, because the numbers in your k take O(log n) memory to store each and there are as many as n of them. \$\endgroup\$
    – Wheat Wizard
    Commented Aug 10, 2017 at 7:08
  • \$\begingroup\$ I should think user202729 is correct too, making your algorithm O(n^2) time complexity. The while loop is O(n) (early break or not), and so is the in call. \$\endgroup\$
    – Sanchises
    Commented Aug 10, 2017 at 7:14
0
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ It's possible to use Dyalog's codepage to make it so it's 52 bytes. Also, you don't need to store the results in a function. And would either of these work in NARS? {1≠⍴⍴⍵:¯1⋄⍬≡m←v⍳v/⍨0>v←(⍵⍳⍵)-⍳⍴⍵:¯1⋄⍵⌷⍨1⌷m} or {1≠⍴⍴⍵:¯1⋄⍬≡m←v⍳(0>v)/v←(⍵⍳⍵)-⍳⍴⍵:¯1⋄(1⌷m)⌷⍵}? \$\endgroup\$
    – Adalynn
    Commented Nov 30, 2017 at 16:39
  • \$\begingroup\$ @Zacharý I like "f←{1≠⍴⍴⍵:¯1⋄⍬≡m←v⍳(0>v)/v←(⍵⍳⍵)-⍳⍴⍵:¯1⋄(1⌷m)⌷⍵}" thank you; for what regard if the name of function I ' am not agree with community, for me the name has to be inside the solution, it will for me 2 characters more (or +4 bytes). It seems my target is not 100% codegolf, perhaps 80% . It would be better for a solution in APL count for codegolf it would be in characters and not in bytes \$\endgroup\$
    – user58988
    Commented Nov 30, 2017 at 17:52
0
\$\begingroup\$

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!

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

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 1s and 0s. 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.

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

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!

\$\endgroup\$

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.