Microsoft Interview Question
Software Engineer / DevelopersFor the left neighbor:
int number = inputNumber;
int delta = 1, moves = 0;
bool neighborNotFound = false;
while ((number & 3) != 2) { // for right neighbor, change this line to
// (number & 3) != 1
number >>= 1;
delta <<= 1;
if (moves++ > 32) {
neighborNotFound = true;
break;
}
}
if (neighborNotFound)
cout << "no left neighbor"
else
cout << "left neighbor is " << inputNumber - delta << endl;
ps: right neighbor can be found in the similar manner. The basic idea is to find first 10(for left neighbor) and 01(for right neighbor) from the right end of the number's binary form.
Hi,
Can you please explain your algorithm in detail? I dont understand why it works.
Thanks
This does not work 100%. For 10001 (=17) the above will obtain 01001 (17-8 = 9), whereas the correct answer is 01100(=12). Once you have subtracted delta, all the 1s to the right needs to move the the left. This will make the difference between number and left neighbor the minimum.
Same for right neighbor. Try with 011100. After adding the delta, all 1's need to move to right most positions to make difference smallest.
class SameNumOfOnes
{
public SameNumOfOnes()
{
string inpStr;
while ((inpStr = ReadInt()) != "END")
{
if(!inpStr.Equals("Error"))
if (GetPrevNextSameOnes(long.Parse(inpStr)) < 0)
Console.WriteLine("Error");
}
}
private string ReadInt()
{
Console.Write("Enter an integer to convert to words (Enter 'END' to quit):");
long inpNum;
string inpStr;
try
{
inpStr = Console.ReadLine();
if (inpStr.Equals("END"))
return inpStr;
inpNum = long.Parse(inpStr);
return inpStr;
}
catch (FormatException ex)
{
Console.WriteLine("Entered an invalid integer!!!. -- " + ex.Message );
return "Error";
}
catch (OverflowException ex)
{
Console.WriteLine("Entered an invalid integer!!!. -- " + ex.Message);
return "Error";
}
catch (ArgumentNullException ex)
{
Console.WriteLine("Entered an invalid integer!!!. -- " + ex.Message);
return "Error";
}
}
private int GetPrevNextSameOnes(long inpNum)
{
if (inpNum == 0)
{
return -1;
}
int countOfOnes = GetNumOfOnes(inpNum);
long tempNum = inpNum;
while (inpNum != long.MaxValue && countOfOnes != GetNumOfOnes(++inpNum)) ;
if (inpNum != long.MaxValue)
Console.WriteLine("Next integer with same number of ones:{0}", inpNum);
else
return -1;
while (tempNum != long.MinValue && countOfOnes != GetNumOfOnes(--tempNum)) ;
if (tempNum != long.MinValue)
Console.WriteLine("Previous integer with same number of ones:{0}", tempNum);
else
return -1;
return 0;
}
private int GetNumOfOnes(long n)
{
Console.Write(".");
bool isNegative = n < 0 ? true : false;
n = isNegative ? -1 * n : n;
int count = 0;
while (0 != n)
{
if (n % 2 == 1)
count++;
n /= 2;
}
count = isNegative ? (sizeof(int) * 8) + 1 - count : count;
return count;
}
}
Greatht's algorithm is correct.
To explain this, let's take 1000101111 for example.
Since we want to find the next binary with same number of 1's. So if we treat this as a string, the next number is among all the strings that swap some 0 and 1 in this string. (If it's all 1, then image there is a leading 0)
We obviously don't want it to be very large. So if there is a 0 in the lower bit for us to swap with some 1 in even lower bit, then we can always keep the higher bit unchanged. [Otherwise we will make this number larger].
So, now we have 10001-01111 with 10001 unchanged, this implies that we have to find the rightmost 01 pattern. Once we get this, the rest of this is simple, just swap the 01 and we get the next neighbor.
I think it is wrong. Consider the following example
Number = 236 = 11101100
Iteration1:
11101100 & 11 = 00
Number = 11101100 >> 1 = 1110110 (118)
Delta = 1 << 1 = 10 (2)
Iteration2:
1110110 & 11 = 10 (2) So will come out of while loop
Will print Number - Delta = 1110110 - 10 = 118 - 2 = 116
The answer should be 234 (11101010) 5 ones in it. 236 also has 5 ones in it.
My Solution. Though brute force it works.
class SameNumOfOnes
{
public SameNumOfOnes()
{
string inpStr;
while ((inpStr = ReadInt()) != "END")
{
if(!inpStr.Equals("Error"))
if (GetPrevNextSameOnes(long.Parse(inpStr)) < 0)
Console.WriteLine("Error");
}
}
private string ReadInt()
{
Console.Write("Enter an integer to convert to words (Enter 'END' to quit):");
long inpNum;
string inpStr;
try
{
inpStr = Console.ReadLine();
if (inpStr.Equals("END"))
return inpStr;
inpNum = long.Parse(inpStr);
return inpStr;
}
catch (FormatException ex)
{
Console.WriteLine("Entered an invalid integer!!!. -- " + ex.Message );
return "Error";
}
catch (OverflowException ex)
{
Console.WriteLine("Entered an invalid integer!!!. -- " + ex.Message);
return "Error";
}
catch (ArgumentNullException ex)
{
Console.WriteLine("Entered an invalid integer!!!. -- " + ex.Message);
return "Error";
}
}
private int GetPrevNextSameOnes(long inpNum)
{
if (inpNum == 0)
{
return -1;
}
int countOfOnes = GetNumOfOnes(inpNum);
long tempNum = inpNum;
while (inpNum != long.MaxValue && countOfOnes != GetNumOfOnes(++inpNum)) ;
if (inpNum != long.MaxValue)
Console.WriteLine("Next integer with same number of ones:{0}", inpNum);
else
return -1;
while (tempNum != long.MinValue && countOfOnes != GetNumOfOnes(--tempNum)) ;
if (tempNum != long.MinValue)
Console.WriteLine("Previous integer with same number of ones:{0}", tempNum);
else
return -1;
return 0;
}
private int GetNumOfOnes(long n)
{
Console.Write(".");
bool isNegative = n < 0 ? true : false;
n = isNegative ? -1 * n : n;
int count = 0;
while (0 != n)
{
if (n % 2 == 1)
count++;
n /= 2;
}
count = isNegative ? (sizeof(int) * 8) + 1 - count : count;
return count;
}
int p;
int a[32] = {0}, b[32] = {0}, c[32] = {0};
int i = 31;
p = 0x51; // Is the input no.
while(p)
{
if(p & 0x80000000)
{
a[i] = c[i] = b[i] = 1;
}
p = p << 1;
i--;
}
for (i =1; i<32; i++)//Find lesser than p with same no. of bits on
{
if(b[i] == 1 && b[i-1] == 0)
{
b[i] = 0;
b[i-1] = 1;
break;
}
}
for (i=1; i<32;i++) //Find more than p with same no. of bits on
{
if(c[i] == 0 && c[i-1] == 1 )
{
for(;i>0;i--)
c[i]=c[i-1];
c[0] = 0;
break;
}
}
Consider the binary number as a string...
For the Next Number -- Traverse the string from right to left,if you find 10 then swap them ...if you dont find any pair of that sort then it is the number with max. number of 1's usually it happens with all 1's
Prev. Number -- Traverse from left to right , if you find 10 then swap them ,similarly..
Check the number from the least significant bit and if you find 1 and 0 combination then swap them else the number doesn't have a next number with same number of bits ... similarly for the previous number start from the most significant bit and try to find 1 and 0 combination if found swap else doesnt have previous number with same number of bits ..
for Next Number
for(int i=0;i<str-1;i++){
if(str[i]=='1' && str[i+1]=='0'){
swap(str[i],str[i+1]);
print(str);
break;
}
}
}
vamsi, you solution has a problem. Think about 6 (0110), the next integer should be 9 (1001), but your solutions gives 10 (1010). So not only you should swap, but you also need to move all other 1's you meet to the LSB side.
So for next number:
int j = 0; /* The least significant bit which is 0 */
for(int i=0;i<str-1;i++){
if(str[i]=='1' && str[i+1]=='0'){
swap(str[i],str[i+1]);
print(str);
break;
} else if (str[i]=='1') {
swap(str[i], str[j]);
j ++;
}
}
int numbits ( int n )
{
int count = 0; for ( ; n; count++) { n &= n-1 } return count;
}
<safetychecks = "off>
int bitcount = numbits ( N ); // N is the integer in question
int tmp = N;
while ( numbits ( --tmp ) != bitcount; // tmp has prev neighbor
tmp = N;
while ( numbits ( ++tmp ) != bitcount; // tmp has next neighbor
</safetychecks = "on">
Doc
#include <iostream>
using namespace std;
int CountOnes(int num)
{
int count = 0;
while(0 != num)
{
if(num%2==1)
count++;
num/=2;
}
return count;
}
int main()
{
int num,passnum,NxtNum;
num=passnum=NxtNum=6;
int count = CountOnes(num);
bool prevnum = false;
bool nxtnum = false;
int prevcount,nxtcount;
int prev_num,nxt_num;
prevcount=0;nxtcount=0;
while( !prevnum || !nxtnum )
{
if ( prevcount == count )
{
prev_num = passnum;
prevnum = true;
}
else
{
prevcount = CountOnes(--passnum);
}
if ( nxtcount == count )
{
nxt_num = NxtNum;
nxtnum = true;
}
else
nxtcount = CountOnes(++NxtNum);
}
return 0;
}
tested with VS 2005....works fine for me..
i think the question says this-
1.find the next no having the same no of 1s as this no. say we have 0101, so the next no having the same no of 1s(here 2)is 0110 also for 0111 the answer is 1011. so we are not talking about the just next no(n+1) (i.e for 0001 the answer is 0010, which BTW also satisfies our criteria.
2.similary for the previous no.
Vamsi solution with alongwith Integers Patch is OK....
I think all of the above discussion missed one point.
For the next neighbor, after finding the rightmost "01" pattern and swap it, we still need to swap the "1"s and "0"s to the right. For example, say A=011,011,111,000. The rightmost "01" pattern appears at position 9(starting from 1 and from left to right). After swapping "0" and "1" in this pattern we get "011,101,111,000". We still need to swap position 7 and 1, 6 and 2, 5 and 3 to get "011,100,001,111". This is the correct next neighbor.
Based on this, the code is very very simple.
bool after_power2(int& b)
{
int w = 1;
if (b == 0) return false;
while(w < b)
{
w *= 2;
}
if(w > b) w /= 2;
b -= w;
return true;;
}
int count_1(int b)
{
int ctr = 0;
while(after_power2(b))
{
ctr++;
}
return ctr;
}
void find_neighbor(const int a, int& p, int& n)
{
int* b = const_cast<int*>(&a);
int ca = count_1(*b);
p = *b - 1;
n = *b + 1;
while(p && count_1(p) != ca)
{
p--;
}
while(n < 0xFFFF && count_1(n) != ca)
{
n++;
}
}
ok, here comes some bit wizardy:
int prev(int n) {
int y = ~n;
y &= -y; // lowest zero bit
n &= ~(y-1); // reset all bits below y
int z = n & -n; // lowest set bit
n &= ~z; // clear z bit
n |= (z - z / (2*y)); // add requried number of bits below z
return n;
}
int next(int n) {
int lo = n & -n; // lowest one bit
int lz = (n + lo) & ~n; // lowest zero bit above lo
n |= lz; // add lz to the set
n &= ~(lz - 1); // reset bits below lz
n |= (lz / lo / 2) - 1; // put back right number of bits at end
return n;
}
to binaryNos:
i think there is a missing in your next section.
for example use your method
10110->11010 but actually we know 11001 is the next to 10110
my mothed is very similar to yours but with correction
X0[1][0]
prev: find righttmost 10 and flip it
next: find rightmost 01, flip it and shift the rest '1's in [1] to left until we get lsb
X1[0][1]
prev: find rightmost 10, flip it and shift all 1s in [1] to left until we get a 1
next: find rightmost 01 and flip it
X represents any digits
//algorithm to get next integer
//i/p = 10011100; o/p = 10100111
(1) check from right to left
(2) leave trailing 0's and find the first 0 (10 0 11100)
(3) we have to make this 0 to 1
(4) watever 1's are there bubble all those 1's to trailing side
u have the answer
int nextInt(int n)
{
int a, b, c, d, e, f, g, val;
a = n ^ (n-1);
b = n | a;
c = b + 1;
d = b ^ c;
e = n & d;
f = a & e;
g = (e >> bitPosition(f));
val = c | g;
return(val);
}
if we can write bitPosition(n) where only 1 bit is set in n in O(1), then nextInt(n) is O(1) time algorithm else its O(log n)
//not compliled
//algorithm to get previous integer
//i/p:11000111; o/p:10111000
int a,b,c,d,e,f,g,h,val;
a = n & (n-1);
b = a ^ (a-1);
c = (b>>1) + 1;
d = n & ~c;
e = d ^ (d+1);
f = log(c, 2) - log(e, 2); //O(log n) step
g = b & d;
h = g << f;
val = a | h; //ANSWER
if (LSB == 0) {
if (continue to find next 1 at index i) {
swapbit(i, i-1); // i is 1, i-1 is 0, get the smaller value
if (continue to find next 0 at index j) {
swapbit(i, j); // j is 0, i is j; get the bigger value
}
else {
// input value is negative value
bigger value = (unsigned int)(input) >> i;
}
}
else {// no value could be found, all 0...}
}
// LSB is 1
else {
if (find next 0 at index i) {
swapbit(i, i-1);// get bigger value;
if (continue to find next bit 1 at index j) {
swapbit(i, j); // get smaller value;
}
else {
smaller value = inputvalue << (sizeof(int)*8-i);
}
}
else {
// all 1, cannot find
}
}
For the next number, scan from left to right to find the last 01 pair, swap it and then sort all the 1's and 0's right of the pair in ascending order.
For the previous number, scan from right to left to find the first 10 pair, swap it and then sort all the 1's and 0's right of the pair in descending order.
//algorithm to get next integer
- mail2vcp@gmail.com September 29, 2008//i/p = 10011100; o/p = 10100111
(1) check from right to left
(2) leave trailing 0's and find the first 0 (10 0 11100)
(3) we have to make this 0 to 1
(4) watever 1's are there bubble all those 1's to trailing side
u have the answer
ex:
(1)
6543210(poistion)
1011010(num)
1st zero position after getting 1 1's is 2, make it 1 and all 1-1 1's at rightmost side
1011100
(2)
6543210(poistion)
1011100(num)
1st zero position after getting 3 1's is 5, make it 1 and all 3-1 1's at rightmost side
1100111
(3)
6543210(poistion)
1100111(num)
1st zero position after getting 3 1's is 3, make it 1 and all 3-1 1's at rightmost side
1101011
etc
check this code
int bitPosition(int n)
{
int count = 0;
while(n>1)
{
n/=2;
count++;
}
return count;
}
int nextInt(int n)
{
int a, b, c, d, e, f, g, val;
a = n ^ (n-1);
b = n | a;
c = b + 1;
d = b ^ c;
e = n & d;
f = a & e;
g = (e >> bitPosition(f));
val = c | g;
return(val);
}
if we can write bitPosition(n) where only 1 bit is set in n in O(1), then nextInt(n) is O(1) time algorithm else its O(log n)