Find single number!!

Given an array containing integers, where each number occurs three times except for one number which occurs only once, find the number which occurs only once.
Couldnt think of a way to use XOR for this. XOR works fine when all numbers appear twice and only one of them appears once.
But we can still use some bit magic for this question.
Lets consider ith bit of all numbers. If we count the total number of one's in the ith bit for all numbers and later divide this number by 3, we can get the ith bit of the desired number. So lets say if we have total of 7 elements for eg: {10, 13, 10, 13, 10, 4, 13}. Now if we count total number of ones for LSB in the whole array, we will get 3(for 3 13s, for every other number LSB is 0). Now if we find remainder of the count when divided by 3, we will get the LSB of the desired number. Why? Because every other number appears three times, hence all other ones will appear three times and when taking a remainder will cancel out.
We can do the same thing for all 32 bits :). Below is the code.

int singleNumber(int A[], int n) {
    int num = 0;
    int temp = 0;
    for(int i = 0; i < 32; i++)
    {
        for(int j = 0; j < n; j ++)
        {
            if((A[j] >> i) & 1)
                temp ++;
        }
        temp = temp %3;
        num = num | (temp<<i);
        temp = 0;
    }
    return num;
}

Unsolved!!

Here are some questions which I will try in coming days and have not solved them. Will take them of this list as I solve each one of them :).

• Given a linked list structure where every node represents a linked list and contains two pointers of its type: (i) pointer to next node in the main list. (ii) pointer to a linked list where this node is the head. Write a function to flatten the list into a single linked list.


• You are given an array of integers A[1..n] and a maximum sliding window of size w. Output an array B where B[i] is the maximum in A[i, i+w-1].


• You have an array of 0s and 1s and you want to output all the intervals (i, j) where the number of 0s and numbers of 1s are equal.


• Given a binary matrix of NxN of integers ,return only unique rows of binary arrays eg: 01001 10110 01001 11100 ans: 01001 10110 11100


• Given an array of integers like ar[]= {1,3,2,4,5,4,2}. Create another array ar_low[] such that ar_low[i] = # of elements lower than or equal to ar[i] in ar[i+1:n-1]. So the output for above array should be {0,2,1,2,2,1,0}