Sort an array by left shifting digits of array elements
Given an array arr[] consisting of N positive integers, the task is to left-shift the digits of array elements such that the array modifies to a sorted form. If multiple solutions exist, then print any one of them. Otherwise, print -1.
Examples:
Input: arr[] = { 511, 321, 323, 432 }
Output: { 115, 132, 233, 243 }
Explanation:
Left shift the digits of arr[0] by 1 modifies arr[0] to 115.
Left shift the digits of arr[1] by 2 modifies arr[1] to 132
Left shift the digits of arr[2] by 1 modifies arr[2] to 233
Left shift the digits of arr[3] by 1 modifies arr[3] to 243Input: { 5, 1, 2, 3, 3 }
Output: -1
Approach: Follow the steps below to solve the problem:
- The idea is to left-shift the digits of each array element such that the current element is the nearest greater element of the previous array elements.
- Traverse the array and shift the digits of array elements in all possible ways and pick the one which is minimum, but greater than the previous array element. If it is not possible to find such elements, then print -1.
- Otherwise, print the array elements after performing the above operations
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check if an array is // sorted in increasing order or not bool isIncreasing(vector< int > arr) { // Traverse the array for ( int i = 0; i < arr.size() - 1; i++) { if (arr[i] > arr[i + 1]) return false ; } return true ; } // Function to sort the array // by left shifting digits of // array elements vector< int > sortArr(vector< int > arr) { // Stores previous array // element int prev = -1; // Traverse the array arr[] for ( int i = 0; i < arr.size(); i++) { // Stores current element int optEle = arr[i]; // Stores current element // in string format string strEle = to_string(arr[i]); // Left-shift digits of current // element in all possible ways for ( int idx = 0; idx < strEle.size(); idx++) { // Left-shift digits of current // element by idx string strEle2 = strEle.substr(idx) + strEle.substr(0, idx); int temp = stoi(strEle2); // If temp greater than or equal to // prev and temp less than optEle if (temp >= prev && temp < optEle) optEle = temp; } // Update arr[i] arr[i] = optEle; // Update prev prev = arr[i]; } // If arr is in increasing order if (isIncreasing(arr)) return arr; // Otherwise else { arr = { -1 }; return arr; } } // Driver Code int main() { vector< int > arr = { 511, 321, 323, 432, 433 }; vector< int > res = sortArr(arr); for ( int i = 0; i < res.size(); i++) cout << res[i] << " " ; return 0; } // This code is contributed by subhammahato348 |
Java
// Java program for the above approach import java.util.*; class GFG { // Function to check if an array is // sorted in increasing order or not static boolean isIncreasing( int []arr) { // Traverse the array for ( int i = 0 ; i < arr.length - 1 ; i++) { if (arr[i] > arr[i + 1 ]) return false ; } return true ; } // Function to sort the array // by left shifting digits of // array elements static int [] sortArr( int []arr) { // Stores previous array // element int prev = - 1 ; // Traverse the array arr[] for ( int i = 0 ; i < arr.length; i++) { // Stores current element int optEle = arr[i]; // Stores current element // in String format String strEle = String.valueOf(arr[i]); // Left-shift digits of current // element in all possible ways for ( int idx = 0 ; idx < strEle.length(); idx++) { // Left-shift digits of current // element by idx String strEle2 = strEle.substring(idx) + strEle.substring( 0 , idx); int temp = Integer.valueOf(strEle2); // If temp greater than or equal to // prev and temp less than optEle if (temp >= prev && temp < optEle) optEle = temp; } // Update arr[i] arr[i] = optEle; // Update prev prev = arr[i]; } // If arr is in increasing order if (isIncreasing(arr)) return arr; // Otherwise else { return new int []{ - 1 }; } } // Driver Code public static void main(String[] args) { int []arr = { 511 , 321 , 323 , 432 , 433 }; int []res = sortArr(arr); for ( int i = 0 ; i < res.length; i++) System.out.print(res[i]+ " " ); } } // This code is contributed by shikhasingrajput |
Python3
# Python3 program for the above approach # Function to check if an array is # sorted in increasing order or not def isIncreasing(arr): # Traverse the array for i in range ( len (arr) - 1 ): if arr[i] > arr[i + 1 ]: return False return True # Function to sort the array # by left shifting digits of # array elements def sortArr(arr): # Stores previous array # element prev = - 1 # Traverse the array arr[] for i in range ( len (arr)): # Stores current element optEle = arr[i] # Stores current element # in string format strEle = str (arr[i]) # Left-shift digits of current # element in all possible ways for idx in range ( len (strEle)): # Left-shift digits of current # element by idx temp = int (strEle[idx:] + strEle[:idx]) # If temp greater than or equal to # prev and temp less than optEle if temp > = prev and temp < optEle: optEle = temp # Update arr[i] arr[i] = optEle # Update prev prev = arr[i] # If arr is in increasing order if isIncreasing(arr): return arr # Otherwise else : return "-1" # Driver Code if __name__ = = '__main__' : arr = [ 511 , 321 , 323 , 432 , 433 ] res = sortArr(arr) for i in res: print (i, end = " " ) |
C#
// C# program for the above approach using System; public class GFG { // Function to check if an array is // sorted in increasing order or not static bool isIncreasing( int []arr) { // Traverse the array for ( int i = 0; i < arr.Length - 1; i++) { if (arr[i] > arr[i + 1]) return false ; } return true ; } // Function to sort the array // by left shifting digits of // array elements static int [] sortArr( int []arr) { // Stores previous array // element int prev = -1; // Traverse the array []arr for ( int i = 0; i < arr.Length; i++) { // Stores current element int optEle = arr[i]; // Stores current element // in String format String strEle = String.Join( "" ,arr[i]); // Left-shift digits of current // element in all possible ways for ( int idx = 0; idx < strEle.Length; idx++) { // Left-shift digits of current // element by idx String strEle2 = strEle.Substring(idx) + strEle.Substring(0, idx); int temp = Int32.Parse(strEle2); // If temp greater than or equal to // prev and temp less than optEle if (temp >= prev && temp < optEle) optEle = temp; } // Update arr[i] arr[i] = optEle; // Update prev prev = arr[i]; } // If arr is in increasing order if (isIncreasing(arr)) return arr; // Otherwise else { return new int []{ -1 }; } } // Driver Code public static void Main(String[] args) { int []arr = { 511, 321, 323, 432, 433 }; int []res = sortArr(arr); for ( int i = 0; i < res.Length; i++) Console.Write(res[i]+ " " ); } } // This code is contributed by shikhasingrajput. |
Javascript
<script> // Javascript program for the above approach // Function to check if an array is // sorted in increasing order or not function isIncreasing(arr) { // Traverse the array for (let i = 0; i < arr.length - 1; i++) { if (arr[i] > arr[i + 1]) return false ; } return true ; } // Function to sort the array // by left shifting digits of // array elements function sortArr(arr) { // Stores previous array // element let prev = -1; // Traverse the array arr[] for (let i = 0; i < arr.length; i++) { // Stores current element let optEle = arr[i]; // Stores current element // in string format let strEle = arr[i].toString(); // Left-shift digits of current // element in all possible ways for (let idx = 0; idx < strEle.length; idx++) { // Left-shift digits of current // element by idx let strEle2 = strEle.substr(idx) + strEle.substr(0, idx); let temp = parseInt(strEle2); // If temp greater than or equal to // prev and temp less than optEle if (temp >= prev && temp < optEle) optEle = temp; } // Update arr[i] arr[i] = optEle; // Update prev prev = arr[i]; } // If arr is in increasing order if (isIncreasing(arr)) return arr; // Otherwise else { arr = [ -1 ]; return arr; } } let arr = [ 511, 321, 323, 432, 433 ]; let res = sortArr(arr); for (let i = 0; i < res.length; i++) document.write(res[i] + " " ); // This code is contributed by mukesh07. </script> |
Output:
115 132 233 243 334
Time Complexity: O(N)
Auxiliary Space:O(N)
Contact Us