Given an array of size N, the task is to determine whether its possible to sort the array or not by just one shuffle. In one shuffle, we can shift some contiguous elements from the end of the array and place it in the front of the array.
For eg:
- A = {2, 3, 1, 2}, we can shift {1, 2} from the end of the array to the front of the array to sort it.
- A = {1, 2, 3, 2} since we cannot sort it in one shuffle hence it’s not possible to sort the array.
Examples:
Input: arr[] = {1, 2, 3, 4}
Output: Possible
Since this array is already sorted hence no need for shuffle.
Input: arr[] = {6, 8, 1, 2, 5}
Output: Possible
Place last three elements at the front
in the same order i.e. {1, 2, 5, 6, 8}
Approach:
- Check if the array is already sorted or not. If yes return true.
- Else start traversing the array elements until the current element is smaller than next element. Store that index where arr[i] > arr[i+1].
- Traverse from that point and check if from that index elements are in increasing order or not.
- If above both conditions satisfied then check if last element is smaller than or equal to the first element of given array.
- Print “Possible” if above three conditions satisfied else print “Not possible” if any of the above 3 conditions failed.
Below is the implementation of above approach:
C++
// C++ implementation of above approach#include <bits/stdc++.h>using namespace std;// Function to check if it is possiblebool isPossible(int a[], int n){ // step 1 if (is_sorted(a, a + n)) { cout << "Possible" << endl; } else { // break where a[i] > a[i+1] bool flag = true; int i; for (i = 0; i < n - 1; i++) { if (a[i] > a[i + 1]) { break; } } // break point + 1 i++; // check whether the sequence is // further increasing or not for (int k = i; k < n - 1; k++) { if (a[k] > a[k + 1]) { flag = false; break; } } // If not increasing after break point if (!flag) return false; else { // last element <= First element if (a[n - 1] <= a[0]) return true; else return false; } }}// Driver codeint main(){ int arr[] = { 3, 1, 2, 2, 3 }; int n = sizeof(arr) / sizeof(arr[0]); if (isPossible(arr, n)) cout << "Possible"; else cout << "Not Possible"; return 0;} |
Java
// Java implementation of above approach class solution{ //check if array is sortedstatic boolean is_sorted(int a[],int n){ int c1=0,c2=0; //if array is ascending for(int i=0;i<n-1;i++) { if(a[i]<=a[i+1]) c1++; } //if array is descending for(int i=1;i<n;i++) { if(a[i]<=a[i-1]) c2++; } if(c1==n||c2==n) return true; return false;}// Function to check if it is possible static boolean isPossible(int a[], int n) { // step 1 if (is_sorted(a,n)) { System.out.println("Possible"); } else { // break where a[i] > a[i+1] boolean flag = true; int i; for (i = 0; i < n - 1; i++) { if (a[i] > a[i + 1]) { break; } } // break point + 1 i++; // check whether the sequence is // further increasing or not for (int k = i; k < n - 1; k++) { if (a[k] > a[k + 1]) { flag = false; break; } } // If not increasing after break point if (!flag) return false; else { // last element <= First element if (a[n - 1] <= a[0]) return true; else return false; } } return false;} // Driver code public static void main(String[] args) { int arr[] = { 3, 1, 2, 2, 3 }; int n = arr.length; if (isPossible(arr, n)) System.out.println("Possible"); else System.out.println("Not Possible"); } }//contributed by Arnab Kundu |
Python 3
# Python 3 implementation of # above approachdef is_sorted(a): all(a[i] <= a[i + 1] for i in range(len(a) - 1)) # Function to check if # it is possibledef isPossible(a, n): # step 1 if (is_sorted(a)) : print("Possible") else : # break where a[i] > a[i+1] flag = True for i in range(n - 1) : if (a[i] > a[i + 1]) : break # break point + 1 i += 1 # check whether the sequence is # further increasing or not for k in range(i, n - 1) : if (a[k] > a[k + 1]) : flag = False break # If not increasing after # break point if (not flag): return False else : # last element <= First element if (a[n - 1] <= a[0]): return True else: return False# Driver codeif __name__ == "__main__": arr = [ 3, 1, 2, 2, 3 ] n = len(arr) if (isPossible(arr, n)): print("Possible") else: print("Not Possible")# This code is contributed# by ChitraNayal |
C#
// C# implementation of above approach using System;class GFG{// check if array is sortedstatic bool is_sorted(int []a, int n){ int c1 = 0, c2 = 0; // if array is ascending for(int i = 0; i < n - 1; i++) { if(a[i] <= a[i + 1]) c1++; } // if array is descending for(int i = 1; i < n; i++) { if(a[i] <= a[i - 1]) c2++; } if(c1 == n || c2 == n) return true; return false;}// Function to check if it is possible static bool isPossible(int []a, int n) { // step 1 if (is_sorted(a,n)) { Console.WriteLine("Possible"); } else { // break where a[i] > a[i+1] bool flag = true; int i; for (i = 0; i < n - 1; i++) { if (a[i] > a[i + 1]) { break; } } // break point + 1 i++; // check whether the sequence is // further increasing or not for (int k = i; k < n - 1; k++) { if (a[k] > a[k + 1]) { flag = false; break; } } // If not increasing after // break point if (!flag) return false; else { // last element <= First element if (a[n - 1] <= a[0]) return true; else return false; } } return false;} // Driver code public static void Main() { int []arr = { 3, 1, 2, 2, 3 }; int n = arr.Length; if (isPossible(arr, n)) Console.WriteLine("Possible"); else Console.WriteLine("Not Possible"); } }// This code is contributed by anuj_67 |
PHP
<?php// PHP implementation of // above approach// Function to check if // it is possiblefunction is_sorted($a, $n){ $c1 = 0; $c2 = 0; // if array is ascending for($i = 0; $i < $n - 1; $i++) { if($a[$i] <= $a[$i + 1]) $c1++; } // if array is descending for($i = 1; $i < $n; $i++) { if($a[$i] <= $a[$i - 1]) $c2++; } if($c1 == $n || $c2 == $n) return true; return false;}function isPossible($a, $n){ // step 1 if (is_sorted($a, $n)) { echo "Possible" . "\n"; } else { // break where a[i] > a[i+1] $flag = true; $i; for ($i = 0; $i < $n - 1; $i++) { if ($a[$i] > $a[$i + 1]) { break; } } // break point + 1 $i++; // check whether the sequence is // further increasing or not for ($k = $i; $k < $n - 1; $k++) { if ($a[$k] > $a[$k + 1]) { $flag = false; break; } } // If not increasing after // break point if (!$flag) return false; else { // last element <= First element if ($a[$n - 1] <= $a[0]) return true; else return false; } }}// Driver code$arr = array( 3, 1, 2, 2, 3 );$n = sizeof($arr);if (isPossible($arr, $n)) echo "Possible";else echo "Not Possible";// This code is contributed// by Akanksha Rai(Abby_akku)?> |
Javascript
<script>// Javascript implementation of above approach // check if array is sorted function is_sorted(a) { let c1=0,c2=0; // if array is ascending for(let i=0;i<n-1;i++) { if(a[i]<=a[i+1]) { c1++; } } // if array is descending for(let i=1;i<n;i++) { if(a[i]<=a[i-1]) c2++; } if(c1==n||c2==n) { return true; } return false; } // Function to check if it is possible function isPossible(a,n) { // step 1 if (is_sorted(a,n)) { document.write("Possible"); } else { // break where a[i] > a[i+1] let flag = true; let i; for (i = 0; i < n - 1; i++) { if (a[i] > a[i + 1]) { break; } } // break point + 1 i++; // check whether the sequence is // further increasing or not for (let k = i; k < n - 1; k++) { if (a[k] > a[k + 1]) { flag = false; break; } } // If not increasing after break point if (!flag) { return false; } else { // last element <= First element if (a[n - 1] <= a[0]) return true; else return false; } } return false; } // Driver code let arr=[3, 1, 2, 2, 3]; let n = arr.length; if(isPossible(arr, n)) document.write("Possible"); else document.write("Not Possible"); // This code is contributed by avanitrachhadiya2155</script> |
Output:
Possible
Time Complexity: O(n)
Auxiliary Space: O(1)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
