Rearrange Array such that adjacent difference is odd - Coding

Given an arr[] containing distinct positive integers of length N(2 ≤ N), the task is to rearrange the array elements in such a way that each element has an odd absolute difference from its adjacent elements.

Note: If it is possible then print that arrangement of arr[] else print -1 in as output.

Examples:

Input: N = 2, arr[] = (6 5)
Output: 6 5
Explanation: There is only one pair (6, 5) present which has already abs difference as |6-5| = 1, which is odd, Therefore arr[] is already arranged in a manner following given conditions.

Input: N = 5, arr[] = (1, 3, 6, 7, 5)
Output: -1
Explanation: It can be verified that no arrangement of given elements are possible that follows the given conditions.

Input: N = 3, arr[] = {3, 1, 2}
Output: 1 2 3
Explanation: At index 1, |1 – 2| = 1
At index 2, |2 – 1| = 1
At index 3, |2 – 3| = 1
At index 4, |3 – 2| = 1
All adjacent pairs has odd differences. Therefore, arrangement is possible and output arrangement satisfies the given condition.

Approach: Implement the idea below to solve the problem

The problem can be solved via counting number of odd and even elements, Which are present initially in the arr[]. For understanding the problem let us see the all possible pair that can be made via an odd or an even element. There are total 4 possible arrangement having an odd and even element.

(Odd, Even) = |Odd – Even| = Odd

(Even, Odd) = |Even – Odd| = Odd

(Odd, Odd) = |Odd – Odd| = Even

(Even, Even) = |Even – Even| = Even

According to this observation, We came to know that for satisfying the given conditions in the problem the arrangement should be in such a way that even and odd elements should occur alternatively. So that their absolute adjacent difference would be odd.

If N is odd and consider ‘O’ represents odd and ‘E’ represent even then the arrangements should be

E, O, E, O, E or

O, E, O, E, O

And if N is even then arrangements should be

E, O, E, O or

O, E, O, E

So the conditions are:

If arr[] has even length, Then odd elements and even elements should be equal to N/2.

If arr[] has odd length, Then either odd elements or even elements should be equal to N/2+1.

Following are the steps to solve the problem:

Count the number of odd and even elements present in given arr[].
Check if the conditions are met or not, which is discussed above to find whether its arrangement is possible or not.
If an arrangement is possible then print it using the above pattern. Otherwise, print -1 as output.

Below is the implementation of the above approach.

C++

// C++ code to implement the approach

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

    // Function to find valid arrangement
    void rearrange(int arr[], int n)
    {

        // ArrayList to store odd elements
        vector<int> odd_ele;

        // Arraylist to store even elements
        vector<int> even_ele;

        // Odd element counter
        int odd = 0;

        // Even element counter
        int even = 0;

        // Loop for traversing on arr[]
        // and check counting
        // of odd and even elements
        for (int i = 0; i < n; i++) {

            if ((arr[i] & 1) == 1) {
                odd_ele.push_back(arr[i]);
                odd++;
            }
            else {
                even_ele.push_back(arr[i]);
                even++;
            }
        }

        // If length of array is even
        if (n % 2 == 0) {

            // For odd abs difference of
            // adjacent pairs equal no of
            // odd and even elements
            // should be there
            if (odd == (n / 2) && even == (n / 2)) {
                for (int i = 0; i < odd_ele.size(); i++) {
                    cout<<odd_ele[i] << " "
                                    << even_ele[i]
                                    << " ";
                }
            }
            else {
                cout<<"-1"<<endl;
            }
        }

        // When array length is odd
        else if (n % 2 != 0) {

            // For odd abs difference of
            // adjacent pairs either odd
            // or even should be ((n/2)+1)
            // to rearrange elements
            if (even == ((n / 2) + 1)
                || odd == ((n / 2) + 1)) {
                if (even == ((n / 2) + 1)) {
                    cout<<
                        even_ele[even_ele.size() - 1]
                        << " ";
                    for (int i = 0; i < odd_ele.size();
                        i++) {
                        cout<<
                            odd_ele[i] << " "
                            << even_ele[i] << " ";
                    }
                }
                else {

                    for (int i = 0; i < even_ele.size();
                        i++) {
                        cout<<
                            odd_ele[i] << " "
                            << even_ele[i] + " ";
                    }
                    cout<<
                        odd_ele[odd_ele.size() - 1];
                }
            }
            else {
                cout<<"-1"<<endl;
            }
        }
        cout<<endl;
    }

    // Driver code
    int main()
    {
        int arr[] = { 6, 1, 3, 4, 5, 2 };
        int N = sizeof(arr) / sizeof(arr[0]);

        // Function call
        rearrange(arr, N);
    }

// This code is contributed by Pushpesh Raj

Java

// Java code to implement the approach

import java.io.*;
import java.lang.*;
import java.util.*;

class GFG {

    // Function to find valid arrangement
    static void rearrange(int arr[], int n)
    {

        // ArrayList to store odd elements
        ArrayList<Integer> odd_ele = new ArrayList<>();

        // Arraylist to store even elements
        ArrayList<Integer> even_ele = new ArrayList<>();

        // Odd element counter
        int odd = 0;

        // Even element counter
        int even = 0;

        // Loop for traversing on arr[]
        // and check counting
        // of odd and even elements
        for (int i = 0; i < n; i++) {

            if ((arr[i] & 1) == 1) {
                odd_ele.add(arr[i]);
                odd++;
            }
            else {
                even_ele.add(arr[i]);
                even++;
            }
        }

        // If length of array is even
        if (n % 2 == 0) {

            // For odd abs difference of
            // adjacent pairs equal no of
            // odd and even elements
            // should be there
            if (odd == (n / 2) && even == (n / 2)) {
                for (int i = 0; i < odd_ele.size(); i++) {
                    System.out.print(odd_ele.get(i) + " "
                                     + even_ele.get(i)
                                     + " ");
                }
            }
            else {
                System.out.println(-1);
            }
        }

        // When array length is odd
        else if (n % 2 != 0) {

            // For odd abs difference of
            // adjacent pairs either odd
            // or even should be ((n/2)+1)
            // to rearrange elements
            if (even == ((n / 2) + 1)
                || odd == ((n / 2) + 1)) {
                if (even == ((n / 2) + 1)) {
                    System.out.print(
                        even_ele.get(even_ele.size() - 1)
                        + " ");
                    for (int i = 0; i < odd_ele.size();
                         i++) {
                        System.out.print(
                            odd_ele.get(i) + " "
                            + even_ele.get(i) + " ");
                    }
                }
                else {

                    for (int i = 0; i < even_ele.size();
                         i++) {
                        System.out.print(
                            odd_ele.get(i) + " "
                            + even_ele.get(i) + " ");
                    }
                    System.out.print(
                        odd_ele.get(odd_ele.size() - 1));
                }
            }
            else {
                System.out.println(-1);
            }
        }
        System.out.println();
    }

    // Driver code
    public static void main(String[] args)
        throws java.lang.Exception
    {
        int[] arr = { 6, 1, 3, 4, 5, 2 };
        int N = arr.length;

        // Function call
        rearrange(arr, N);
    }
}

Python3

# Python code to implement the approach

# Function to find valid arrangement
def rearrange(arr, n):

    # ArrayList to store odd elements
    odd_ele = []

    # Arraylist to store even elements
    even_ele = []

    # Odd element counter
    odd = 0

    # Even element counter
    even = 0

    #  Loop for traversing on arr[]
    #  and check counting
    #  of odd and even elements
    for i in range(n):

        if ((arr[i] & 1) == 1):
            odd_ele.append(arr[i])
            odd += 1

        else:
            even_ele.append(arr[i])
            even += 1

    # If length of array is even
    if (n % 2 == 0):

        # For odd abs difference of
        # adjacent pairs equal no of
        # odd and even elements
        # should be there
        if (odd == (n / 2) and even == (n / 2)):
            for i in range(len(odd_ele)):
                print(odd_ele[i], end=" ")
                print(even_ele[i], end=" ")

        else:
            print("-1")

    # When array length is odd
    elif (n % 2 != 0):

        # For odd abs difference of
        # adjacent pairs either odd
        # or even should be ((n/2)+1)
        # to rearrange elements
        if (even == ((n / 2) + 1) or odd == ((n / 2) + 1)):
            if (even == ((n / 2) + 1)):
                print(even_ele[len(even_ele) - 1], end=" ")
                print(odd_ele[len(odd_ele) - 1], end=" ")

                for i in range(len(odd_ele)):
                    print(odd_ele[i], end=" ")
                    print(even_ele[i], end=" ")

            else:

                for i in range(len(even_ele)):
                    print(odd_ele[i], end=" ")
                    print(even_ele[i], end=" ")

                print(odd_ele[len(odd_ele) - 1])

        else:
            print("-1")

    print()

# Driver code
arr = [6, 1, 3, 4, 5, 2]
N = len(arr)

# Function call
rearrange(arr, N)

# This code is contributed by Samim Hossain Mondal.

C#

// C# code to implement the approach
using System;
using System.Collections;
using System.Collections.Generic;

public class GFG {

  // Function to find valid arrangement
  static void rearrange(int[] arr, int n)
  {

    // ArrayList to store odd elements
    ArrayList odd_ele = new ArrayList();

    // Arraylist to store even elements
    ArrayList even_ele = new ArrayList();

    // Odd element counter
    int odd = 0;

    // Even element counter
    int even = 0;

    // Loop for traversing on arr[]
    // and check counting
    // of odd and even elements
    for (int i = 0; i < n; i++) {

      if ((arr[i] & 1) == 1) {
        odd_ele.Add(arr[i]);
        odd++;
      }
      else {
        even_ele.Add(arr[i]);
        even++;
      }
    }

    // If length of array is even
    if (n % 2 == 0) {

      // For odd abs difference of
      // adjacent pairs equal no of
      // odd and even elements
      // should be there
      if (odd == (n / 2) && even == (n / 2)) {
        for (int i = 0; i < odd_ele.Count; i++) {
          Console.Write(odd_ele[i] + " "
                        + even_ele[i] + " ");
        }
      }
      else {
        Console.WriteLine(-1);
      }
    }

    // When array length is odd
    else if (n % 2 != 0) {

      // For odd abs difference of
      // adjacent pairs either odd
      // or even should be ((n/2)+1)
      // to rearrange elements
      if (even == ((n / 2) + 1)
          || odd == ((n / 2) + 1)) {
        if (even == ((n / 2) + 1)) {
          Console.Write(
            even_ele[even_ele.Count - 1] + " ");
          for (int i = 0; i < odd_ele.Count;
               i++) {
            Console.Write(odd_ele[i] + " "
                          + even_ele[i] + " ");
          }
        }
        else {

          for (int i = 0; i < even_ele.Count;
               i++) {
            Console.Write(odd_ele[i] + " "
                          + even_ele[i] + " ");
          }
          Console.Write(
            odd_ele[odd_ele.Count - 1]);
        }
      }
      else {
        Console.WriteLine(-1);
      }
    }
    Console.WriteLine();
  }

  static public void Main()
  {

    // Code
    int[] arr = { 6, 1, 3, 4, 5, 2 };
    int N = arr.Length;

    // Function call
    rearrange(arr, N);
  }
}

// This code is contributed by lokeshmvs21.

Javascript

// JavaScript code for the above approach

// Function to find valid arrangement
function rearrange(arr, n)
{

    // ArrayList to store odd elements
    let odd_ele = [];

    // Arraylist to store even elements
    let even_ele = [];

    // Odd element counter
    let odd = 0;

    // Even element counter
    let even = 0;

    // Loop for traversing on arr[]
    // and check counting
    // of odd and even elements
    for (let i = 0; i < n; i++) {

        if ((arr[i] & 1) == 1) {
            odd_ele.push(arr[i]);
            odd++;
        }
        else {
            even_ele.push(arr[i]);
            even++;
        }
    }

    // If length of array is even
    if (n % 2 == 0) {

        // For odd abs difference of
        // adjacent pairs equal no of
        // odd and even elements
        // should be there
        if (odd == Math.floor(n / 2)
            && even == Math.floor(n / 2)) {
            for (let i = 0; i < odd_ele.length; i++) {
                console.log(odd_ele[i] + " " + even_ele[i]
                            + " ");
            }
        }
        else {
            console.log(-1);
        }
    }

    // When array length is odd
    else if (n % 2 != 0) {

        // For odd abs difference of
        // adjacent pairs either odd
        // or even should be ((n/2)+1)
        // to rearrange elements
        if (even == (Math.floor(n / 2) + 1)
            || odd == (Math.floor(n / 2) + 1)) {
            if (even == (Math.floor(n / 2) + 1)) {
                console.log(even_ele[even_ele.length - 1]
                            + " ");
                for (let i = 0; i < odd_ele.length; i++) {
                    console.log(odd_ele[i] + " "
                                + even_ele[i] + " ");
                }
            }
            else {

                for (let i = 0; i < even_ele.length; i++) {
                    console.log(odd_ele[i] + " "
                                + even_ele[i] + " ");
                }
                console.log(odd_ele[odd_ele.length - 1]);
            }
        }
        else {
            console.log(-1);
        }
    }
    console.log(" ");
}

// Driver code

let arr = [ 6, 1, 3, 4, 5, 2 ];
let N = arr.length;

// Function call
rearrange(arr, N);

// This code is contributed by Potta Lokesh

Output

1 6 3 4 5 2

Time Complexity: O(N)
Auxiliary Space: O(N)

Reffered: https://www.geeksforgeeks.org

Arrays

Related
Count pairs such that difference between them and indices are different
Minimum cost to make Array equal by increment/decrementing elements
Minimum jumps to same value or adjacent to reach end of Array
Minimize division by 2 to make at least K even numbers in given Array
Partition Array into 3 Subarrays to maximize the product of sums

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	12