Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Rearrange the Array of Given Range N, such that A[i]=i

Algo­rithmsRearrange the Array of Given Range N, such that A[i]=i.

Objec­tive: Given a array of length N, in which ele­ments are in the range of 1 to N. All ele­ments may not present in the array. If ele­ment is not present , there will be –1 present in the array. Rearrange the array such that A[i]=i and if i is not present, dis­play –1 at that place. See example

Exam­ple:

Rearrange the Array of Given Range N, such that A[i]=i

Rearrange the Array of Given Range N, such that A[i]=i

Approach: — Time Com­plex­ity –O(N), Space Com­plex­ity — O(1)

  1. Nav­i­gate the array.
  2. Check if ele­ment is –1, if yes then ignore it.
  3. If ele­ment is not –1, Check if its at it cor­rect posi­tion (i=A[i]), If yes then ignore it.
  4. If ele­ment is not –1, and ele­ment is not at its cor­rect posi­tion (i!=A[i]) then We need to place it to its cor­rect posi­tion but there are two conditions
    1. Either A[i] is vacate, means A[i]=-1, then just put A[i]=i .
    2. OR A[i] is not vacate, means A[i]=x, then int y=x put A[i]=i. Now we need to place y to its cor­rect place, so repeat from step 3. .

Code:


Out­put:

Fixed Indexed Array [-1, 1, 2, 3, 4, -1, 6, -1, -1, 9]
Fixed Indexed Array [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

You may also like...