Program to arrange an array in alternate positive and negative numbers
Let’s say, there is given an array arr, arrange the array in such a way that every positive number is followed by a negative number. If there are extra positive or negative numbers, arrange them in such a way that they occur at the end of the array.
Example
Input:
arr[] = {1, 2, 3, -4, -1, 4}
Output:
arr[] = {-4, 1, -1, 2, 3, 4}
Explanation:
The first negative number is -4. It appears at the start of the array and following it 1, which is the first positive number, so it is aligned next to -4.
Similarly, all the numbers are arranged in the array.
Input:
arr[] = {-5, -2, 5, 2, 4, 7, 1, 8, 0, -8}
Output:
arr[] = {-5, 5, -2, 2, -8, 4, 7, 1, 8, 0}
Explanation:
The first positive number next to -5 is 5, so -2 is shifted to the right. After arranging the alternate positive and negative elements, the extra positive elements are shifted to the right of the array.
- Naive approach: Iterate in the array
Find the first out of place of an element which is defined as an element which is negative and at odd index or an element that is positive and at even index.
After finding the out of place element find the element next to it with an opposite sign and rotate the right subarray between these two elements.
CPP code
#include <bits/stdc++.h>
using namespace std;
void rightrotatearray(int arr[], int n, int out_of_place, int current)
{ // function to rotate the right subarray
char tmp = arr[current];
for (int i = current; i > out_of_place; i--)
arr[i] = arr[i - 1];
arr[out_of_place] = tmp;
}
void rearrangealternate(int arr[], int n) // function to rearrange alternate elements
{
int out_of_place = -1; // current out of place is -1
for (int index = 0; index < n; index++)
{
if (out_of_place >= 0)
{
// find the item which must be moved into the
// out-of-place entry if out-of-place entry is
// positive and current entry is negative OR if
// out-of-place entry is negative and current
// entry is negative then right rotate
//
// [...-3, -4, -5, 6...] --> [...6, -3, -4,
// -5...]
// ^ ^
// | |
// outofplace --> outofplace
//
if (((arr[index] >= 0) && (arr[out_of_place] < 0))
|| ((arr[index] < 0)
&& (arr[out_of_place] >= 0)))
{
rightrotatearray(arr, n, out_of_place, index);
// the new out-of-place entry is now 2 steps
// ahead
if (index - out_of_place >= 2)
out_of_place = out_of_place + 2;
else
out_of_place = -1;
}
}
// if no entry has been flagged out-of-place
if (out_of_place == -1) {
// check if current entry is out-of-place
if (((arr[index] >= 0) && (!(index & 0x01)))
|| ((arr[index] < 0) && (index & 0x01))) {
out_of_place = index;
}
}
}
}
int main()
{
int arr[] = { -5, -2, 5, 2,
4, 7, 1, 8, 0, -8 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Given array is \n";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
rearrangealternate(arr, n);
cout << "Rearranged array is \n";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}
Output
Given array is -5 -2 5 2 4 7 1 8 0 -8 Rearranged array is -5 5 -2 2 -8 4 7 1 8 0
C code
#include <stdio.h>
void rightrotatearray(int arr[], int n, int out_of_place, int current)
{ // function to rotate the right subarray
char tmp = arr[current];
for (int i = current; i > out_of_place; i--)
arr[i] = arr[i - 1];
arr[out_of_place] = tmp;
}
void rearrangealternate(int arr[], int n) // function to rearrange alternate elements
{
int out_of_place = -1; // current out of place is -1
for (int index = 0; index < n; index++)
{
if (out_of_place >= 0)
{
// find the item which must be moved into the
// out-of-place entry if out-of-place entry is
// positive and current entry is negative OR if
// out-of-place entry is negative and current
// entry is negative then right rotate
//
// [...-3, -4, -5, 6...] --> [...6, -3, -4,
// -5...]
// ^ ^
// | |
// outofplace --> outofplace
//
if (((arr[index] >= 0) && (arr[out_of_place] < 0))
|| ((arr[index] < 0)
&& (arr[out_of_place] >= 0)))
{
rightrotatearray(arr, n, out_of_place, index);
// the new out-of-place entry is now 2 steps
// ahead
if (index - out_of_place >= 2)
out_of_place = out_of_place + 2;
else
out_of_place = -1;
}
}
// if no entry has been flagged out-of-place
if (out_of_place == -1) {
// check if current entry is out-of-place
if (((arr[index] >= 0) && (!(index & 0x01)))
|| ((arr[index] < 0) && (index & 0x01))) {
out_of_place = index;
}
}
}
}
int main()
{
int arr[] = { -5, -2, 5, 2,
4, 7, 1, 8, 0, -8 };
int n = sizeof(arr) / sizeof(arr[0]);
printf( "Given array is \n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
rearrangealternate(arr, n);
printf( "Rearranged array is \n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
Output
Given array is -5 -2 5 2 4 7 1 8 0 -8 Rearranged array is -5 5 -2 2 -8 4 7 1 8 0