With less memory usage need to reorder the array elements

Question

I have a recent interview question, reordering of elements in an array with minimum memory usage. Not to use any additional variable or collections etc.

input:

value   65 7 1 68 90
index    0 1 2  3  4

output:

value   90 68 1 7 65
index    0  1 2 3  4

Answer 1

You can use XOR to swap between elements (first with last, second with second from the end, etc) as follows:

int [] arr = {65, 7, 1, 68, 90};
for(int i=0; i<arr.length/2; i++){
    // the following 3 lines swap between elements arr[i] and arr[arr.length-i-1]
    arr[i] = arr[i] ^ arr[arr.length-i-1];
    arr[arr.length-i-1] = arr[i] ^ arr[arr.length-i-1];
    arr[i] = arr[i] ^ arr[arr.length-i-1];
}

for(int i=0; i<arr.length; i++){
    System.out.print(arr[i]+" ");
}

OUTPUT

90 68 1 7 65 

Answer 2

The main issue here is swapping array elements without using temp variable. You can make use of XOR(^) operation like this:

For swapping a and b:

int a = 4;
int b = 5;
a ^= b
b ^= a
a ^= b

Now, you just need to iterate over the array from index = 0 to index = length / 2, and swap elements at beginning and end.

Answer 3

It looks like the elements are simply reversed. You can do this without additional arrays, with whatever implementation of the swap that you feel like using:

int b = 0, e = array.length-1;
while (b < e) {
    array.swap(b, e);
    b = b + 1;
    e = e - 1;
}

For integers you can use "storageless swap" by computing a sum and subtracting, by XORing, etc. One would never do that in production, though - it's a useless interview trick invented at the time when hardware engineers doubled as programmers more often than they do now (I saw this problem formulated in terms of hardware logical gates some 25 years ago).