-synx-'s blog

How to find the odd element (generalized version) in the list?
By -synx-, history, 6 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?
»
6 years ago, # |
  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
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Storing the elements of list would require O(n) memory!

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 3   Vote: I like it -14 Vote: I do not like it

      Use in place quicksort to do it in O(lgn)

      See this thread — https://apps.topcoder.com/forums/?module=Thread&threadID=753840&start=0&mc=7

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

        You cant read the elemenets into an array, the memory complexity O(lgk) I mentioned is strict, it does not mean extra space complexity.

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

          Can you give me the source of the question ??

          → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          I am not sure but i think you can xor each number in base k to get the solution. It takes O(logk) memory. And O(n*logk) time complexity if you consider xor as constant time operation.

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

            Yes, this was my intended idea. But the problem is at the end of xoring in base k, we will get the ans only if it repeats once. (however it can repeat [1, k) times)

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

              I think this may be done in O(klgk considering k<n it still remains nlgk). After finding the answer see if it can be expressed as xor of a same number 1,2,...,k-1 times. Of course I am not sure of this one also.

              → Reply
»
6 years ago, # |
← 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
  • »
    »
    6 years ago, # ^ |
      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
    • »
      »
      »
      6 years ago, # ^ |
        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
»
6 years ago, # |
  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
  • »
    »
    6 years ago, # ^ |
      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
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          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
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
          ← 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