Amazon Interview Question
InternsCountry: United States
Interview Type: Phone Interview
n>>1 Is it a left shift or right?
>> Indicates the bits are to be shifted to the right.
But in your code if there is a number with no zeros even then you would iterate over the entire string which is not efficient. Rather if you mask all your 1's and the if number masked number is 0 then clearly it contains no 0's so you don't need to check the entire string.
Sorry, it was right shift, I have changed this. Shalini can you please elaborate through code. Thanks!
It can be found by finding number of times 5 appears in the factors, since 5 *2 always gives one zero. So to proceed, try to find maximum value of n in 5^n in case where number is divisible.
Ex: 100 => 5^2 , therefore n = 2 so maximum trailing zeros are 2.
I would it by counting the number of ones and subtracting from sizeof(integer).
Assume input = v
for (int c =0; v; v>>1)
c+= (v&1)
At end 'c' will contain number of ones in number
So number of zeros is:
NoOfZeros = sizeof(int) *8 - c
(8= number of bits in byte. I guess this is an assumption so the code may not be fully portable)
So final code
int NoOfZeros(int v)
{
for (int c = 0; v; v>>1)
c+= (v&1);
return sizeof(int)*8-c;
}
For calculating the number of zeroes in the given integer we will have to check for n&1 == 0 every time after shifting the bit to the right by 1 and then, if found increment the count and hence, return the count when all the bits have been traversed.
Implementation:
#include<bits/stdc++.h>
using namespace std;
int countno(int r){
//int r = ~n;
int count = 0;
while(r > 0){
if((r&1) == 0)
count++;
r = r>>1;
}
return count;
}
int main(){
int n;
n = 2;
cout<<countno(n)<<endl;
return 0;
}
for(int i = 0; i < sizeOf(int) * 8 ; i++)
{
x & x-1
count++;
}
Answer = sizeOf(int)*8 - count
Basically number of 1's minus the total possible binary digits.
<<<
for(int i = 0; i < sizeOf(int) * 8 ; i++)
{
x & x-1
count++;
}
Answer = sizeOf(int)*8 - count
Basically number of 1's minus the total possible binary digits.
>>>
count will always be equal to sizeof(int)*8 so the code will always return zero
Is it to find the zeros in binary format?
- Punit Jain March 29, 2012If yes then:
count = 0
while (n>0) {
count = count + !(n&1)
n=n>>1 //Right shift by 1
}
return count
To find in decimal format the
count = 0
while (n>0) {
count = count + (n%10>0 ? 0 : 1)
n = n/10;
}
return count