-synx-'s blog

How to find the odd element (generalized version) in the list?
By -synx-, history, 9 years ago, In English

Given a list of n numbers in which all but one repeat exactly k times, but the remaining one appears less than k times (and at least once).
Find this number (which repeats less than k times).
Expected Complexity
Time  ≤ O(nlgk)
Memory  ≤ O(lgk)

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (16)
| Write comment?
»
9 years ago, hide # |
 
Vote: I like it -16 Vote: I do not like it

Use quicksort to sort in nlogk and then traverse array to find element which occurs less than k times in O(n).

→ Reply
»
9 years ago, hide # |
← Rev. 4  
Vote: I like it +4 Vote: I do not like it

Hint: for k = 2 we have the classical 'xor all elements' problem. Xorring m-bit numbers is just adding vectors in . Can you generalize this?

EDIT: I am assuming here that the number of bits is considered O(1).

→ Reply
  • »
    »
    9 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Yes, it can be generalized to xor base k, but the issue that does not arise in k=2 case is that number is present exactly twice or exactly once, which greatly simplifies the problem (the answer is just xor of all numbers),
    but for general k, how do we retrieve the number which repeats greater than 1 time and less than k times?

    → Reply
    • »
      »
      »
      9 years ago, hide # ^ |
       
      Vote: I like it +1 Vote: I do not like it

      The number repeats 1 ≤ i < k times, so all positions in the final vector will have their value set to 0 (this bit is turned off in the required number) or to i (this bit is turned on in the required number).

      → Reply
»
9 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

For each bit store the value modulo k. Get the number, divide it by (n%k).

→ Reply
  • »
    »
    9 years ago, hide # ^ |
     
    Vote: I like it -13 Vote: I do not like it

    What if the coefficient of (n%k) is divisible by k, we wouldnt be able to retrieve in that case, right?

    → Reply
    • »
      »
      »
      9 years ago, hide # ^ |
       
      Vote: I like it +7 Vote: I do not like it

      n % k < k, it represents number of occurences of required number

      → Reply
      • »
        »
        »
        »
        9 years ago, hide # ^ |
         
        Vote: I like it -8 Vote: I do not like it

        lets say n=6, k=4,
        and list is [3, 3, 3, 3, 2, 2],
        how will your approach work?

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, hide # ^ |
          ← Rev. 2  
          Vote: I like it +7 Vote: I do not like it

          bit 1 -> 4 -> 0(modulo k)

          bit 2 -> 6 -> 2(modulo k)

          num = 4, divide it by (6%4) -> answer is 2

          → Reply