### -synx-'s blog

By -synx-, history, 4 years ago,

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)

• +3

 » 4 years ago, # |   -16 Use quicksort to sort in nlogk and then traverse array to find element which occurs less than k times in O(n).
•  » » 4 years ago, # ^ |   0 Storing the elements of list would require O(n) memory!
•  » » » 4 years ago, # ^ | ← Rev. 3 →   -14 Use in place quicksort to do it in O(lgn)
•  » » » » 4 years ago, # ^ |   0 You cant read the elemenets into an array, the memory complexity O(lgk) I mentioned is strict, it does not mean extra space complexity.
•  » » » » » 4 years ago, # ^ |   -8 Can you give me the source of the question ??
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » » 4 years ago, # ^ |   0 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)
•  » » » » » » » 4 years ago, # ^ |   0 I think this may be done in O(klgk considering k
 » 4 years ago, # | ← Rev. 4 →   +4 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).
•  » » 4 years ago, # ^ |   0 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?
•  » » » 4 years ago, # ^ |   +1 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).
•  » » » » 4 years ago, # ^ |   0 Thank you, I understood your explanation! :)
 » 4 years ago, # |   0 For each bit store the value modulo k. Get the number, divide it by (n%k).
•  » » 4 years ago, # ^ |   -13 What if the coefficient of (n%k) is divisible by k, we wouldnt be able to retrieve in that case, right?
•  » » » 4 years ago, # ^ |   +7 n % k < k, it represents number of occurences of required number
•  » » » » 4 years ago, # ^ |   -8 lets say n=6, k=4,and list is [3, 3, 3, 3, 2, 2],how will your approach work?
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   +7 bit 1 -> 4 -> 0(modulo k)bit 2 -> 6 -> 2(modulo k)num = 4, divide it by (6%4) -> answer is 2