Achieve Internet Interview Question Analysts
Team: artificial intelligence team
Country: United States
Interview Type: Written Test
Anon:
for 3 will not have any 0. binary of 3 = 11.
As per Sunny we will prepend with 0 means it will become 011. Now we will start from right and search for 1st 0 which will have 1 before that. we will get 0 at 3rd position. Then we will swap 3rd position number with 2nd position number so binary representation will be 101 i.e. 5.
you solution canot get the right answer in some case.
for example, N=(10110)2, in your case, you will get (11010)2, am i right? but the right answer is (11001)2, which is smaller than (11010)2.
so your step (3) of flip is just not enough, the right way is set the 0 you find in (2) to 1, and rearrange the 1's on the right side of this 0 to the lowest positions if there exist.
I will still use N=(10110)2 to demonstrate that. the 0 you find at (2) is at pos 3(pos 0 is the rightmost bit), so you flip it to 1, and there are 2-1=1(you already use one of it) 1's left on the right side of pos 3, so you set this 1 to the pos 0,then we'll get (11001)2 as the right answer.
you can use bit operation to solve it, assume the pos you find zero is i, there are j 1's on rightside, then the answer is: res = (N&(~(1<<i-1)))|(1<<(j-1)-1)
@busycai - good catch on the trailing zeroes case. Yes after the flip, we also need to rearrange all those ones to lowest positions. Multiple ways to do that, but I might jsut reverse the substring before the bit we are switching since that substring should consist of 1s followed by one more 0s.
Written in C++.
Input:
2
3
7
Output:
5
11
Code:
#include <iostream>
int count_bits(int n) {
int i = 0;
while (n > 0) {
if (n & 1)
i++;
n >>= 1;
}
return i;
}
int smallest_greater_same_weight(int n) {
int i = count_bits(n);
int m = n;
for (;;) {
if (i == count_bits(++m))
break;
}
return m;
}
int main() {
int ntests;
std::cin >> ntests;
if (std::cin.fail())
return 1;
while (ntests--) {
int n;
std::cin >> n;
if (std::cin.fail())
return 1;
std::cout << smallest_greater_same_weight(n) << std::endl;
}
return 0;
}
I think your program will return 5 for input 5. The result should be greater than the original number.
int flag = 0;
int shift = 0;
while(true)
{
if(n & 1 == 0 && flag == 0)
continue;
if(n & 1 && flag == 0)
{
flag = 1;
}
if(n & 1 == 0 && flag == 1) //this means we have a bit 0 before bit 1
{
we exchange the bit 0 and bit 1(there are nearby bits), then we got the right number like: 1101 --> 1110; 0111->1011; 10101-->10110; 10100-->11000
}
n >>= 1;
shift += 1;
}
/*
* binweight: The key is to find a 01 sequence. Flipping that to
* 10 will get us to the next integer of the same weight. We need
* to consider the corner case where we had one or more zeroes in
* the least significant part and a 11 more significant to that.
* The least significant 1 needs to be right shifted as far as it
* will go. Next for 0110 is 1001 not 1010.
*/
unsigned short
binweight(unsigned short i)
{
if (i >= (1<<15))
return 0; /* next requires more than 16 bits */
if (i == 0)
return 0; /* no set bits */
int ls0pos = 1; /* LSb that is still zero */
for (unsigned short shift = 1; shift < (1<<15); shift <<= 1) {
if ((i & shift) == 0)
continue;
unsigned short nextshift = shift << 1;
if ((i & nextshift) == 0) {
i |= nextshift;
i &= ~shift;
return i;
}
i &= ~shift;
i |= ls0pos;
ls0pos <<= 1;
}
assert(0);
}
Hi,
I tried to solve this problem in a different way. I think it’s a more general one. I've started with writing the binary weight for the 20 first integer numbers:
N binary N W
---------------------------
(0) 0000 0000 - 0
(1) 0000 0001 - 1
(2) 0000 0010 - 1
(3) 0000 0011 - 2
---------------------------
(4) 0000 0100 - 1
(5) 0000 0101 - 2
(6) 0000 0110 - 2
(7) 0000 0111 - 3
---------------------------
(8) 0000 1000 - 1
(9) 0000 1001 - 2
(10) 0000 1010 - 2
(11) 0000 1011 - 3
---------------------------
(12) 0000 1100 - 2
(13) 0000 1101 - 3
(14) 0000 1110 - 3
(15) 0000 1111 - 4
---------------------------
(16) 0001 0000 - 1
(17) 0001 0001 - 2
(18) 0001 0010 - 2
(19) 0001 0011 - 3
---------------------------
(20) 0001 0100 - 2
…
The immediate solution will be to have a program which defines a pre-programmed array containing the binary weights, where the index to this array is N. For a given N - we first find its weight W by A[N] . Then, we search for the same W in the array starting the search with index equal to N+1. This algorithm is very efficient since the array serves as a look-up table. But now I wanted to solve it without having the look-up table.
Writing the binary weights above, I've observed two things:
1. The binary weights are elements of a sequence. I mean - the math term of a sequence.
0, 1, 1, 2, 1, 2, 2, 3, …
The weights form an ordered list with a “pattern”. Writing the weights as quadruplets, we get:
0 1 1 2 1 2 2 3
1 2 2 3 2 3 3 4
1 2 2 3 2 3 3 4
…
The first element of each quadruplet is the lowest value in the 4-element group; the last element has the greater value; the two mid elements have the same value and the difference between the values of first- mid-last -elements is always 1 (of course, it’s due to the bits combinations!). And the sequence, in some way, has a repeated quadruplet and “an increasing by one” quadruplet.
2. I also noticed that to find the smallest integer greater than N - it depends if N is even, or an odd number. So I'm looking for two roles.
By the way, I think that if you apply the algorithm suggested in this conversation (the find & flip algorithm) for an even number, it doesn't work. It works only for odd numbers. For example, let’s check it for N=6. Applying the steps described, the result is 5 which is NOT the smallest integer greater than 6, like: 0110 --> 0101. The result should be 9 .
3. Unfortunately, I’m a little rusty in math (it has been a while since college graduation) and I couldn't write down the roles for an odd and even integer of the sequence. I goggled the subject to find out that:
This sequence is a known sequence that was researched; it’s documented in the “On-Line Encyclopedia of Integer Sequences” created by Neil Sloane (see wiki about On-Line_Encyclopedia_of_Integer_Sequences).
The sequence is cataloged as oeis.org/A000120.
The roles I was looking for are given by the formula (see A000120):
a(0) = 0, a(2*n) = a(n), a(2*n+1) = a(n) + 1.
Or
a(0) = 0, a(2^i) = 1; otherwise if n = 2^i + j with 0 < j < 2^i, a(n) = a(j) + 1.
4. Notes:
– For N even (N=2*n), use: a(2*n) = a(n);
– For N odd(N=2*n+1), use: a(2*n+1) = a(n) + 1
– Weight calculation is a recursive function. Calculate weight of N given, keeping the weights calculated for further calculations, especially weight of N which will be used in searching the smallest integer greater than N. Seems that it wasn't a bad idea at all to have a look-up table (or cache).
– Calculate weight for the next K integers, to find the smallest integer greater than N that has the same weight as of N (from index N+1 to N+K). What is K? K says how far we need to test the next elements. If you look at the sequence (see A000120), it’s clear that as N is bigger, K is also bigger. I can guess that the iteration step is N+1+j where j is: 0 < j < 2^i. But, I didn't check if it's correct.
I actually don't think this question is outside the realm of this website. It's a perfectly legitimate interview problem that falls within 30-45 min timeframe. As for whether I am helping someone do his homework, I actually don't care. Just want to practice on reasonable questions.
(1) Get the binary representations of N, and prepend it with a zero.
- Sunny December 10, 2013(2) Starting from least significant bit, look for the first zero bit that has a one bit before it.
(3) Flip the zero and one bit. Since we prepended the binary representation with a zero, we are guaranteed to find this pair of zero/one bit.