Amazon Interview Question Software Engineer / Developers
Country: India
Interview Type: In-Person
just 1 small correction.
33+
9+13 +2
=57. and not56. just a minor calculation overlook. but once again great logic
thanks Sonu.
Actually the answer is 56 and not 57. I forgot to highlight the part (2) where it should be 8 + 13 and not 9. The delta must be relative to the current value we wish to right as a power of 2.
Hence it is 33 + 8 + 13 + 2 = 56.
sorry to ask. i didn't get this solution. Could you please explain the equation a littile bit more
Well the equation can be easily observed from the way we write binaries.
So if N = 4, then its 000,001,010,011,100 with number of 1s = 5. which is [2^(2-1) * 2] + 1 = 5.
Try the same for N = 8. You will get 13. 2^(3-1) * 3 + 1 = 13.
Now say I N = 10, now we know that it has to be more than 5 1s and less than 13 1s. so if you write it as 2^3 + 2^1 we will be able to solve this mathematically. 2^3 = 13 ones and 2^1 will be 1 1s. But since 10 > 8 the MSB for 8 will have 1 set for the value > 8 right? so after 1000 we have 1001 and 1010. Hence we gotta account for those two ones too.
the formula applied to part (2) is for 2^1 right? we would need only 2 bits to write that. However, since its greater than 8 we gotta account for the MSB set which in this case is 2.
Hence it is 13 + 2(MSB bits) + 1(number of 1s for N = 2^1) = 16 which is the number of 1s for 10.
correction - delete("Now say I N = 10, now we know that it has to be more than 5 1s and less than 13 1s.") :P
int CountSetBits(int x)
{
int count = 0;
while (x != 0)
{
x = x & (x-1);
count++;
}
return count;
}
int main()
{
int totalBits = 0, n = 6;
for(int i = 1; i<= n; i++)
{
totalBits += CountSetBits(i);
}
cout<<totalBits;
}
This bit counting is rather interesting
Perhaps
unsigned int bit_count(unsigned int x) {
unsigned int count = 0;
while (x) {
count += x & 1;
x >>= 1;
}
return count;
}
is a better one (a bit less operation performed).
But the real issue is that your algorithm is calling the bit counting N times, so it cannot be O(log N) - it is O(N)
To have a O(log N) algorithm you should think about a tree and not traversing but descending into it from the root at some "good" direction. This sounds crazy to descend from the root but trees in computers grow upside down :)
The immediate above method (x>>1) is not better one.. Its order is order of no. of bits in binary representation of x. if we will use x=x&(x-1) then its order will b order of no. of 1s in binary representation which is always <= order of no. of bits in binary representation. So 1st approach is better.
ex:
x=513
1st approach( x&(x-1)) will calculate total no of 1 in 2 step... i.e order of no. of 1 in x.
2nd approach will calculate in 10 steps.. as 10 bits r required 2 represent 513
It seems the solution could be:
Let high_bit - the highest bit in the number (from 0).
First calculate the function p(i) - answer for 2^i - 1.
p(i) = 2 * p(i-1) + (1<<(i-1))
p(0) = 0
We will do it from 1 to high_bit.
Now we can find the answer:
f(n) = (n XOR (1 << (high_bit - 1))) + p(high_bit) + f(n XOR (1 << (high_bit - 1)))
it is O(logN)
I didnt understand the above logic... can anyone explain?
what is i in this case and what is the logic behind it?
@Alex
Could you please explain the logic for n = 15?
Also I didnt get why the complexity is O(log N) in your case
ok.
First we need to find the highest bit in the n. We can do in in O(logN) time.
int n2 = n;
int ret = 0;
for (int i = 0; n2; ++i) {
if (n2 & (1 << i)) {
n2 ^= (1 << i);
ret = i;
}
}
Second.
Let's understand what is p.
p(i) is the answer for numbers that looks like 2^i - 1 or it means all 1s in binary representation.
p(i) = p(i-1) * 2 (it is because we will calculate the all 1s besides the first one) and + (1 << (i-1)) the first one will be from 10000..0 to 111..1.
--------------------------------
Now the f function.
Let the number looks like 10101.
We can say that the first 1 will be 101 + 1 times (from 000 to 101) (6 times).
so the first 1 will be n XOR (1 << (highest_bit - 1)). (I assume that we index the bits from 0).
then. the numbers until our number are 0, 1, 10, ... , 1111, 10000, ..., 10101. So from 0 to 1111 we know the anser - it is p(high_bit).
And now we need to find the answer for 10000 to 10101, and we have calculate the first 1. So we can skip it. it is f(101). or f(n XOR (1 << (high_bit - 1))) in the formula.
--------------------------------
Every calculation will takes only O(logN) because we just go through the bits of the number.
-----------------------------------
For 15 - 1111 - it will be
p(0) = 0, p(1) = 1, p(2) = 4, p(3) = 12.
f(1111) = p(3) + 1000 + f(111) = 12 + 8 + f(111) = 20 + f(111) = 32
f(111) = p(2) + 100 + f(11) = 8 + f(11) = 12
f(11) = p(1) + 10 + f(1) = 3 + f(1) = 4
f(1) = 1
log(n) time one number's bit counting will take and then we have to count the number of 1's for 1 to n number, which will lead to o(NlogN).
@jain . we can coun the number of set bits in O(1) for one number , but we have n numbers at-least it takes in O(N) , hows the interviewer asking the soln for logn , no significance ?
suppose no is 14.
Represent number from 0 to 14(total count = 15), Run the below algo for all bits in number i.e (1110).
lowest bit will alternate b/w 0&1 so no of ones from lowest bit is - 15/2 + 15%2 = 7+1 =8,
2nd lowest bit will have first two zeros and then two ones, so no of ones from 2nd lowest bit is 15/4*2(for 4 bits we have two ones) + 15%4-(4/2, initial two bits will be zero) = 6+1 = 7
3rd lowest bit will have first 4 zeros and then 4 ones, so no of ones from 3rd lowest bit is 15/8*4 + 15%8-(8/2) = 4 + 3 =7
4th lowest bit will have first 8 zeros and then 8 ones, so no of ones from 4rd lowest bit is 15/16*8 + 15%16-(16/2) = 0 + 7 =7
total number of ones = 28
int count1s(int n) {
if (n < 1) {
cout << "error" << endl;
return -1;
} else if (n == 1) {
return 1;
}
int t = n;
int cnt = 0;
int acc = 0;
int i = 2;
while (t > 0) {
cnt += ((n - acc) / i) * (i / 2);
int rem = (n - acc) % i;
if (rem > i / 2) {
cnt += i / 2;
} else {
cnt += rem;
}
acc += i / 2;
i *= 2;
t >>= 1;
}
return cnt;
}
A more mathematical solution to get O(logN) could be as follows:
- keshy December 14, 2011The equation for the number of ones for N where N = 2^n
is
[(2^(n-1) * n) + 1] where n >= 1.
So if we have a number say 25, we can break it up as 2^4 + 2^3 + 2^0. Now before applying this formula we must take care of the MSB in the difference. To elaborate:
1. Apply formula for 16 (i.e. 2^4 in the above break up). (2^3*4 + 1) We get 33 1s (which is true).
2. For the remaining 9, all numbers would have its MSB set to 1 (logical) so we should take that into account. Hence here we would have 9(from the MSB) + (from formula for number 8) (2^2*3 + 1) = 9 + 13 = 21.
3. Performing the same operation for the last set, we have (from the difference with respect to the MSB) 1 + 1(for 1 only one bit is set) = 2.
Add (1) + (2) + (3) = 56 which is the number of 1s for 25.
Since we can easily find out the number of 1s for a power of 2 in O(1) this problem now reduces to a binary search problem.