Rearrange array elements into alternate even-odd sequence by anticlockwise rotation of digits

0 0 9 minutes read

Given an array arr[] consisting of N positive integers, the task is to rotate the digits of array elements in an anti-clockwise direction such that elements of the array elements are in alternate even-odd or odd-even form. If multiple solutions exists, then print any one of them. Otherwise, print -1.

Examples:

Input: arr[] = { 143, 251, 534, 232, 854 }
Output: 143 512 345 232 485
Explanation:
Rotating arr[1] by 1 in anticlockwise direction modifies arr[1] to 512.
Rotating arr[2] by 1 in anticlockwise direction modifies arr[2] to 345.
Rotating arr[4] by 2 in anticlockwise direction modifies arr[4] to 485.

Input: arr[] = { 44, 23, 21, 33, 14 }
Output: 44 23 12 33 14

Approach: The above problem can be solved by either modifying the first array element to an odd number or an even number. The array element can be modified by converting the number into a string and then rotate the characters of the string left as needed. Follow the steps below to solve the problem:

Rearrange the first array element as an even number and check if the remaining array elements can be rearranged into odd-even alternately or not. If found to be true, then rearrange the array elements into odd-even alternately and print the array elements.
Otherwise, rearrange the first array element as an odd number and check if the remaining array elements can be rearranged into even-odd alternately or not. If found to be true, then rearrange the remaining array elements into even-odd alternately and print the array elements.
Otherwise, print -1.

Below is the implementation of the above approach:

C++

// c++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Utility function to rotate the digits of
// array elements such that array elements are
// in placed even-odd or odd-even alternately
bool is_possible(vector<int>& arr, bool check)
{
 
    // Checks if array can be converted
    // into even-odd or odd-even form
    bool exists = true;
 
    // Store array elements
    vector<int> cpy = arr;
    bool flag;
    // Traverse the array
    for (int i = 0; i < arr.size(); i++) {
 
        // Check if arr[i] is already
        // at correct position
        if (arr[i] % 2 == check) {
            check = !(check);
            continue;
        }
 
        // Checks if it is possible
        // to modify the number arr[i]
        // by rotating the digits of
        // the number anticlockwise
        flag = false;
 
        // Stores the number arr[i] as
        // string
        string strEle = to_string(arr[i]);
 
        // Traverse over the digits of
        // the current element
        for (int j = 0; j < strEle.size(); j++) {
 
            // Checks if parity of check and
            // current digit is same or not
            if (int(strEle[j]) % 2 == check) {
 
                // Rotates the string by j + 1 times
                // in anticlockwise
                arr[i] = stoi(strEle.substr(j + 1)
                              + strEle.substr(0, j + 1));
 
                // Marks the flag
                // as true and break
                flag = true;
                break;
            }
        }
 
        // If flag is false
        if (flag == false) {
            // Update exists
            exists = false;
            break;
        }
 
        // Changes the
        // parity of check
        check = !(check);
    }
 
    // Checks if arr[] cannot be
    // modified, then returns false
    if (!exists) {
        arr = cpy;
        return false;
    }
 
    // Otherwise, return true
    else
        return true;
}
 
// Function to rotate the digits of array
// elements such that array elements are
// in the form of even-odd or odd-even form
void convert_arr(vector<int>& arr)
{
 
    // If array elements can be arranged
    // in even-odd manner alternately
    if (is_possible(arr, 0)) {
        for (auto& i : arr)
            cout << i << " ";
    }
 
    // If array elements can be arranged
    // in odd-even manner alternately
    else if (is_possible(arr, 1)) {
        for (auto& i : arr)
            cout << i << " ";
    }
 
    // Otherwise, prints -1
    else
        cout << "-1" << endl;
}
 
// Driver Code
int main()
{
 
    vector<int> arr = { 143, 251, 534, 232, 854 };
    convert_arr(arr);
}
 
// This code is contributed by grand_master.

Java

// java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG {
 
  // Utility function to rotate the digits of
  // array elements such that array elements are
  // in placed even-odd or odd-even alternately
  static boolean is_possible(int arr[], int check)
  {
 
    // Checks if array can be converted
    // into even-odd or odd-even form
    boolean exists = true;
 
    // Store array elements
    int cpy[] = arr.clone();
    boolean flag;
    // Traverse the array
    for (int i = 0; i < arr.length; i++) {
 
      // Check if arr[i] is already
      // at correct position
      if (arr[i] % 2 == check) {
        // Changes the
        // parity of check
        check = (check == 0 ? 1 : 0);
        continue;
      }
 
      // Checks if it is possible
      // to modify the number arr[i]
      // by rotating the digits of
      // the number anticlockwise
      flag = false;
 
      // Stores the number arr[i] as
      // string
      String strEle = Integer.toString(arr[i]);
 
      // Traverse over the digits of
      // the current element
      for (int j = 0; j < strEle.length(); j++) {
 
        // Checks if parity of check and
        // current digit is same or not
        if ((strEle.charAt(j) - '0') % 2 == check) {
 
          // Rotates the string by j + 1 times
          // in anticlockwise
          arr[i] = Integer.parseInt(
            strEle.substring(j + 1)
            + strEle.substring(0, j + 1));
 
          // Marks the flag
          // as true and break
          flag = true;
          break;
        }
      }
 
      // If flag is false
      if (flag == false) {
        // Update exists
        exists = false;
        break;
      }
 
      // Changes the
      // parity of check
      check = (check == 0 ? 1 : 0);
    }
 
    // Checks if arr[] cannot be
    // modified, then returns false
    if (!exists) {
      arr = cpy;
      return false;
    }
 
    // Otherwise, return true
    else
      return true;
  }
 
  // Function to rotate the digits of array
  // elements such that array elements are
  // in the form of even-odd or odd-even form
  static void convert_arr(int arr[])
  {
 
    // If array elements can be arranged
    // in even-odd manner alternately
    if (is_possible(arr, 0)) {
      for (int v : arr) {
        System.out.print(v + " ");
      }
    }
 
    // If array elements can be arranged
    // in odd-even manner alternately
    else if (is_possible(arr, 1)) {
      for (int v : arr) {
        System.out.print(v + " ");
      }
    }
 
    // Otherwise, prints -1
    else
      System.out.println(-1);
  }
 
  // Driver code
  public static void main(String[] args)
  {
    // Given array
    int arr[] = { 143, 251, 534, 232, 854 };
 
    // FUnction call
    convert_arr(arr);
  }
}
 
// This code is contributed by Kingash.

Python3

# Python program of the above approach
 
# Utility function to rotate the digits of 
# array elements such that array elements are
# in placed even-odd or odd-even alternately
def is_possible(arr, check):
 
    # Checks if array can be converted 
    # into even-odd or odd-even form
    exists = True
 
    # Store array elements
    cpy = arr
 
    # Traverse the array
    for i in range(len(arr)):
 
        # Check if arr[i] is already
        # at correct position 
        if (arr[i] % 2 == check):
            check = not(check)
            continue
 
        # Checks if it is possible
        # to modify the number arr[i]
        # by rotating the digits of
        # the number anticlockwise
        flag = False
 
        # Stores the number arr[i] as
        # string
        strEle = str(arr[i])
 
        # Traverse over the digits of
        # the current element
        for j in range(len(strEle)):
 
            # Checks if parity of check and
            # current digit is same or not
            if int(strEle[j]) % 2 == check:
 
                # Rotates the string by j + 1 times
                # in anticlockwise
                arr[i] = int(strEle[j + 1:] + strEle[:j + 1])
 
                # Marks the flag
                # as true and break
                flag = True
                break
 
        # If flag is false
        if flag == False:
 
            # Update exists
            exists = False
            break
 
        # Changes the
        # parity of check
        check = not(check)
 
    # Checks if arr[] cannot be
    # modified, then returns false
    if not exists:
        arr = cpy
        return False
         
         
    # Otherwise, return True
    else:
        return True
 
# Function to rotate the digits of array
# elements such that array elements are
# in the form of even-odd or odd-even form
def convert_arr(arr):
 
    # If array elements can be arranged
    # in even-odd manner alternately
    if(is_possible(arr, 0)):
        print(*arr)
 
    # If array elements can be arranged
    # in odd-even manner alternately
    elif(is_possible(arr, 1)):
        print(*arr)
         
    # Otherwise, prints -1
    else:
        print(-1)
 
# Driver Code
if __name__ == '__main__':
     
    arr = [143, 251, 534, 232, 854]
    convert_arr(arr)
 
    # This code is contributed by ipg2016107.

C#

// C# program of the above approach
using System;
using System.Collections.Generic;
 
 
class GFG{
   
// Utility function to rotate the digits of
// array elements such that array elements are
// in placed even-odd or odd-even alternately
static bool ispossible(List<int> arr, bool check)
{
 
    // Checks if array can be converted
    // into even-odd or odd-even form
    bool exists = true;
 
    // Store array elements
    List<int> cpy = arr;
    bool flag;
    // Traverse the array
    for (int i=0;i<arr.Count;i++) {
 
        // Check if arr[i] is already
        // at correct position
        int temp = check ? 1 : 0;
        if (arr[i] % 2 == temp) {
            check = !(check);
            continue;
        }
 
        // Checks if it is possible
        // to modify the number arr[i]
        // by rotating the digits of
        // the number anticlockwise
        flag = false;
 
        // Stores the number arr[i] as
        // string
        int p = arr[i];
        string strEle = p.ToString();
 
        // Traverse over the digits of
        // the current element
        for (int j = 0; j < strEle.Length; j++) {
 
            // Checks if parity of check and
            // current digit is same or not
             temp = check ? 1 : 0;
            if ((int)(strEle[j] - '0')% 2 == temp) {
 
                // Rotates the string by j + 1 times
                // in anticlockwise
                string s  = strEle.Substring(j + 1) + strEle.Substring(0, j + 1);
                arr[i] = Int32.Parse(s);
                 
                // Marks the flag
                // as true and break
                flag = true;
                break;
            }
        }
 
        // If flag is false
        if (flag == false) {
            // Update exists
            exists = false;
            break;
        }
 
        // Changes the
        // parity of check
        check = !(check);
    }
 
    // Checks if arr[] cannot be
    // modified, then returns false
    if (exists==false) {
        arr = cpy;
        return false;
    }
 
    // Otherwise, return true
    else
        return true;
}
 
// Function to rotate the digits of array
// elements such that array elements are
// in the form of even-odd or odd-even form
static void convert_arr(List<int> arr)
{
 
    // If array elements can be arranged
    // in even-odd manner alternately
    if (ispossible(arr, false)) {
        foreach (int i in arr)
            Console.Write(i +" ");
    }
 
    // If array elements can be arranged
    // in odd-even manner alternately
    else if (ispossible(arr, true)) {
        foreach (int i in arr)
           Console.Write(i + " ");
    }
 
    // Otherwise, prints -1
    else
        Console.Write("-1");
}
 
// Driver Code
public static void Main()
{
    List<int> arr = new List<int>(){143, 251, 534, 232, 854};
    convert_arr(arr);
}
}

Javascript

<script>
 
    // JavaScript program of the above approach
 
    // Utility function to rotate the digits of
    // array elements such that array elements are
    // in placed even-odd or odd-even alternately
    function is_possible(arr,check)
    {
 
        // Checks if array can be converted
        // into even-odd or odd-even form
        let exists = true;
 
        // Store array elements
        let cpy = arr;
          let flag;
        // Traverse the array
        for (let i = 0; i < arr.length; i++) {
 
            // Check if arr[i] is already
            // at correct position
            if (arr[i] % 2 == check) {
                check = !(check);
                continue;
            }
 
            // Checks if it is possible
            // to modify the number arr[i]
            // by rotating the digits of
            // the number anticlockwise
            flag = false;
 
            // Stores the number arr[i] as
            // string
            let strEle = arr[i].toString();
 
            // Traverse over the digits of
            // the current element
            for (let j = 0; j < strEle.length; j++) {
 
                // Checks if parity of check and
                // current digit is same or not
                if (strEle[j].charCodeAt() % 2 == check) {
 
                    // Rotates the string by j + 1 times
                    // in anticlockwise
                    arr[i] = parseInt(strEle.substr(j + 1)
                                + strEle.substr(0, j + 1));
 
                    // Marks the flag
                    // as true and break
                    flag = true;
                    break;
                }
            }
 
            // If flag is false
            if (flag == false) {
                // Update exists
                exists = false;
                break;
            }
 
            // Changes the
            // parity of check
            check = !(check);
        }
 
        // Checks if arr[] cannot be
        // modified, then returns false
        if (!exists) {
            arr = cpy;
            return false;
        }
 
        // Otherwise, return true
        else
            return true;
    }
 
    // Function to rotate the digits of array
    // elements such that array elements are
    // in the form of even-odd or odd-even form
    function convert_arr(arr)
    {
 
        // If array elements can be arranged
        // in even-odd manner alternately
        if (is_possible(arr, 0)) {
            for (let i = 0; i < arr.length; i++)
                document.write(arr[i] + " ");
        }
 
        // If array elements can be arranged
        // in odd-even manner alternately
        else if (is_possible(arr, 1)) {
            for (let i = 0; i < arr.length; i++)
                document.write(arr[i] + " ");
        }
 
        // Otherwise, prints -1
        else
          document.write("-1");
    }
 
    // Driver Code
 
 
    let arr = [ 143, 251, 534, 232, 854 ];
    convert_arr(arr);
     
</script>

Output:

314 251 534 223 854

Time Complexity: O(N), as we are using a loop to traverse N times.

Auxiliary Space: O(N), as we are using extra space for cpy.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!