Google Interview Question
Software Engineer / DevelopersCountry: United States
Haha that's cool!!! Everyone should +1.
That might let 0 through, so you might need to do it like this:
bool isPowerof4(unsigned int n) {
return ( n !=0U && (n & 0xAAAAAAAAU) == 0 && (n&(n-1)) == 0);
}
It is O(lglgn) n=the number
Constant time function is element of O(lglgn) class of functions.
Do we want theta( lglgn ) ?
Just do two level tower of powers 4^(2^i) <--- that's 2 levels of left shifting
Loop on i until some 4^(2^i) is greater than your number (you can make this platform independent, and even work on mythical infinite sized integers)
.
Then you know the number is between 4^(2^(i-1)) and 4^(2^i) for last seen i
{Except some boundary case(s)}
Now binary search on that range. Lower = 2^(i-1), Upper= 2^i
We don't have to keep calculating powers throughout all this, as we can adjust previous powers whenever we have a loop.
And every ^ you see above is some kind of shifting.
First check whether number is power of 2:
x = 2^k
x == 0...010...0
x-1 == 0...001...1
x & (x-1) == 0...000...0
x != 2^k
x == 0...1...010...0
x-1 == 0...1...001...1
x & (x-1) == 0...1...000...0
If it is not power of 2 - then it is not power of 4.
If it power of 2 - then it have exactly one 1 in binary record.
1 = 000000001
4 = 000000100
16 = 000010000
64 = 001000000
256 = 100000000
If it is power of 4 - position of this single 1 will be odd.
bool isPowerOfTwo = x && !(x & (x - 1));
//101010100 = 0x5...554
int mask = 0x5...554; //(or 0x5...555 is 1 should be included as 4^0)
return isPowerOfTwo && (x & mask );
Similar to joe_kidd's solution, the pattern we want to find is that there is exactly only one '1' in an odd position of the bit representation of the number.
Instead of looping and checking all possible numbers, which gives O(log n) runtime, we can do binary selection to further optimize it to O(log log n).
The idea is to break the number into 2 parts, and do zero-check on both parts. go to the part that is non-zero, until you find a '1' and check if its position is on an odd index. Go to the original number, flip the 1 on the index you found, and do zero-check of the flipped number.
PS: 1 is also counted as power of 4, I assume
Is this really O(lglgn)?
"Do zero check on both parts" ? Except for the case when the parts are perfectly aligned and CPU accessible objects (e.g., int, short, char), how would you do that part when you are dealing with parts that are < 1byte in size?
Pseudocode please?
Why not (for sizeof(int) independent alg.) just sweep through the bytes and do "zero check" and "odd 1 set check" byte by byte?
Oh this one looked cool.
Write a multibyte example on paper, then you get the idea to use a lookup table:
Note: 4^i = (2^2)^i = 2^(2i)
Also, on paper you see that any integer is a power of 4 precisely when:
1) One of it's bytes is a power of 4
2) All other bytes are fully 0
bool LUT[1U<<8]; //look up: is a byte sized integer a power of 4?
//initialize: LUT[1U] = LUT[1U<<2] = LUT[1U<<4] = LUT[1U<<6] = true;
bool ispower4 ( uint x )
{
union {
uint whole;
unsigned char part[sizeof(uint)];
} var;
bool bytecheck = false; //whether we've seen a byte in the integer that's power of 4
int zerobytes = 0; //count number of all-0 bytes in integer
int i;
var.whole=x;
for(i=0; i < sizeof(uint); i++)
{
if( LUT[var.part[i]] ) bytecheck=true; //i-th byte is a power of 4
else if (var.part[i] == 0x0 ) zerobytes++; //i-th byte is all 0s
}
//all bytes are totally 0s, except 1 byte that is power of 4
return ( zerobytes == sizeof(uint)-1 && bytecheck );
}
Or since LUT is "sparse" you can turn it into a quick function too.
bool LUT[1U << 8]; //look up: is a byte sized integer a power of 4?
//initialize: LUT[1U] = LUT[1U<<2] = LUT[1U<<4] = LUT[1U<<6] = true;
bool ispower4 ( uint x )
{
union {
uint whole;
unsigned char part[sizeof(uint)];
} var;
bool bytecheck = false; //whether we've seen a powerof4 byte
int zerobytes = 0; //count number of all-0 bytes in integer
int i;
var.whole=x;
for(i=0; i < sizeof(uint); i++)
{
if( LUT[var.part[i]] ) bytecheck=true; //i-th byte is a power of 4
else if (var.part[i] == 0x0 ) zerobytes++; //i-th byte is all 0s
}
//all bytes are totally 0s, except 1 byte that is power of 4
return ( zerobytes == sizeof(uint)-1 && bytecheck );
}
or use this instead of LUT (calling it LUT(x) for convenience ) if you don't mind the extra time:
bool LUT(unsigned char b) //returns true if byte "b" is a power of 4
return( b== 1U ||b == 1U<<2 || b==1U<<4 || b==1U<<6 );
We list the following sequence:
a_0 = 4
a_1 = 4^{a_1}
a_2=4^{a_2}
...
a_n=4^{a_{n-1}}
We can find the range the integer N belongs to. say a_i, and a_{i+1}.
Now, do the previous calculation, and multiply a_i each time.
We recursively do the previous steps. Until we n=a^k or n is between a^k and a^k+1.
Here.
- Forest October 21, 2013