Country: United States

Comment hidden because of low score. Click to expand.
1
of 1 vote

Exchange the lowest order adjacent 1 and 0.

``````def nearest(num):
p = 1
while num & p == 0:
p <<= 1
if p == 1:
while num & p != 0:
p <<= 1
return num ^ (p | p >> 1)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi Mehrdad, that is certainly true and it looks good. What remains now is to minimize |x-y|. Sorry I edited the task right after I posted it, I forgot to write the minimization condition.

I like the trick with two's complement (x & -x), awesome :)

Comment hidden because of low score. Click to expand.
0
of 0 vote

Exchange the lowest order 1 and 0.

``````def nearest(num):
p = 1
while num & p == 0:
p <<= 1
if p == 1:
while num & p != 0:
p <<= 1
return num ^ (p | p >> 1)``````

Comment hidden because of low score. Click to expand.
0

You would want to check for zero before you start your loops or does the question say the input will be non zero.

Comment hidden because of low score. Click to expand.
0

The question states "positive integer between 0 and 2^32-2". This is required as the problem solution condition cannot be satisfied for 0x0 or 0xFFFFFFFF.
The constraint however should be "between 0 and 2^32 -1" - between implies an open interval.

Comment hidden because of low score. Click to expand.
0
of 0 vote

find the next smaller and next greater number with same set of bits.
Find the one with minimum difference and return the same.

finding next greater -
1) find the first one from right;
2) find the first zero from right and first one.
3) set the first zero as One and right next to it as Zero.
4) Set all remaining zeros first and then Ones.

Same for other also...

Comment hidden because of low score. Click to expand.
0

Perhaps this would be clearer with code.

Comment hidden because of low score. Click to expand.
0
of 0 vote

if bit 0 is set, find the first unset bit, then set it and unset the bit to its right.
Otherwise (bit 0 is not set), find first set bit, unset it and set the bit to its right.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Suppose x has 5 bit set. Return y such that it same high bit as x except the lower one bit.

example
x (bitwise) = 11110100
then y = 11110010

border cases when the first bit is set, in this case choose the one higher bit.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Suppose x has 5 bit set, choose y such that it has same exact 4 high bit set, except the smallest 1 bit. This can be one position to the right or left.

Example :
x (bitwise) : 11110100
y (bitwise) : 11110010

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public int findMinDistanceNumber(int number) throws Exception {
int powOf2 = 1;
if (number <= 0 || number >= Integer.MAX_VALUE - 2) throw new Exception("Invalid number!");
//Find the 0 before/after the first 1 and toggle
while(powOf2 < Integer.MAX_VALUE - 2) {
// If power of 2 bit is set
if ((number & powOf2) > 0) {
// Check right first if that bit can be set to 1
if (powOf2 != 1 && (number & (powOf2 >> 1))==0) {
number = number + (powOf2 >> 1) - powOf2;
break;
}
// Else check left
if ((number & (powOf2 << 1))==0) {
number = number + (powOf2 << 1) - powOf2;
break;
}
}
powOf2 = powOf2 << 1;
}
return number;
}``````

Comment hidden because of low score. Click to expand.
0

(powOf2 << 1) - powOf2 == powOf2

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def solve(input: Long): Long = {
val shifted = num >> 1
if ((shifted & 1) != (num & 1))
else
}

if (input < 1 || input > Math.pow(2, 32).toLong - 2)
throw new IllegalArgumentException

//Exchange the lowest order adjacent 1 and 0
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

1. get the bit count for X
n = get_bit_count(X);
2. get the one count for X
one_cnt = get_one_count(X)

int min = INT_MAX;

for(i = 1;i < 2 ^ n; i++ ) {
if(one_cnt = = get_one_count(i) &&
X != i) {
if(i < min)
min = i;
}
}
return min

Comment hidden because of low score. Click to expand.
0

Sorry , liitle correct

line if(i < min) should be replaced as

if (abs(X- i ) < min)

Comment hidden because of low score. Click to expand.
0

That's an exponential-time solution. You are calculating the Hamming weight 2**n + 1 times. That's pretty expensive when you really only need to do n-1 shift and & operations.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````unsigned int func(unsigned int x)
{
int i=0;

while (  !(  ((x & 1<<i) ? 1:0)  ^  ((x & 1<<(i+1)) ? 1:0)  ) )
i++;

return x ^ 3<<i;
}``````

Find "01" or "10" within the binary representation of number and swap it to "10" or "01" respectively. This will give a number with same set bits and minimum difference from x.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````var x = parseInt("01010111",2);

function first(n){
return n & ~(n-1);
}

function flip(x,n){
var tmp = n + (n>>1);
return tmp^x;
}

var f0 = first(~x);

var result = flip(x, (f0>1)?f0:first(x));``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````unsigned int minDiffBitSwap(unsigned int x) {
unsigned int y = x;
if (x & 1) {
for (int i = 1; i < 32; ++i) {
int mask = (1 << i);
}
}
} else {
for (int i = 1; i < 32; ++i) {
int mask = (1 << i);
}
}
}
return y;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/*
Strategy: From LSB to MSB, identify first consecutive bits
those are different and swap/flip them.
No solution for 0x0 and 0xffffffffffffffff
*/
#include <iostream>
#include <stdio.h>

using namespace std;

int main(){
unsigned long long x;
scanf("%lld", &x);

if(x == 0 || x == 0xffffffffffffffff) {
cout << "No solution\n";
return 0;
}

unsigned long long x_tmp = x;
int i=0;
int prevBit = x_tmp & 0x1;
while(x_tmp){
x_tmp >>= 1;
if(prevBit != (x_tmp&0x1)) break;
prevBit = x_tmp & 0x1;
i++;
}

unsigned long long y = x ^ (3<<i);
cout << y << endl;

return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````// The idea is to start from the LMB by taking a pair of consecutive bits.
// If the consecutive bits are not equal, they are exchanged. The resulting number after
// exchange is the result.
// If the bits either all 0s or 1s, it is not applicable as all the bits are same.
// Otherwise there should be atleast a pair of consecutive bits which are not same - 01 or 10
// We don't cosider if the pair of bits are at the righmost position, as after exchanging the bits
// one of the numbers will have a leading zero which doesn't get counted as part of the unsigned number.
// Example -
// 10000                      : bitset = 1 1s, 4 0s
// 01000    =>  1000    : bitset =  1 1s, 3 0s

// flipBit flips the bit at position pos
func flipBit(n uint32, pos uint) uint32 {
return n
}

// nearestBitset returns a number m with same bitset as n such that |n - m| is minimimum.
// It returns n if it is not applicable
func nearestBitset(n uint32) uint32 {
// bit positions
pos1, pos2 := uint(0), uint(1)
// how far should pos2 go
for m > uint32(0x11) {
if ((n >> pos1) & mask) != ((n >> pos2) & mask) {
fmt.Printf("exchanging bits at positions: %d, %d\n", pos1, pos2)
n = toggleBit(n, pos1)
n = toggleBit(n, pos2)
return n
}
pos1++
pos2++
}
return n
}``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

``````if(x&1){
y = x << 1;
}
else{
y = x >> 1;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

For example, we reversing one bit 1 to 0, so we have to revers another bit from 0 to 1 to have same bits set.
We can repeat such pair operations several times to get any y with same bits set as x.
Consider y > x, lets find nearest (min) y. Each bit corresponds to order of 2.
Consider y has reversed bits on position K and N (K>N, N=K+I), in this case y-x = 2orderK-2orderN=2OrderK*(2orderI-1)
We can see that min of y-x will be in case I=1 -> K and N are nearest bits and in this case y-x=2orderK.
Also K should be minimum to get minimum y-x. In this case x^y=2orderK*(2+1) =3*2orderK . We need to find K.
Same logic for case x>y, depends of is x odd or not.

``````public static int getNearestSameBitSet(int x)
{
if(x==0||x==Integer.MAX_VALUE)  {
return -1;
}

int y;

if(x%2!=0)   //starts from 1 on the right side
{
int i = 1;

while (i<Integer.MAX_VALUE)
{
y=x+i;
if((x^y)==(3*i)) return y;
i <<= 1;
}
} else if((x%2)==0)   //starts from 0 on the right side
{
int i = 1;
while (i<x)
{
y=x-i;
if((x^y)==(3*i)) return y;
i <<= 1;
}
}

return -1;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````unsigned int func(unsigned int x)
{
if(x==0)
return 1;

int i=0;
for(i=0 ; i<31 ; i++)
{
if( ((x&1<<i) > 0 && (x&1<<i+1) > 0) || ((x&1<<i) == 0 && (x&1<<i+1) == 0) )
continue;
else
break;
}

x = x^(1<<i);
x = x^(1<<i+1);

return x;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````unsigned int func(unsigned int x)
{
if(x==0)
return 1;

int i=0;
for(i=0 ; i<31 ; i++)
{
if( ((x&1<<i) > 0 && (x&1<<i+1) > 0) || ((x&1<<i) == 0 && (x&1<<i+1) == 0) )
continue;
else
break;
}

x = x^(1<<i);
x = x^(1<<i+1);

return x;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Exchange lowest neighboring 1 and 0.

``````#include <functional>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <utility>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <set>

using namespace std;

int bit_count(int n)
{
int r=0;
while(n)
{
r++;
n &= (n-1);
}

return r;
}

int similar_etalon(int n)
{
int bits = bit_count(n);

int smaller = -1;
int greater = -1;

for(int i = n-1; i >= 0; --i)
{
if (bit_count(i) == bits)
{
smaller = i;
break;
}
}

for(int i = n+1; ; ++i)
{
if (bit_count(i) == bits)
{
greater = i;
break;
}
}

if (smaller == -1)
return greater;

if (n-smaller < greater-n)
return smaller;

return greater;
}

int similar(int n)
{
if (n == 0)
throw 0;

int last_bit = n ^ (n & (n-1));

if (last_bit > 1)
{
int result = n - last_bit + (last_bit >> 1);

return result;
}
else
{
int k = n + 1;
int last_zero = k ^ (k & (k-1));

int result = n + last_zero - (last_zero >> 1);

return result;
}
}

int main()
{
int total = 0;
int passed = 0;
for(int i = 1; i <= (1 << 16); ++i, ++total)
{
int e = similar_etalon(i);
int r = similar(i);

if (e != r)
{
cout << "Test Case #" << i << " FAILED! " << "Expected: " << e << " Received: " << r << endl;
}
else
{
passed++;
}
}

cout << "Passed " << passed << "/" << total << endl;

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Exchange lowest neighbouring 1 and 0.

``````#include <functional>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <string>
#include <utility>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <set>

using namespace std;

int bit_count(int n)
{
int r=0;
while(n)
{
r++;
n &= (n-1);
}

return r;
}

int similar_etalon(int n)
{
int bits = bit_count(n);

int smaller = -1;
int greater = -1;

for(int i = n-1; i >= 0; --i)
{
if (bit_count(i) == bits)
{
smaller = i;
break;
}
}

for(int i = n+1; ; ++i)
{
if (bit_count(i) == bits)
{
greater = i;
break;
}
}

if (smaller == -1)
return greater;

if (n-smaller < greater-n)
return smaller;

return greater;
}

int similar(int n)
{
if (n == 0)
throw 0;

int last_bit = n ^ (n & (n-1));

if (last_bit > 1)
{
int result = n - last_bit + (last_bit >> 1);

return result;
}
else
{
int k = n + 1;
int last_zero = k ^ (k & (k-1));

int result = n + last_zero - (last_zero >> 1);

return result;
}
}

int main()
{
int total = 0;
int passed = 0;
for(int i = 1; i <= (1 << 16); ++i, ++total)
{
int e = similar_etalon(i);
int r = similar(i);

if (e != r)
{
cout << "Test Case #" << i << " FAILED! " << "Expected: " << e << " Received: " << r << endl;
}
else
{
passed++;
}
}

cout << "Passed " << passed << "/" << total << endl;

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

All you need to do is to swap leftmost neighbouring 1 and 0. This can be done in constant time.

Comment hidden because of low score. Click to expand.
0

Rightmost. And it's linear time.

Comment hidden because of low score. Click to expand.
0
of 0 vote

You need to find the first two bits with different value, 0 and 1, or 1 and 0, for that porpuose you need XOR, then toggle those bits using XOR again.

For example:

number = 11

Bit representation: 1011

0111 = 7

1110 = 12

1101 = 13

All these numbers have the same amount of 1’s, but according to restriction, the answer is 1110 = 12.

Using toggle(int n) you will encounter than 1011 the LSB and third LSB are different, so just toggle those bits using XOR, and that is the answer.

``````int toggle (int n) {
if (n == 0)
return 0;
int i = 0;
while (true) {
if ((n & 1) ^ ((n >> ++i) & 1))
{
n ^= 1 << 0;
n ^= 1 << i;
return n;
}
}
return n;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think this problem is the same as "find the next(previous) integer with the same number of bit set", code as follows:

``````unsigned int Next(unsigned int x) {
// test: x = 01101110
int a = x & ~(x - 1); // a = 00000010
int b = x + a;		  // b = 01110000
int c = x & ~b;		  // c = 00001110
int d = c / a >> 1;   // d = 00000011

return b | d; // ans = 01110011
}

unsigned int Previous(unsigned int x) {
// test: x = 01110011
unsigned int a = x & ~(x - 1);         // a = 00000001
unsigned int b = x + a;                // b = 01110100
unsigned int c = x & b;				   // c = 01110000
unsigned int d = (c & ~(c - 1)) >> 1;  // d = 00001000
unsigned int e = ~x & b;	           // e = 00000100
unsigned int f = d / e;				   // f = 00000010
unsigned int g = e - 1;		           // g = 00000011

return (c & ~(d << 1)) | d | f * g;	// ans = 01101110
}

unsigned int solve(unsigned int x) {
unsigned int pre = Previous(x);
unsigned int next = Next(x);

return x - pre < next - x ? pre : next;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def bit_change(x):
return (x&1)*(x^(~x&(x+1))^((~x&(x+1))>>1))+(1-x&1)*(x^(x&(~x+1))^((x&(~x+1))>>1))``````

If the first (rightmost) bit is 0, set the first set bit to 0, and the bit to the right of it to 1. If the first bit is 1, then set the first unset bit to 1, and the bit to the right of it to 0.

Comment hidden because of low score. Click to expand.
0
of 0 vote

If the LSB is 0 find the least significant set bit, unset it and add 1 to the result;
If the LSB is 1 find the least significant unset bit, set it and deduct 1 from the result;

``````public static int findClosestWithOneChange(int a) {
if (a % 2 == 0) {
int firstOne = a & -a;
return a - firstOne + 1;
} else {
int b = a + 1;
int firstZero = b & -b;
return a + firstZero - 1;
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 5 vote

int firstOne = (x & -x);
int i = log(firstOne)/log(2.0);

y = (x >> (i+1) ) | ( 1<<32);

first we need to find the first set bit of x (from right).let's say first 1 occurred at i-th bit. if we shift all bits of x, (i+1) times to the right, then x will have one set-bit less than before. now, if we change the last bit (32-th place) to 1, the result would have equal number of 1's and is different from x.

Update: When I wrote this solution, writers of question hadn't mentioned the constraint of minimizing |y-x|

Comment hidden because of low score. Click to expand.
0

x is unsigned though. -x gives a compilation error in C++

Comment hidden because of low score. Click to expand.
0

Hi Mehrdad, that is certainly true and it looks good. What remains now is to minimize |x-y|. Sorry I edited the task right after I posted it, I forgot to write the minimization condition.

I like the trick with two's complement (x & -x), awesome :)

Comment hidden because of low score. Click to expand.
0

|x-y| is not minimized hence not correct solution...

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Let's move all bits one position left, carry-over the first bit if it is set.

``````unsigned foo(unsigned x) {
unsigned y = x >> 1;
if (x & 1) {
y |= 0x10000000; // 0b1000...000
}
return y;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Let's move all bits one position left, carry-over the first bit if it is set.

``````unsigned foo(unsigned x) {
unsigned y = x >> 1;
if (x & 1) {
y |= 0x10000000; // 0b1000...000
}
return y;
}``````

Comment hidden because of low score. Click to expand.
0

How to you minimize the distance |x-y|? A am afraid this is not a solution.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Let's move all bits one position left, carry-over the first bit if it is set.

unsigned foo(unsigned x) {
unsigned y = x >> 1;
if (x & 1) {
y |= 0x10000000; // 0b1000...000
}
return y;
}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Let's move all bits one position left, carry-over the first bit if it is set.

unsigned foo(unsigned x) {
unsigned y = x >> 1;
if (x & 1) {
y |= 0x10000000; // 0b1000...000
}
return y;
}

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.