With less memory use, you need to reorder the elements of the array

Question

I have a recent interview question, reordering elements in an array with minimal memory usage. Do not use any additional variables 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 exchange between elements (first with the last, second with the 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 problem here is replacing array elements without using the temp variable. You can use the XOR(^) operation as follows:

To replace a and b :

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

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

Answer 3

It looks like the elements are just upside down. You can do this without additional arrays, with any swap implementation that you want to use:

 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 the unchanged storage "by calculating the sum and subtracting it with XORing, etc. However, never do this in production. A useless interview trick invented at a time when hardware engineers doubled the programmers more often than now (I saw this problem formulated in terms of hardware logic gates about 25 years ago).