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.

Rearrange positive and negative numbers with constant extra space-arrays.cpp
content_copyfile_download

#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] << "  ";
}
Rearrange positive and negative numbers with constant extra space-vectors.cpp
content_copyfile_download
#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]<< "  ";
}