# Rearrange Positive and Negative Numbers Alternatively in Array

Difficulty Level Easy
Array

## Problem Statement

In the “Rearrange Positive and Negative Numbers Alternatively in Array” problem we have given an array a[]. This array contains positive and negative integers. Rearrange the array in such a way that positive and negative are placed alternatively. Here, the number of positive and negative elements need not be equal.

Note: If there are more positive or negative elements then they appear at the end of the array.

## Input Format

The first and only one line containing an integer N.

Second-line containing N space-separated integers.

## Output Format

The first and only one line containing N space-separated integer.

## Constraints

• 1<=N<=10^5
• -10^9<=N<=10^9

## Example

```7
-5 -7 9 11 12 -15 17```
`-5 11 -15 17 -7 12 9`

Explanation: Rearranged positives and negatives in alternative positions and excess in the end.

```8
-4 -7 9 11 -16 13 3 -5```
`-16 11 -4 3 -7 13 -5 9`

Explanation: Rearranged positives and negatives in alternative positions.

## Algorithm

Here, we rearrange all positives at odd indices and negatives at even indices. The algorithm we follow is written below.

1. We modify the array such that all positives will be in the beginning of the array. And all the negative elements at the end.
[1, -2, 3, 4, 5, -6, 7, 8, -9] → [1, 3, 4, 5, 7, 8, -2, -6, -9]
2. We maintain two pointers i and j. If array[j] > 0 we move it to the front of the array by a swap with the first element. Else we move forward.
3. We initialize negative numbers start index as negative and positive as 0.
4. Increment the negative index by 1 and the positive index by 2. That means we swap every alternate positive number with the next negative number.
Data Structure Designing

## Implementation

### C++ Program for Rearrange Positive and Negative Numbers Alternatively in Array

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

//Rearrange function
void Rearrange(int array[], int n)
{
int i = -1;
//swap positive elements to the start of the array
for (int j = 0; j < n; j++)
{
if (array[j] > 0)
{
i = i + 1;
swap(array[i], array[j]);
}
}
//Initialize positive_index, negative_index
int positive_index = 0, negative_index = i + 1;
//Increment postive by 2 and negative by 1.
//swap elements after each increments and swap them.
//such that alternative elements will be changed
while (negative_index < n && negative_index > positive_index && array[negative_index] < 0)
{
swap(array[negative_index], array[positive_index]);
positive_index = positive_index + 2;
negative_index = negative_index + 1;
}
}

int main()
{
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
Rearrange(a,n);
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
return 0;
}
```

### Java Program for Rearrange Positive and Negative Numbers Alternatively in Array

```import java.util.Scanner;
class sum
{
//Rearrange function
public static void Rearrange(int array[], int n)
{
int i = -1;
//swap positive elements to the start of the array
for (int j = 0; j < n; j++)
{
if (array[j] > 0)
{
i = i + 1;
array[i] = (array[i] + array[j]) - (array[j] = array[i]);
}
}
//Initialize positive_index, negative_index
int positive_index = 0, negative_index = i + 1;
//Increment postive by 2 and negative by 1.
//swap elements after each increments and swap them.
//such that alternative elements will be changed
while (negative_index < n && negative_index > positive_index && array[negative_index] < 0)
{
array[negative_index] = (array[negative_index] + array[positive_index]) - (array[positive_index] = array[negative_index]);
positive_index = positive_index + 2;
negative_index = negative_index + 1;
}
}
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
int n = sr.nextInt();
int a[] = new int[n];
for(int i=0;i<n;i++)
{
a[i] = sr.nextInt();
}
Rearrange(a, n);
for(int i=0;i<n;i++)
{
System.out.print(a[i]+" ");
}
}
}```
```5
-1 -2 -3 4 5```
`-3 5 -1 4 -2`

## Complexity Analysis for Rearrange Positive and Negative Numbers Alternatively in Array

### Time Complexity

O(n) where n is the size of the given array. Here we simply traverse the whole array and perform some operations which take constant time.