Rearrange the element such that array[i] = i

C++ implementation to rearrange the element such that array[i] = i using multiple approaches.
Submitted by Vikneshwar GK, on March 04, 2022

Consider an integer array, of size n, that has elements either from the range 0 to n-1 or -1. The task at hand is to arrange the array in such a way that the array[i] = i. If the corresponding element is not present, then fill the position with -1.

Example:

```Input:
array[]= {2, 3, -1, 4, -1}

Output:
array[] = {-1, -1, 2, 3, 4}

Input:
array[]= {2, 1, -1, 0, 4, -1}

Output:
array[] = {0, 1, 2, -1, 4, -1}
```

Solution 1: Using Another Array

This method involves using an additional array and inserting the elements from the original array into the new array following the constraint of the given problem statement.

• Declare a new array of size n
• Iterate through the original array and place the element other than -1 in their corresponding position in the new array
• Now, iterate the new array and check if newarray[i] = i
• If yes, set array[i] = i, else array[i] = -1
• Print the array

C++ Implementation:

```#include <iostream>
#include <unordered_set>

using namespace std;

// Function to rearrange the array
void rearrangeArray(int array[], int length)
{
int newarray[length];

for (int i = 0; i < length; i++) {
// copy element into new array
if (array[i] != -1) {
newarray[array[i]] = array[i];
}
}
for (int i = 0; i < length; i++) {
// copy back from new array to original array
if (newarray[i] != i) {
array[i] = -1;
}
else {
array[i] = i;
}
}
}

// Function to print the array
void printArray(int array[], int length)
{
for (int i = 0; i < length; i++) {
cout << array[i] << " ";
}
}

// Main function
int main()
{
int array[100], N, element;

cout << "Enter Number of elements: ";
cin >> N;

for (int i = 0; i < N; i++) {
cout << "Enter element " << i + 1 << ": ";
cin >> array[i];
}
rearrangeArray(array, N);
printArray(array, N);

return 0;
}
```

Output:

```Enter Number of elements: 5
Enter element 1: 2
Enter element 2: 3
Enter element 3: -1
Enter element 4: 4
Enter element 5: -1
-1 -1 2 3 4
```

Time Complexity: O(n), where n is the length of the array.

Solution 2: Using Set

Set is a C++ STL container that stores unique elements in a sorted manner. We will use these features to facilitate our problem statement. It involves the following steps.

• Iterate the array and store the elements in the set
• Now iterate the array again and check if array[i] = i
• If not, check whether i is present in the set
• If present, set array[i] = i, else set it to -1
• Print the array

C++ Implementation:

```#include <iostream>
#include <unordered_set>

using namespace std;

// Function to rearrange the array
void rearrangeArray(int array[], int length)
{
// declare unordered set
unordered_set<int> s;

// copy array element to set
// skip -1
for (int i = 0; i < length; i++) {
if (array[i] != -1)
s.insert(array[i]);
}

for (int i = 0; i < length; i++) {
// if i present if set
if (s.find(i) != s.end()) {
array[i] = i;
}
// if i not found
else {
array[i] = -1;
}
}
}

// Function to print the array
void printArray(int array[], int length)
{
for (int i = 0; i < length; i++) {
cout << array[i] << " ";
}
}

// Main function
int main()
{
int array[100], N, element;

cout << "Enter Number of elements: ";
cin >> N;

for (int i = 0; i < N; i++) {
cout << "Enter element " << i + 1 << ": ";
cin >> array[i];
}
rearrangeArray(array, N);
printArray(array, N);

return 0;
}
```

Output:

```Enter Number of elements: 6
Enter element 1: -1
Enter element 2: 0
Enter element 3: 4
Enter element 4: 2
Enter element 5: -1
Enter element 6: 1
0 1 2 -1 4 -1
```

Time Complexity: O(n), where n is the length of the array.

Solution 3: Using Swap

This method involves iterating through the array and swapping the array elements until the given constraint in the problem is satisfied. It involves the following steps.

• Iterate the array
• If array[i] != -1 and array[i] != i, swap the element with array[array[i]] and decrement the loop counter
• Print the array

C++ Implementation:

```#include <iostream>
#include <unordered_set>

using namespace std;

// Function to rearrange the array
void rearrangeArray(int array[], int length)
{
int temp;
for (int i = 0; i < length; i++) {
if (array[i] != -1 && array[i] != i) {
temp = array[i];
array[i] = array[array[i]];
array[temp] = temp;
i--;
}
}
}

// Function to print the array
void printArray(int array[], int length)
{
for (int i = 0; i < length; i++) {
cout << array[i] << " ";
}
}

// Main function
int main()
{
int array[100], N, element;

cout << "Enter Number of elements: ";
cin >> N;

for (int i = 0; i < N; i++) {
cout << "Enter element " << i + 1 << ": ";
cin >> array[i];
}

rearrangeArray(array, N);
printArray(array, N);

return 0;
}
```

Output:

```Enter Number of elements: 10
Enter element 1: 1
Enter element 2: 2
Enter element 3: 3
Enter element 4: 4
Enter element 5: 5
Enter element 6: 6
Enter element 7: 7
Enter element 8: -1
Enter element 9: 9
Enter element 10: 0
0 1 2 3 4 5 6 7 -1 9
```

Time Complexity: O(n), where n is the length of the array.

Comments and Discussions!

Student's Section
Subscribe

Copyright © 2024 www.includehelp.com. All rights reserved.