Amazon Interview Question
Country: United States
g233007 Solution is perfect and will work. Let me explain the algorithm for people who are not so privileged (or you can say proficient) with Binary numbers.
A general rule of thumb when ever you are asked for log(n) solution think in terms of binary trees, recursion with problem divided into two half problems in each step.
Now consider a Binary tree.
At root level (level = 0), Number of node = 0. Assign it a number 0.
At level 1, Number of nodes = 2, assign it numbers 1 and 2
At level 2, Number of nodes = 4, assign it numbers 3, 4, 5, 6
At level 3, Number of nodes = 8, assign it numbers 7, 8 ,9, 10, 11, 12, 13, 14
Tree should look like following:
0 (0)
___________|__________
| |
1 (01) 2 (10)
_____|_____ _____|_____
| | | |
3(11) 4(100) 5(101) 6(110)
___|___ ____|____ _____|_____ _____|_____
| | | | | | | |
7(111) 8(1000) 9(1001) 10(1010) 13(1101) 14 (1110)
Number of digit at level 0 = 0
Number of digit at level 1 = 2
Number of digit at level 2 = 7
Number of digits at level 3 = 19
Number of digits at level 4 = 47
Number of digits at level 5 = 111
If you stare at them hard enough you will see a pattern.
Lets denote the number of digits at Level L by N(L)
Let number of nodes at Level L X
Then N(L) = (N(L-1) + 1 ) + (N(L - 1) + (X / 2))
Lets solve the above eq for Level 5:
N(5) = (N(4) + 1) + (N(4) + 16) = 47 + 1 + 17 + 16 = 111.
Thats you algorithm in Log(n) time
I still have something in mind. For a tree of n nodes , the depth is Log(n).So with the algorithms mentioned here, you can only calculate the results to the Log(n)-1 level. As a result, for the leaves in the last level , you still have to use the common idea to calculate the bits. which may still be a result of n*log(n). I don't know whether it is right.
I still have something in mind. For a tree of n nodes , the depth is Log(n).So with the algorithms mentioned here, you can only calculate the results to the Log(n)-1 level. As a result, for the leaves in the last level , you still have to use the common idea to calculate the bits. which may still be a result of n*log(n). I don't know whether it is right.
Heres a log2(n) solution. Loop iterates log2(n) times.
correct me if i am wrong ..work for signed 4 bytes integer
int fun(int n)
{
int k=(int)log2(n)+1;
int mul=2;
int sum=0;
int x,y;
for(int i=1;i<=k;i++)
{
x=(n+1)/mul;
y=((n+1)-(x*mul))>(mul>>1)?((n+1)-(x*mul))-(mul>>1):0;
sum+=x*(mul/2)+y;
mul=mul<<1;
}
return sum;
}
If you're not allowed to use log2n() function, the only way to compute that is using this (from graphics.standford.edu/~seander/bithacks.html):
unsigned int v; // 32-bit value to find the log2 of
const unsigned int b[] = {0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000};
const unsigned int S[] = {1, 2, 4, 8, 16};
int i;
register unsigned int r = 0; // result of log2(v) will go here
for (i = 4; i >= 0; i--) // unroll for speed...
{
if (v & b[i])
{
v >>= S[i];
r |= S[i];
}
}
k = r + 1;
So, technically this algorithm is O(2log(n)).
I'm not sure about the logN solution, but there is a constant time solution (that I've written and tested):
The idea is to observe the pattern in the bits: the LSB goes like 0, 1, 0, 1... the LSB+1 bit goes like 0,0,1,1,...
From this pattern, you can construct a function that can calculate the sum of bits up to that N number (hence it will calculate 32 bits no matter what N is -> constant time).
If you program in Java, watch out that this dumb environment will do nothing to a number (instead of making it 0) if you call NUM >>> 32 :) I presume it' a bug not a feature :)
#include<stdio.h>
#include<conio.h>
#include<math.h>
main()
{
int num;
int count_prev,count_current,count_final;
count_prev = count_current = count_final = 0;
scanf("%d",&num);
printf("%d\n",num);
int temp = num;
while (temp > 0)
{
temp = reduced(temp,&count_prev,&count_current);
}
printf("\n total no of 1's is %d",count_current);
getch();
}
int reduced(int num,int *count_prev,int *count_current)
{
int i = 0;
int small =num;
while(num != 0)
{
if(num & 0xFFFFFFFF)
{
i++;
}
num = num>>1;
}
int temp = small - pow(2,i-1) + 1;
int num_next,num_prev;
num_next = pow(2,i-1)*i;
num_prev = pow(2,i-2)*(i-1);
*count_prev = num_prev + temp;
*count_current = *count_prev + *count_current;
temp--;
return temp;
}
This should work if you're passed in an 32-bit integer. If you want to use for 64-bit integers, change the function accordingly!
unsigned int bitcount(unsigned int v)
{
unsigned int count = 0;
for (v; v != 0; v>>=1)
{
count += (v & 1);
}
return count;
}
public int Calcbits(int num)
{
if (num == 0)
return 0;
int bits = 0;
while (num > 0)
{
if (num % 2 != 0)
bits++;
num = num / 2;
}
return bits;
}
public int TotalBits(int number)
{
if (number == 0)
return 0;
else
{
int initialBits = Calcbits(number);
return (initialBits + TotalBits(number - 1));
}
}
public int Calcbits(int num)
{
if (num == 0)
return 0;
int bits = 0;
while (num > 0)
{
if (num % 2 != 0)
bits++;
num = num / 2;
}
return bits;
}
public int TotalBits(int number)
{
if (number == 0)
return 0;
else
{
int initialBits = Calcbits(number);
return (initialBits + TotalBits(number - 1));
}
}
public int Calcbits(int num)
{
if (num == 0)
return 0;
int bits = 0;
while (num > 0)
{
if (num % 2 != 0)
bits++;
num = num / 2;
}
return bits;
}
public int TotalBits(int number)
{
if (number == 0)
return 0;
else
{
int initialBits = Calcbits(number);
return (initialBits + TotalBits(number - 1));
}
}
log(n) solution, n is the number of bit of an integer. For int32 n=32.
The basic algorithm is divide-and-conquer.
int Calculate(int x)
{
if(x==0) return 0;
x=(x&0x55555555)+((x>>1)&0x55555555);
x=(x&0x33333333)+((x>>2)&0x33333333);
x=(x&0x0f0f0f0f)+((x>>4)&0x0f0f0f0f);
x=(x&0x00ff00ff)+((x>>8)&0x00ff00ff);
x=(x&0x0000ffff)+((x>>16)&0x0000ffff);
return x;
}
The binary form of hexadecimal numbers above:
0x55555555=01010101010101010101010101010101
0x33333333=00110011001100110011001100110011
0x0f0f0f0f=00001111000011110000111100001111
0x00ff00ff=00000000111111110000000011111111
0x0000ffff=00000000000000001111111111111111
If you understand the usage of these 5 numbers above, the algorithm is easy to understand too.
/**
* Time: O( lg(32) )
*/
int numOfBits(int value){
int res = value;
res = (res & 0x55555555) + ((res>>1) & 0x55555555); // 1bit + 1bit
res = (res & 0x33333333 ) + ((res>>2) & 0x33333333); // 2bits + 2bits
res = (res & 0x0F0F0F0F) + ((res>>4) & 0x0F0F0F0F); // 4bits + 4bits
res = (res & 0x00FF00FF) + ((res>>8) & 0x00FF00FF); // 8bits + 8bits
res = (res & 0x0000FFFF) + ((res>>16) & 0x0000FFFF); // 16bits + 16bits
return res;
}
I think its just a tricky one.Every one knows the answer. :)
say : n= 8
8/2 = 4, 8%2 = 0
4/2 = 2 ,4%2=0
2/2=1, 2%2 =0
O(lg n)
#include <stdio.h>
#include <math.h>
extern float log2f(float x);
int BitsUptoN (int N)
{
int TwoPower_absLog2N;
if(N == 1) {
return 1;
}
else {
TwoPower_absLog2N = pow (2, (int) fabsf (log2f (N*1.0)));
if(TwoPower_absLog2N == N) {
return 1 + BitsUptoN (N-1);
}
else {
return BitsUptoN (TwoPower_absLog2N) + (N - TwoPower_absLog2N) + BitsUptoN (N - TwoPower_absLog2N);
}
}
}
int main (int argc, char **argv)
{
printf ("Bits up to %d - %d\n", atoi (argv[1]), BitsUptoN (atoi(argv[1])));
return 0;
}
There is a very good explanation for this problem on stackoverflow:
just search : finding the total number of set bits from 1 to n
consider the below:
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
If you want to find total number of set bits from 1 to say 14 (1110)
Few Observations:
1) 0th bit (LSB) 1 bit appears once every two bit (see vertically) so number of set bits = n/2 +(1 if n's 0th bit is 1 else 0)
2)1st bit : 2 consecutive 1s appear every four bits (see 1st bit vertically along all numbers)
number of set bits in 1st bit position = (n/4 *2) + 1 (since 1st bit is a set, else 0)
3)2nd bit: 4 consecutive 1s appear every 8 bits ( this one is a bit tricky)
number of set bits in 2nd position = (n/8*4 )+ 1( since 2nd bit is set, else 0) + ((n%8)%(8/2))
the last term is to include the number of 1s that were outside first (n/8) group of bits (14/8 =1 considers only 1 group ie. 4 set bits in 8 bits. we need to include 1s found in last 14-8 = 6 bits)
4)3rd bit: 8 consecutive 1s appear every 16 bits (similar to above)
number of set bits in 3rd position = (n/16*8)+1(since 3rd bit is set, else 0)+ ((n%16)%(16/2))
so we do O(1) calculation for each bit of a number n.
a number contains log2(n) bits. so when we iterate the above for all positions of n and add all the number of set bits at each step, we get the answer in O(logn) steps
How about something better than O(log(n)) :) (I am guessing mine is log(log(n)) ? This is more of a math problem.
public int F(int n)
{
if (n == 0)
return 0;
int bits = (int)Math.Log(n, 2); //This will be the bit count
int count = (int) (Math.Pow(2,bits-1)) * (bits) + 1; //The count value of the largest power of 2 closest to the number n. This is known to us (how I wont explain :P)
int balance = n - (int)Math.Pow(2, bits); //Balance amount. For example: If n=18, balance=2;
return count + balance + F(balance); //I add the balance because, the leading 1 is always going to contribute. Now recurse on the balance amount.
}
Alignment is screwed up.. Hold on...
public int F(int n)
{
if (n == 0)
return 0;
//This will be the bit count
int bits = (int)Math.Log(n, 2);
//The count value of the largest power of 2 closest to the number n.
//This is known to us (how I wont explain :P)
int count = (int)(Math.Pow(2, bits - 1)) * (bits) + 1;
//Balance amount. For example: If n=18, balance=2;
int balance = n - (int)Math.Pow(2, bits);
//I add the balance because, the leading 1 is always going to contribute.
//Now recurse on the balance amount.
return count + balance + F(balance);
}
Here is my code
Solution is if n is square of 2 then f(n) = f(n/2*2 -1) + (n - n/2)
if n is not square of 2 then f(n) = f(n&n-1) + (f(n-(n&n-1) + (n - (n&(n-1))))
n&n-1 is square of 2 which is closest but smaller than n
If you use Hashtable to track already calculated result like cache then it's gonna be faster.
int getNumberOf1 (int num) {
if (num == 1) {
System.out.println("f(1) = 1");
return 1;
}
int n = (num & num-1);
if (n == 0) {
int result = (getNumberOf1(num/2) * 2 -1) + (num-(num/2));
System.out.println("f("+ num +") = " + result);
return result;
}
int result = getNumberOf1(n) + getNumberOf1(num -n) + (num - n);
System.out.println("f("+ num +") = " + result);
return result;
}
public int Calcbits(int num)
{
if (num == 0)
return 0;
int bits = 0;
while (num > 0)
{
if (num % 2 != 0)
bits++;
num = num / 2;
}
return bits;
}
public int TotalBits(int number)
{
if (number == 0)
return 0;
else
{
int initialBits = Calcbits(number);
return (initialBits + TotalBits(number - 1));
}
}
Sorry I misunderstood the question. Here is a log(n) solution for calculating the number of 1s from 1 to n:
We know that for every number n: n*2==n<<1. Thus for every even number n the number of 1s is the same as n/2 while for odd number n the number of 1s is just one more that that of n/2. We assume that the number of 1s in number n is F(n) so we have:
F(n)=F(n/2) for even number
F(n)=F(n/2)+1 for odd number.
According to this we can build a complete tree like this:
1 / \ / \ 2 3 / \ / \ 4 5 6 7 / \ / \ / \ / \ 8 9 10 11 12 13 14 15In this tree every for every node, we assume G(node)= number of 1s of node.value, then we have G(node.lchild)=G(node)*2, G(node.rchild)=G(node)*2+1. If we can calculate the number of 1s in one level's numbers in O(1) then we can achieve O(logn) for this question.
Due to G(node.lchild)=G(node)*2, G(node.rchild)=G(node)*2+1, we can prove that for each level, G(nodes in nextLevel)=G(nodes in this level)*2+t, having t be the number of nodes in this level. Now we can calculate G(level) in O(1) and calculate F(n=exp(2,k)-1) in O(log n) using the conclution above.
There is still one question: how about n!=exp(2,k)-1? Actually as we've already had G(nodes concerned) and t, we can get G(first half of nodes concerend)=G(second half of nodes concerned)+t/2; now t is the number of nodes that concerned; we start to concern with the whole level. It's easy to prove. Thus we can use this to calculate.
Take n=10 for example:
The tree is like
1 / \ / \ 2 3 / \ / \ 4 5 6 7 / \ / \ / \ / \ 8 9 10 11 12 13 14 15First we calculate G(nodes in this level) for every level, so we have
1---------------->G=1, t=1 / \ / \ 2 3---------->G=1*2+1=3, t=2 / \ / \ 4 5 6 7------->G=3*2+2=8, t=4 / \ / \ / \ / \ 8 9 10 11 12 13 14 15----->G=8*2+4=20, t=8We found for every level t=t*2 and calculate the number of 1s in first 3 level is 1+3+8=12. For level 4, we just need G(8,9,10,11). We already new that G(8 to 15)=G(8 to 11)+G(12 to 15) and G(8 to 11)=G(12 to 15)-t/2 (t=8). So we can calculate G(8 to 11)=(G(8 to 15)-4)/2=20-4/2=8.
- g233007 March 22, 2012Now we have got G(8 to 11)=8, we do the routin again and get G(8,9)=(G(8 to 11)-2)/2=3 and G(10,11)=(G(8 to 11)-2)/2+2=(G(8 to 11)+2)/2=5.Do the routine again we have G(10)=(5-1)/2=2, G(11)=(5+1)/2=3.
Thus F(10)=G(1)+G(2,3)+G(4 to 7)+G(8,9)+G(10)=17.
In this solution the time complexity is O(2logn).
Later I will give a code in C# if any one need.