Search

Rearrange positive and negative numbers alternatively

Given an integer array, rearrange it such that it contains positive and negative numbers at alternate positions. If the array contains more positive or negative elements, move them to the end of the array.


Example:

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

The idea is to use 0 as a pivot element and make one pass of the partition process. The resultant array will contain all positive integers to the end of the array and all negative integers at the beginning. Then swap alternate negative elements from the next available positive element until the end of the array is reached, or all negative or positive integers are exhausted.


Solution:

int partition(int A[])
{
 int j = 0;
 int pivot = 0; 
 for (int i = 0; i < A.length; i++)
 {
     if (A[i] < pivot)
     {
          swap(A[i], A[j]);
          j++;
     }
 }
 return j;
}
 
int rearrange(int A[], int size)
{
  int positive = partition(A, size);
  for (int negative = 0; (positive < size && negative < positive);   positive++, negative += 2) 
  {
    swap(A[negative], A[positive]);
  }
}


24 views0 comments

Recent Posts

See All

A string s is called good if there are no two different characters in s that have the same frequency. Given a string s, return the minimum number of characters you need to delete to make s good. The f

The numeric value of a lowercase character is defined as its position (1-indexed) in the alphabet, so the numeric value of a is 1, the numeric value of b is 2, the numeric value of c is 3, and so on.