dreamCoder
BAN USERint count=0;
while(n>0){
//n-1 will set the right most set bit to zero. AND with the same number will sustain the remaining bits
n&=n-1;
count++;
}
the value of count gives the number of count bits.
When one number is missing:
find the sum of numbers from 1 to n using the formula... n(n+1)/2. Then the difference between the actual sum and the calculated sum is the missing number
when two numbers are missing:
like above, get equation for a+b=x -------- equation 1
now sum the square the numbers using n(n+1)(2n+1)/6 and then calculate actual value for numbers from 1 to n. Now the difference is in the form of equation a^2 + b ^2 = y ------ equation 2
From these two equations, you can solve for a and b.
Dates and times can be well sorted using radix sort, whose time complexity is O(K*n) where K is maximum length of element of input string. Since K is less and fixed, we can sort the given array using almost O(n) time rather than merge sort. The rest solution is same as what I think.
- dreamCoder June 05, 2012The worst case scenario for any sorting algo is not nlogn. See this page wikipedia/Radix_sort about Radix sort and you will know what my suggested solution
- dreamCoder June 03, 2012How about sorting the given array using radix sort (length of each input element is just 1, so it just takes O(n) time). And then walk through the array and return the first unique element?
- dreamCoder June 03, 2012
Suppose, the number n is 7 (in binary 0111) and n-1 will be 6 (0110)
- dreamCoder September 04, 2012n&=n-1 in the first iteration will be 6 (count incremented to 1)
in the second iteration it will be (0100) count incremented to 2 and in the third iteration n will be 0000 and count incremented to 3 and the loop exits as n will go less than 0 after this. Now, the count has the number of bits set.