## Repeated digits

Points: 20
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

Given a non-empty array of integers, every element appears two times except for one, which appears exactly once. Find that single one, ine linear time, with no extra memory.

#### Input Specification

The first line of the input file contains one integer $$N$$ the size of the array A. The next line contains $$N$$ space separated integers $$a_i$$ ($$1 \leq a_i \leq 10^5$$).

#### Output Specification

Output one line with one integer : the element that occurs exactly once.

#### Sample Input

7
2 2 3 3 4 4 1

#### Sample Output

1

• AkramElOmrani  commented on Jan. 10, 2021, 12:39 a.m. edited

could you please tell me what is the 'cnt' array ? Edit : Nerver mind xor made the job

• ilyassozo  commented on Dec. 13, 2020, 8:56 p.m.

please where is the problem in my code!

• tamahom  commented on Dec. 14, 2020, 5:14 p.m. edit 2

First of all your code won't pass cause it's O(N^2) which will lead to Time limit exceeded. Secondly you use num = list(input().split(" ")) actually the input().split() by default separate the input by single spaces and then it return a list of Strings so to read Ints you can either use this num = list(map(int,input().split()) or num = [*map(int,input().split())] or num = [int(i) for i in input().split()] and you need to change your code because it won't pass, Try to read about the operation XOR and re-attempt the problem

• Soufiane_ELM  commented on Aug. 26, 2020, 12:08 p.m.

Any hint guys the program give me value error the time complexity is linear

• aymanemoutei  commented on Aug. 26, 2020, 12:52 p.m.

"Find that single one, in linear time, with no extra memory" , while you stored the occurence of numbers in a map .

• Soufiane_ELM  commented on Aug. 26, 2020, 1:04 p.m.

bro, I didn't understand

• aymanemoutei  commented on Aug. 26, 2020, 1:21 p.m.

You shouldn't use the "cnt" array , as it has a linear memory complexity . It is required to solve it in O(1) .

• akwa_blue  commented on June 8, 2020, 3:12 a.m.

I don't understand this problem. For the test case 2, my program gives 5 as an answer, and I checked that it appears only once in the input, yet I get WA as a result. Any ideas why? Aside from that $$a_i$$ is not less than $$10^5$$. There are elements larger than that.

• aymanemoutei  commented on June 8, 2020, 2:01 p.m.

"Find that single one, in linear time, with no extra memory" , while you used an array of size 1e5.

• akwa_blue  commented on June 8, 2020, 3:09 p.m.

Hmm I see. It should give a memory limit or something in that case, not WA because it's misleading. Thank you!

• F0lio  commented on June 1, 2020, 12:15 a.m.

I think the constraints of N should be stated.

• Rabraghib  commented on June 14, 2021, 2:11 a.m. edited

wait is a < N ??

• youssefboumhaout  commented on June 14, 2021, 11:17 a.m.

in short it is necessary to write the number which appears only once in the list , that mean is necessary to a[i] appears once in the array and N is the length of the array (a.length() == a) .

• Mahdi_Oulkadi  commented on May 31, 2020, 12:04 a.m.

i don't think there is a solution for python users because of the input format i need a clarification please

• aymanrs  commented on May 31, 2020, 1:55 p.m. edit 2

input()

numbers = [i for i in map(int, input().split())]

• Mahdi_Oulkadi  commented on May 31, 2020, 8:34 p.m.

using map give me a valueError because of the memory limit

• Mexudi20  commented on May 28, 2020, 2:26 p.m.

the elements that appears two times , should always be next to each other ?

• aymanrs  commented on May 28, 2020, 5:15 p.m. edited

no, it's not said in the statement.