1.
Introduction
1.1.
Problem statement
1.2.
Examples
2.
Brute Force Approach
2.1.
Algorithm
2.2.
Implementation in C++
2.2.1.
Complexity analysis
3.
Optimal Approach - 1
3.1.
Algorithm
3.2.
Implementation in C++
3.2.1.
Complexity analysis
4.
Optimal Approach-2
4.1.
Algorithm
4.2.
Implementation in C++
4.2.1.
Complexity analysis
5.
5.1.
Define an array.
5.2.
What is the time complexity of swapping two elements in an array?
5.3.
Why do we need arrays in C++?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Positive elements at even and negative at odd positions

Tarun Singh
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

This article will explain array rearrangement; we will learn how to manipulate an array by various methods to place positive elements at even and negative elements at odd positions. After reading this blog, you will learn array rearrangement techniques. We will discuss the algorithm for rearrangement with the given condition with its pseudocode, program, and time complexity.

Must Read, Array Implementation of Queue and  Rabin Karp Algorithm

Problem statement

We are given an array in this problem, and we must rearrange it so that all positive numbers are in even indexes and all negative numbers are in odd indexes. If the number of positive and negative values is uneven, we shall not transfer any additional values.

Examples

Input

``N=6, arr[]={1 -3 -2 4 5 -9}``

We want to get all positive numbers at the even index and all negative numbers at the odd index.

Output

``arr[] = {1, -3, 4, -2, 5, -9}``

Input

``N=6, arr[]={3, 9, 10, -3, -4, -7}``

Output

``arr[] = {3, -3, 9, -4, 10, -7} ``

Brute Force Approach

The brute force approach will be straightforward; in this, we will sort the whole array, and then we will make a copy array and place n/2 negative elements at even positions and n/2 odd elements at odd positions.

Algorithm

1. Take the input for the number of elements for the array.
2. Take the input for the elements of the array.
3. Sort the array in ascending order.
4. Doing the above step will divide the array into n/2 negative elements and n/2 positive elements, n being the size of the array.
5. We will make an empty array of the same as the input array.
6. We will initialize a variable k with zero; we will fill the empty array with firstly all odd elements and then with all even elements.
7. By doing so, we will get the positive element at even and the negative element at the odd position.

Implementation in C++

``````#include <bits/stdc++.h>
using namespace std;
int main()
{
// initializing and taking input for no of elements.
int n;
cin >> n;
int a[n];
// initializing and taking input for the array.
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
cout << "The size of the array: " << n << endl;
cout << "The array elements before the rearrangement: ";
for (int i = 0; i < n; i++)
{
cout << a[i] << " ";
}
cout << endl;
// sorting the array
sort(a, a + n);

// making another array of size n
int b[n];

// fixing all negative numbers
int k = 0;
for (int i = 1; i < n; i += 2)
{
b[i] = a[k];
k++;
}

// fixing all even numbers
for (int i = 0; i < n; i += 2)
{
b[i] = a[k];
k++;
}

// printing the modified array
cout << "The array elements after the rearrangement: ";
for (int i = 0; i < n; i++)
{
cout << b[i] << " ";
}
cout << endl;

return 0;
}``````

Input

``n=8, arr[]={11, 5, 6, -1, -6, -7, -1, 7}``

Output

``````The size of the array: 8
The array elements before the rearrangement: 11 5 6 -1 -6 -7 -1 7
The array elements after the rearrangement: 5 -7 6 -6 7 -1 11 -1``````

Complexity analysis

Time complexity

The time complexity is O(Nlog(N)), where n is the size of the array as we used sorting to separate negative and positive elements.

Space complexity

O(N) will be the space complexity as we have taken an extra array to make a copy of the array.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Optimal Approach - 1

This approach will be better than the brute force approach in terms of time complexity; the time complexity of the above approach is O(N log(N)) whereas, in this approach, the time complexity would be O(N), and the space complexity will be O(1).

Algorithm

1. Take two-pointers Even = 0 and odd = 1 as the initial values for two-pointers.
2. Iterate through the array's elements from index=0 to the last element i.e., while it is true, and stop if it gets out of range.
3. Increase the even pointer by 2 if the element at the even index is even or zero.
4. Increase the odd pointer by 2 if the element at the odd index is odd or zero.
5. Swap the items and increase both pointers by two if the element at the even index is odd and the element at the odd index is even.
6. For swapping, we'll utilize a built-in C++ method. If you desire, you can create your own swap function.
7. At the end of the loop, you will get the desired result.

In the C++ code below, we will make a separate function for rearrangement of the array for better understanding.

Implementation in C++

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

// function in which rearrangement of the array will be done
void solve(int arr[], int n)
{
// initilize even and odd pointer
int even = 0, odd = 1;

for (even, odd; even < n && odd < n;)
{
// check for positive at even positions
while (even < n && arr[even] >= 0)
even += 2;

// check for negative at odd positions
while (odd < n && arr[odd] <= 0)
odd += 2;

// Swap elements
if (even < n && odd < n)
swap(arr[even], arr[odd]);
}
}

int main()
{
// taking input for the size of array
int n;
cin >> n;
cout<<"The size of the array:";
cout<<n<<endl;
// initializing and taking input for the array.
int a[n];
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
cout<<"The array elements before rearrangement: ";
for (int i = 0; i < n; i++)
{
cout<<a[i]<<" ";
}
cout<<endl;
// calling our solve function
solve(a, n);
cout<<"The array elements after rearrangement: ";
for (int i = 0; i < n; i++)
{
cout << a[i] << " ";
}
cout<<endl;

return 0;
}``````

Input

``n=6, arr[]={1, 2, 3, -1, -2, -3}``

Output

``````The size of the array: 6
The array elements before rearrangement: 1 2 3 -1 -2 -3
The array elements after rearrangement:  1 -2 3 -1 2 -3``````

Complexity analysis

Time complexity
The time complexity is O(N), where n is the size of the array as we traverse the array only one time to swap the elements if needed.

Space complexity
O(1) will be the space complexity as we have taken only two pointers to traverse the array and haven't used any other data structure.

Also see, Morris Traversal for Inorder.

Optimal Approach-2

The aim is to discover a positive/negative element that is in the wrong place, then find the opposite sign element in the remaining array that is likewise in the wrong place, and then swap these two elements. The expected time complexity will be O(N), and space complexity will be O(1).

Algorithm

1. We take the input for the size of the array and elements of the array.
2. We make a void demo function for rearrangement of the array.
3. We make a SwapValue function to swap two numbers.
4. We loop through the array and check if the array element is positive or negative.
5. If it is positive and the index is an odd swap for the next negative and vice versa.
6. At the end of the loop, you will get the desired result.

Implementation in C++

``````// including header files
#include <bits/stdc++.h>
#include <cmath>
using namespace std;

// function to swap the misplaced elements
void swapValue(int *arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
return;
}

// function to print the array elements
void demo(int *arr, int n)
{
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return;
}

int main()
{
// initializing and taking input for no of elements.
int n;
cin >> n;
cout << "The size of the array:"
<< " " << n << endl;
// initializing and taking input for the array.
int arr[n];
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}

// printing array before modification
cout << "The array elements before rearrangement: ";
demo(arr, n);
for (int i = 0; i < n; i++)
{ // checking for correct placement of positive elements
if (arr[i] >= 0 && i % 2 == 1)
{

for (int j = i + 1; j < n; j++)
{
if (arr[j] < 0 && j % 2 == 0)
{
// swapping the misplaced elements
swapValue(arr, i, j);
break;
}
}
}
else if (arr[i] < 0 && i % 2 == 0)
{
// checking for correct placement of negative elements
for (int j = i + 1; j < n; j++)
{
if (arr[j] >= 0 && j % 2 == 1)
{
// swapping the misplaced elements
swapValue(arr, i, j);
break;
}
}
}
}

cout << "The array elements after rearrangement: ";
demo(arr, n);
return 0;
}``````

Input

``n=8, arr[]={9, 3, 4, -3, -8, -9, -3, 5}``

Output

``````No of elements in array: 8
Array before modification : 9 3 4 -3 -8 -9 -3 5
Array after modification: 9 -8 4 -3 3 -9 5 -3``````

Complexity analysis

Time complexity
The time complexity is O(N), where n is the size of the array as we traverse the array only one time to check for all positive and negative numbers.

Space complexity
O(1) will be the space complexity as we have only traversed the array and haven't used any extra array.

Define an array.

An array is a collection of similar data types stored in contiguous memory spaces. When declaring an array, the type of data must be specified together with the array name. The index of different elements in an array can be used to access them.

What is the time complexity of swapping two elements in an array?

It takes a constant time complexity to swap two elements of an array. We just maintain a temp variable to swap the elements and no loop is taken in action.

Why do we need arrays in C++?

Instead of defining distinct variables for each item, arrays are used to hold numerous values in a single variable.

Conclusion

In this article, we have analyzed how to rearrange an array such that positive elements are placed at even and negative at odd positions. We have gone through three different approaches to solving the problem; we have also discussed their algorithm, C++ code, and also their space and time complexity.

After reading about the array rearrangement, are you not feeling excited to read/explore more articles on the topic of array and data structures and algorithms? Don't worry; Coding Ninjas has you covered. To learn, see Data Structures and AlgorithmsCompetitive Programming.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Operating SystemUnix File SystemFile System RoutingFile Input/Output.JavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Live masterclass