ronith
5/30/2018 - 10:03 AM

## Rearrange positive and negative numbers with constant extra space

Given an array of positive and negative numbers, arrange them such that all negative integers appear before all the positive integers in the array without using any additional data structure like hash table, arrays, etc. The order of appearance should be maintained.

``````
#include <bits/stdc++.h>
using namespace std;

int rearrange(int a[],int n){
for(int i=0;i<n;i++){
if (a[i] < 0){
int t =a[i];
int j=i-1;
while(j>=0 && a[j] > 0){
a[j+1]=a[j];
j--;
}
a[j+1] = t;
}
}
}

int main(){
int n;
cout << "No.of elements \n";
cin >> n;
int a[n];
cout << "Enter the elements \n";
for (int i = 0;i<n;i++)
cin >> a[i];

rearrange(a,n);

for (int i=0;i<n;i++)
cout << a[i] << "  ";
}
``````
``````#include <bits/stdc++.h>
using namespace std;

int rearrange(vector <int> &a){
int n = a.size();
int count =0;
for(int i=0;i<n;i++){
if(a[i] < 0 && count!=i){
int t = a[i];
a.erase(a.begin() + i);
a.insert(a.begin()+count,t);
count++;
}
}
}

int main(){
cout << "Enter the no.of elements:";
int n;
cin >> n;
vector <int> a(n);
cout << "Enter the elements:";
for(int i=0;i<n;i++)
cin >> a[i];

rearrange(a);

for(int i=0;i<n;i++)
cout << a[i]<< "  ";
}
``````