# AC java solution, Radix sort to sort in linear time O(32*n)

• For Simplicity I will use 4 bits to explain.
if we have {-6,-3,-5,1,2}

For 4 bits, the most significant bit will be used for sign. So binary representation will be

-6 -> 1010

-3 -> 1101

-5 -> 1011

1 -> 0001

2 -> 0010

we will create a map with keys 0,1 Mapping to LinkedList

[0] ->

[1] ->

looking bits from right

-6 -> 101 0

-3 -> 110 1

-5 -> 101 1

1 -> 000 1

2 -> 001 0

using the bits to map to respective key.

[0] -> -6 -> 2

[1] -> -3 -> -5 ->1

put them back into the array

-6 , 2 , -3 , -5 , 1

checking the next bits

-6 -> 10 1 0

2 -> 00 1 0

-3 -> 11 0 1

-5 -> 10 1 1

1 -> 00 0 1

using the bits to map to respective key.

[0] -> -3 -> 1

[1] -> -6 -> 2 ->-5

put them back into the array

-3 , 1 , -6 , 2 , -5

checking the next bits

-3 -> 1 1 0 1

1 -> 0 0 0 1

-6 -> 1 0 1 0

2 -> 0 0 1 0

-5 -> 1 0 1 1

using the bits to map to respective key.

[0] -> 1 -> -6-> 2 ->-5

[1] -> -3

put them back into the array

1,-6,2,-5,-3

The most significant bit is sign, we have to use it to bring all the negative integers before the positive. so if the most significant bit is 1 we map to 0 and vice-versa.

1 -> 0 0 0 1

-6 -> 1 0 1 0

2 -> 0 0 1 0

-5 -> 1 0 1 1

-3 -> 1 1 0 1

[0] -> -6 -> -5 -> -3

[1] -> 1 -> 2 ->

put them back into the array

-6, -5, -3, 1, 2

We have the array sorted in linear time, from here its one more loop to check for a sequence.

``````public int longestConsecutive(int[] nums) {
for(int i=0;i<32;i++){
for(int j=0;j<nums.length;j++){
if(i!=31){
int k = (nums[j]>>>i) & 1;
}
else{
int k = ((nums[j]>>>i) & 1 )^1;
}
}
Iterator itr = hm.entrySet().iterator();
int k=0;
while (itr.hasNext()) {
while(!lst.getValue().isEmpty()){
nums[k]=lst.getValue().pop();
k++;
}
}
}
int max=1;
int curr=1;
for(int i =0;i<nums.length-1;i++){
if(nums[i]==nums[i+1]){
continue;
}
if(nums[i]+1==nums[i+1]){
curr=curr+1;
max=Math.max(max,curr);
}
else{
curr=1;
}
}
return max;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.