Find a single number in a list when other numbers occur more than twice

Question

The problem is extended from Finding a single number in a list

If I extend the problem to this: What would be the best algorithm for finding a number that occurs only once in a list which has all other numbers occurring exactly k times?

Does anyone have good answer?

for example, A = { 1, 2, 3, 4, 2, 3, 1, 2, 1, 3 }, in this case, k = 3. How can I get the single number "4" in O(n) time and the space complexity is O(1)?

Answer 1

If every element in the array is less n and greater than 0.
Let the array be a, traverse the array for each a[i] add n to a[(a[i])%(n)].
Now traverse the array again, the position at which a[i] is less than 2*n and greater than n (assuming 1 based index) is the answer.

This method won't work if at least on element is greater than n. In that case you have to use method suggested by Jayram

EDIT:
To retrieve the array just apply mod n to every element in the array

Answer 2

This can be solved in given with your constraints if the numbers other than lonely number are occurring exactly in even count (i.e. 2, 4, 6, 8...) by doing the XOR operation on all the numbers. But other than this in space complexity O(1) its just teasing me.

If other than your given constraints you could use these approaches to solve this.

1. Sort the numbers and have a current variable to get the count of current number. If it is greater than 1 then go to next number and so on. Space O(1)...Time O(nlogn)
2. Use O(n) extra memory to count the occurrences of each number. Time O(n)...Space O(n)