spt
BAN USERanother simple solution that works in O(n) time.
Traverse the array and find the right location. Eg: if an element is located at position 2 (array starts at 0) its right position would be 2*2 mod maxIndexofArray = 4. Replace the value at position 4 and and find the right position for this new element. Keep track of the start index to make sure we dont do into an infinite loop. Get the next untouched element and repeat.
pseudo code:
startIndex,curIndex =0; maxIndexofArray=lenghtofArray-1;
while (curIndex != maxArrayofIndex)
{
do {
curIndex = curIndex*2;
curVal = array[curIndex];
array[curIndex] = prevVal;
prevVal = curVal;
}while (curIndex != startIndex)
curIndex = (curIndex *2) + 1
startIndex = curIndex;
prevVal = array[curIndex];
}
the solution needs to be an "in place algorithm", cant use an additional array
- spt January 08, 2008