CODEWITHSUNDEEP
arraysalgorithmlanguage-agnostic
Ritesh Mahato
Ritesh Mahato

Reputation: 631

Rearrange an array so that arr[i] becomes arr[arr[i]] with O(1) extra space

The task is to rearrange an array so that arr[i] becomes arr[arr[i]] with O(1) extra space.

Example:

2 1 3 5 4 0

becomes:

3 1 5 0 4 2

I can think of an O(n²) solution. An O(n) solution was presented here:

  1. Increase every array element arr[i] by (arr[arr[i]] % n)*n.
  2. Divide every element by n.

But this is very limited as it will cause buffer overflow.

Can anyone come up with an improvement upon this?

Upvotes: 12

Views: 3018

Answers (2)

Ranger7
Ranger7

Reputation: 11

//Traverse the array till the end. //For every index increment the element by array[array[index] % n]. To get //the ith element find the modulo with n, i.e array[index]%n. //Again traverse to end //Print the ith element after dividing the ith element by n, i.e. array[i]/n

   class Rearrange  
{ 
       void rearrange(int arr[], int n)  
    { 
        for (int i = 0; i < n; i++) 
            arr[i] += (arr[arr[i]] % n) * n; 
  
        for (int i = 0; i < n; i++) 
            arr[i] /= n; 
    } 
  
    void printArr(int arr[], int n)  
    { 
        for (int i = 0; i < n; i++) 
            System.out.print(arr[i] + " "); 
        System.out.println(""); 
    } 
  
    public static void main(String[] args)  
    { 
        Rearrange rearrange = new Rearrange(); 
        int arr[] = {6, 4, 9, 2, 5, 7}; 
        int n = arr.length; 
  
        System.out.println("Given Array is :"); 
        rearrange.printArr(arr, n); 
  
        rearrange.rearrange(arr, n); 
  
        System.out.println("Modified Array is :"); 
        rearrange.printArr(arr, n); 
    } 
}

Upvotes: 0

גלעד ברקן
גלעד ברקן

Reputation: 23955

If the values in the array are all positive (or all negative), one way to avoid overflow could be to run the permutation cycles and use the integer sign to mark visited indexes. (Alternatively, if the array length is smaller than 2^(number of bits for one array element - 1), rather than use the sign, we could shift all the values one bit to the left and use the first bit to mark visited indexes.) This algorithm results in both less iterations and less modifications of the original array values during run-time than the algorithm you are asking to improve.

JSFiddle: http://jsfiddle.net/alhambra1/ar6X6/

JavaScript code:

function rearrange(arr){
    var visited = 0,tmp,indexes,zeroTo

    function cycle(startIx){
        tmp = {start: startIx, value: arr[startIx]}
        indexes = {from: arr[startIx], to: startIx}

        while (indexes.from != tmp.start){
            if (arr[indexes.from] == 0)
                zeroTo = indexes.to
            if (indexes.to == visited){
                visited++
                arr[indexes.to] = arr[indexes.from]
            } else {
                arr[indexes.to] = -arr[indexes.from]
            }
            indexes.to = indexes.from
            if (indexes.from != tmp.start)
                indexes.from = arr[indexes.from]
        }

        if (indexes.to == visited){
            visited++
            arr[indexes.to] = tmp.value
        } else {
            arr[indexes.to] = -tmp.value
        }
    }

    while (visited < arr.length - 1){
        cycle(visited)

        while (arr[visited] < 0 || visited == zeroTo){
            arr[visited] = -arr[visited]
            visited++
        }
    }

    return arr
}

Upvotes: 1

Related Questions