Amazon Software Development Engineer (SDE) I interview questions

A average level DSA question.

Developers at Amazon are working on a new algorithm to sort a permutation of n integers using the bitwise AND operation. For an array of integers, arr and some chosen integer k, you can swap the i-th element with the j-th element only if (arri] & arr[j)) = k, where '&' represents the bitwise AND operation. Given an array arr of n integers which is a permutation of integers from 0 to n - 1, i.e. contains all integers from 0 to n - 1, find the value of the maximum non-negative integer k for which the array can be sorted using this algorithm. It can be shown that it is always possible to sort the array. Report O if the array is already sorted.