2

Suppose we have an array having 0 to n-1 distinct integers

example

{2,1,4,3,5,0}

our goal is to modify this array such that a[0] becomes a[a[0]] means a[0] has value 2 here so a[0] = a[2] and so on.

Having the following output :

{4,1,5,3,0,2}.

Three things are to be noted here that:

  1. positions have range 0 to n-1 and values have range 0 to n-1 too (obviously).
  2. no extra array or link list or any data structure should be taken.
  3. should have time complexity O(n).

1 Answer 1

0

Here's the idea:

You can store the original and desired numbers in the same array position by keeping the original one and pushing the new one as a base n number.

That way, to extract the original number we just need to compute the modulo n operation:

original = array[index] % array.length

And we can get the target value dividing by the array length

target = array[index] / array.length

That way we won't require additional memory and we will be able to do it in two passes O(2n) complexity.

The algorithm is pretty straightforward (implemented in python):

def self_permute(arr):
    length = len(arr)
    for i in range(length):
        if arr[i] < i:
            arr[i] += (arr[arr[i]] % length) * length
        else:
            arr[i] += arr[arr[i]] * length

    for i in range(length):
        arr[i] /= length

    return arr

a = [2,1,4,3,5,0]
print self_permute(a)
1
  • Awsome thinking man!!!!! 2 things time complexity will be 3n as n time for calculation of Length too and i dont think if else is required. arr[i] += (arr[arr[i]] % length) * length will work normally if the value is not processed too. thanks anyway
    – oneranker
    Nov 19, 2015 at 15:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.