Rearrange positive and negative numbers in O(n) time

Question -

An array contains both positive and negative numbers in random order. Rearrange the array element so that positive and negative numbers are placed alternately. Number of positive negative numbers need not be equal. If there are more positive numbers they appear at the end of the array. If there are more negative numbers , they too appear in the end of the array.

Example - 

Input : a[] = {-1, 2, -3, 4, -5, 6, -7, 8, 9}

Output : {2, -1, 4, -3, 5, -7, 6, 8, 9}

Approach - 

first we calculate the number of positive and negative numbers, now create two temporary array, one for positive number and one for negative number. now print temporary array's element alternately.

Implementation - 

//rearrange array like as alternate positive and negative

#include<iostream>

using namespace std;

int main()

{

    int n;

    cout<<"Enter the size of array : ";cin>>n;

    int arr[n];

    cout<<"Enter array element : "<<endl;

    for(int i=0;i<n;i++)

    cin>>arr[i];

    //count positive and negative number in array

    int positive=0,negative=0;

    for(int i=0;i<n;i++){

        if(arr[i]>=0)

        positive++;

        else

        negative++;

        

    }

    int narr[negative];

    int parr[positive];

    int j=0,k=0;

    for(int i=0;i<n;i++){

        if(arr[i]>=0){

        parr[j]=arr[i];

        j++;

        }

        else{

        narr[k]=arr[i];

        k++;

        }

    }

    j=0,k=0;

    for(int i=0;i<n;i++){

        if(i<positive)

        cout<<parr[i]<<" ";

        

        if(i<negative)

            cout<<narr[i]<<" ";

        

        

        

    }

}

code on compiler

Time complexity - O(n)