In C++, rearrange positive and negative numbers in O(n) time complexity and O(1) extra space

We get an array of integer type containing positive and negative numbers, say, arr[] of any given size. The task is to rearrange an array so that all positive and negative numbers should be in alternating positions and if there are extra positive or negative numbers elements and they will be placed at the end of the array.

Let us look at various input and output scenarios for this situation -

Input − int arr[] = {4, 2, -1, -1, 6, -3}

Output− Rearrange positive and negative numbers in O(n) time and O(1) time. The extra space is: 2 - 1 6 -1 4 -3

Explanation− We get an integer array of size 6 containing positive and negative elements. Now we will rearrange the array so that all positive elements sum Negative elements are at alternate positions and all extra elements will be added to the end of the array i.e. 2 -1 6 -1 4 -3 will be the final result

Input

Input

strong>− int arr[] = {-1, -2, -3, 1, 2, 3, 5, 5, -5, 3, 1, 1}

Output strong>− Rearrange positive and negative numbers in O(n) time and O(1) extra space as: 2 - 2 3 -5 5 -3 5 -1 1 3 1 1

Explanation - We get an integer array of size 12 containing positive and negative elements. Now we will rearrange the array so that all positive and negative elements are in alternating positions and all extra elements will be added to the end of the array i.e. 2 -2 3 -5 5 -3 5 -1 1 3 1 1 for the final Result

The method used in the program below is as follows

• Enter an integer array input elements and calculate the size of the array.

• Print the array before performing the rearrange operation using a FOR loop.

• Call the function Rearrangement(arr, size) by passing the array and array size as parameters.

• Internal function Rearrangement(arr, size)

  • Declare temporary integer variable, that is, temp is -1, positive number is temp 1, Negative numbers are 0.

  • Start looping from i to 0 until i is less than the size of the array. Inside the loop, check IF arr[i] is less than 0, then increment temp by 1 and call the built-in method of C STL, which is swap(arr[temp], arr[i]) and pass arr[temp] and arr[i] as parameters.

  • Start looping, WHILE positive number is less than the array size AND negative number is less than the positive number AND arr[negative number] is less than 0. Within the loop, calls are exchanged by passing arr[negative] and arr[positive] as arguments. Add 1 to a positive number and set negative 2 to a negative number.

• Print the result.

Example

#include <bits/stdc++.h>
using namespace std;
void Rearrangement(int arr[], int size){
   int temp = -1;
   for(int i = 0; i < size; i++){
      if (arr[i] < 0){
         temp++;
         swap(arr[temp], arr[i]);
      }
   }
   int positive = temp + 1;
   int negative = 0;
   while(positive < size && negative < positive && arr[negative] < 0){
      swap(arr[negative], arr[positive]);
      positive++;
      negative = negative + 2;
   }
}
int main(){
   int arr[] = {4, 2, -1, -1, 6, -3};
   int size = sizeof(arr)/sizeof(arr[0]);
   //calling the function to rearrange the array
   Rearrangement(arr, size);
   //print the array after rearranging the values
   cout<<"Rearrangement of positive and negative numbers in O(n) time and O(1) extra space is: ";
   for(int i = 0; i < size; i++){
      cout<< arr[i] << " ";
   }
   return 0;
}

Output

If we run the above code it will generate the following output

Rearrangement of positive and negative numbers in O(n) time and O(1) extra space is: 2 -1 6 -1 4 -3

The above is the detailed content of In C++, rearrange positive and negative numbers in O(n) time complexity and O(1) extra space. For more information, please follow other related articles on the PHP Chinese website!