[Java] Reverse integer

Given a 32 bit integer, reverse it.

Example:

123 becomes 321

The initial thought was to treat the integer as a bit array, swapping each from left to right.

This would have some tricks in the implementation, especially since Java uses 2's complement for negative representation, but could be done and has a complexity of O(32) at most as we consider each bit in the number.

However, turns out there is a much better approach that uses divide and conquer logic to achieve the same result:

 public static int reverseBits(int n){  
     //take half of the bits from MSB to mid portion  
     //take half of the bits from mid to LSB portion  
     //swap them  
     //repeat the process with always smaller masks and portions  
     //mask is always 32 bit in size  
   
     //initial swap, throw away 16 LSB and 16 MSB, combine them together  
     //now we have the two halves reversed  
     n = n >>> 16 | n << 16;  
   
     //mask for left portion: 1111 1111 0000 0000 1111 1111 0000 0000  
     //mask for right portion: 0000 0000 1111 1111 0000 0000 1111 1111  
     //then shift by half of previous size (8 bit)  
     n = (n & 0xff00ff00) >>> 8 | (n & 0x00ff00ff) << 8;  
   
     //mask for left portion: 1111 0000 1111 0000 1111 0000 1111 0000  
     //mask for right portion: 0000 1111 0000 1111 0000 1111 0000 1111  
     //then shift by half of previous size (4 bit)  
     n = (n & 0xf0f0f0f0) >>> 4 | (n & 0x0f0f0f0f) << 4;  
   
     //mask for left portion: 1100 1100 1100 1100 1100 1100 1100 1100  
     //mask for right portion: 0011 0011 0011 0011 0011 0011 0011 0011  
     //then shift by half of previous size (2 bit)  
     n = (n & 0xcccccccc) >>> 2 | (n & 0x33333333) << 2;  
   
     //mask for left portion: 1010 1010 1010 1010 1010 1010 1010 1010  
     //mask for right portion: 0101 0101 0101 0101 0101 0101 0101 0101  
     //then shift by half of previous size (1 bit)  
     n = (n & 0xaaaaaaaa) >>> 1 | (n & 0x55555555) << 1;  
   
     //now all the bits have been moved around in the reverse place  
     return n;  
   }  

The idea is to split the integer in two halves, shift them by half the size of the integer, and combine them back.

Repeating this process on each half will in the end give the desired result.

[Java] Find missing integer in array of unique elements

Given an array of length N of unique positive integers in range 0..N both inclusive, find the missing one.

We have two linear approaches, one uses a mathematical formula, the other some bit magic.

Math:

all numbers in range 0..N summed up can be calculated with the formula:

N * (N + 1) / 2

If we sum up all elements in the array, our missing number is the expected sum minus the actual sum

Bit:

if the array was of size N + 1 and all integers in range 0 .. N were present and sorted, each would sit at the index same as the number itself, for example:

idx: 0 1 2

num: 0 1 2

Since we know only one number is missing, there must be some index where the value doesn't match the index.

Since N + 1 is NOT a valid index in the array, we can initialize a variable to that, then XOR that variable with all values and indices in the array.

All repeated elements (index and value) would cancel out, leaving only the missing one as result.

You can check my implementation of findMissingNumber on my Gist (math) and Gist (bit) along with some tests in FindMissingNumberJTests (math) and FindMissingNumberJTests (bit).

[Java] Count number of bits set to 1

Given a positive integer N, find for each integer in range 0..N inclusive, how many bits are set to 1.

We could for each integer in range 0..N consider its binary representation and pick off all bits set to 1 counting them.
This would make us do at most 32 operations for each number, being 32 a constant we'd have linear time but performance is still impacted.

We can however reuse information we stored earlier (especially in this case it's part of our answer anyway)
Drawing the binary sequence for 0..8 gives us:

• 0: 0000
• 1: 0001
• 2: 0010
• 3: 0011
• 4: 0100
• 5: 0101
• 6: 0110
• 7: 0111
• 8: 1000

And we notice that N and N*2 have exactly the same amount of bits set, just shifted left one position, example:

• 3 and 6
• 2, 4 and 8

What is left out is odd numbers like 5 and 7. But in that case, it's just about setting the lsb to 1 from the previous number, example:

• 5 = 4 + 1
• 7 = 6 + 1

so to create an odd N, we can simply start from N/2, shift it up one position AND check if we should set the lsb to 1 in this new number.
 

If we know how many bits are set in N/2, we skip all of this process and just reuse that value adding one to it if the lsb should be 1. We know if it should be 1 by checking N & 1.

This is also equal to saying number of bits set in N is N/2 + N mod 2 as anything modulo 2 will always be either 0 or 1, specifically 0 if N is even and 1 if N is odd.

We repeat this process for all numbers in our range and we have the solution.

Since the output is part of the solution, our space complexity is O(1) and our time is O(N).

All operations we use are division by 2 and modulo by 2, which are a right bit shift and a bitwise AND.

You can check my implementation of countOnes on my Gist along with some tests in CountOnesJTests.

[Java] Sum two integers without sum operator

Given two integers, return a + b without using sum operator.

Seems like it's time for more bit magic. 

We process our numbers bit by bit starting from LSB, we track a carry, a position in the result sum, and the result sum.

Getting the LSB can be done by:

n & 1

If 1 the bit was set to 1

Then we can calculate the result of the sum:

it will be a 1 only if there is an odd number of ones between lsbA, lsbB and carry:

• 1 + 1 = 0, unless carry was 1
• 1 + 0 = 0, unless carry was 1
• 0 + 0 = 0, unless carry was 1

res = lsbA ^ lsbB ^ carry

Then we can push that bit in the correct place in the final result:

res = res << position

And set it in the final sum:

sum |= res

Also we need to increase position for the next iteration, but we can't use sum operator:

position = -(~position)

We can then calculate the carry for the next iteration:

it will be a 1 if there were at least two ones between lsbA, lsbB, carry:

• 0 + 1 + 0 = 1 no carry
• 1 + 1 + 0 = 0 with carry
• 0 + 0 + 1 = 1 no carry
  
• 1 + 1 + 1 = 1 with carry 

carry = (lsbA & lsbB) | (lsbA & carry) | (lsbB & carry)

we then drop the lsb from both a and b WITHOUT preserving sign (we need it come to us for processing, we can't leave it set in MSB):

a = a >>> 1

b = b >>> 1

and repeat this process until both a and b are 0

One last thing to do after all of this, if there was still a carry left AND we are not trying to set it in position 32 (MSB), set it in the final sum.

You can check my implementation of sum on my Gist along with some tests in SumJTests.

[Java] Increment number without using sum operator

Here's another piece of bit magic that works on those systems where numbers are stored using 2's complement.

Since a negative number is stored using that form, and that form is obtainable by inverting all the bits then adding one, we can get the number + 1 by inverting all bits first and then flipping its sign:

n = -(~n)

This works for both negatives and positives.

[Java] Find all paths from source to dest in a directed acyclic graph

Given a DAG, find all paths from source to target.

Since it is a DAG, there are no cycles, therefore we can't go back to an already visited vertex during a visit.

We can therefore add the source to a stack, then use recursion to find all paths from source to target.

In the recursive function, we look at the current node (top of stack) and for each one of its edges, we add the destination to the stack and call recursion on that destination.

When the top of stack is the target, we scan the scan and track all elements as a solution, they will be in inverted order from last vertex to first. However, a foreach loop on a Stack (in Java) gives element in order from bottom to top, so there is no need to invert them in our result.

When we get back from a recursive call, we remove ourselves from the stack as we have fully explored our subgraph.

This code works in O(V) space as that's how deep the recursion could go, and our stack also matches the recursion in size.

For time complexity, I assumed we would get a O((V+E)^2) upper bound as without cycles we cannot go back to previously visited vertices but some paths might overlap and we would walk down the same edge multiple times.

This might not be the case if we look for ALL paths from ALL vertices, however we only consider ONE start vertex in this case.

I think it made sense as a similar problem which is topological sorting is linear and in this case we're looking at all paths between the two farthest nodes.

Turns out it's exponential in reality:  If all vertices are connected (without cycles) for each new node excluding start and end, we have a choice of either including it in a path or not, which would give a O(2^V) upper bound.

You can check my implementation of findAllPathsFromSourceToDestInDAG on my Gist along with some tests in FindAllPathsFromSourceToDestInDAGJTests.

[Java] Find index in circular array so that rolling sum never falls below zero

The title is actually a simplification of the following problem:

given a car with unlimited fuel capacity, an array indicating the amount of fuel that can be put in the car at a specific city i and another array indicating the amount of fuel necessary to travel from city i to the next, return the index of any city that allows making a round trip passing through all other cities in the order they appear.

Example:

gasAtCity = 1,1

gasForNextCity = 1,1

Any index is correct, start at city 0 we will the tank with 1 unit of fuel, we spend 1 unit of fuel and reach city 1 with 0 fuel left. We fill the tank there with 1 unit of fuel, spend 1 unit of fuel to go to the next city which bring us back to the start and end our journey.

gasAtCity = 1,1

gasForNextCity = 2,2

No city is correct since no matter where we start, we won't ever have enough fuel in the tank to reach the next city.

gasAtCity = 1,1,2

gasForNextCity = 1,2,1

Start from last city is the only possible choice as starting from earlier places will leave us at some point with not enough fuel to continue the trip.