Repeated digits


Submit solution

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

Comments


  • 0
    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


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

    please where is the problem in my code!


    • 0
      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


  • 0
    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


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


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

        bro, I didn't understand


        • 0
          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) .


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


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


      • 2
        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!


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

    I think the constraints of N should be stated.


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

      wait is a < N ??


      • 0
        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) .


  • -1
    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


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

      input()

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


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

        using map give me a valueError because of the memory limit


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

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


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

      no, it's not said in the statement.