Rearrange an array such that it contains alternate positive and negative numbers

Posted in

Rearrange an array such that it contains alternate positive and negative numbers
maazbinasad

Maaz Bin Asad
Last updated on March 29, 2024

    Problem

    You are given an array. Rearrange the elements such that positive and negative integers occur at alternate positions.

    Sample Input

    [9, -3, 5, -2, -8, -6, 1, 3]

    Sample output

    5, -2, 9, -6, 1, -8, 3, -3

    Explanation

    We can make 0 as our pivot element and partition the array into negative elements on the left side of the pivot and positive elements on the right side of the pivot using the approach of the quicksort algorithm.

    Later, we can swap alternate negative elements with positive elements until all positive and negative elements are exhausted.

    C++

    #include<bits/stdc++.h>
    usingnamespacestd;
    intpartitionHelper(int arr[], int n)
    {
     int j = 0;
     int pivot = 0; 
     for (int i = 0; i < n; i++)
     {
     if (arr[i] < pivot)
     {
     swap(arr[i], arr[j]);
     j++;
     }
     }
     return j;
    }
    intsolve(int arr[], int n)
    {
     int p = partitionHelper(arr, n);
     for (int i = 0; (p < n && i < p); p++, i += 2) {
     swap(arr[i], arr[p]);
     }
    }
    intmain()
    {
     int arr[] = {1, 2, -4, -5};
     int n = sizeof(arr)/sizeof(arr[0]);
     solve(arr, n);
     for (int i = 0; i < n; i++) {
     cout << " " << arr[i];
     }
     return0;
    }

    Output

    1 -5 2 -4

    C

    #include<stdio.h>
    voidswap(int *x, int *y)
    {
     int temp = *x;
     *x = *y;
     *y = temp;
    }
    intpartitionHelper(int arr[], int n)
    {
     int j = 0;
     int pivot = 0; 
     for (int i = 0; i < n; i++)
     {
     if (arr[i] < pivot)
     {
     swap(&arr[i], &arr[j]);
     j++;
     }
     }
     return j;
    }
    intsolve(int arr[], int n)
    {
     int p = partitionHelper(arr, n);
     for (int i = 0; (p < n && i < p); p++, i += 2) {
     swap(&arr[i], &arr[p]);
     }
    }
    intmain()
    {
     int arr[] = {1, 2, -4, -5};
     int n = sizeof(arr)/sizeof(arr[0]);
     solve(arr, n);
     for (int i = 0; i < n; i++) {
     printf("%d ",arr[i]);
     }
     return0;
    }

    Output

    1 -5 2 -4

    Python

    defpartitionHelper(arr):
     j = 0
     pivot = 0 
     for i in range(len(arr)):
     if arr[i] < pivot:
     temp = arr[i]
     arr[i] = arr[j]
     arr[j] = temp
     j = j + 1
     return j
    defsolve(arr):
     p = partitionHelper(arr)
     n = 0
     while len(arr) > p and p > n:
     temp = arr[n]
     arr[n] = arr[p]
     arr[p] = temp
     p = p + 1
     n = n + 2
    arr = [1,2,-5,-4]
    solve(arr)
    print(arr)

    Output

    [1, -4, 2, -5]

    People are also reading:

    Leave a Comment on this Post

    0 Comments