Alexander Opekunov
BAN USERJava, SQL, Telecom
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;
}
Method returns new int array, takes into account requirements regarding array length and leading zeros. Optimized to use 1 pass array navigation. Main time consuming operation is array copy.
public static int[] incrementIntArray(int[] inputOriginalIntArray)
{
if(inputOriginalIntArray==null) return null;
//Create copy of input array to not mutate it
int[] inputIntArray = Arrays.copyOfRange(inputOriginalIntArray,0,inputOriginalIntArray.length);
// Increment by 1 using taking into account 9 in the end
int i = inputIntArray.length-1; //firstNonNine
while (i>=0 && inputIntArray[i] == 9) {
inputIntArray[i]=0;
i--;
if(i<0) //All are 9
{
int[] result = new int[inputIntArray.length+1];
result[0]=1;
return result;
}
}
//first non 9 found, lets increment it
inputIntArray[i]++;
//check if there are leading zeros, calculate first non zero
int j = 0; // fistNonZero
while(j<i && inputIntArray[j] == 0) j++;
if(inputIntArray.length==j)
{
return new int[]{1}; //if all are zeros
} else if(j==0)
{
return inputIntArray; //no leading zeros at all, just return modified array
} else
return Arrays.copyOfRange(inputIntArray,j,inputIntArray.length); //there are leading zeros, return trimmed array
}
Replarenccabral, Title searcher at Fisher Foods
In real estate business and law, a title search or property title search is the process of examining public records ...
RepDessieBieri, Human Resource Executive at Bazaarvoice
I am Dessie, an academic advisor with more than 2 years of extensive field experience and a well-developed industry knowledge ...
RepDiptaHunt, Apple Phone Number available 24/7 for our Customers at A9
I am a dedicated english-mandarin Chinese translator with years of experience working in professional and scientific communities.I have exceptionally ...
Guess if the lists are sorted, we can just compare them by 1 pass, O(N), logic already mentioned, here is just my implenetation, without any extra transformations to lists:
}
- Alexander Opekunov September 10, 2015