Given a permutation arr[] of size n and a positive integer x, the task is to sort the permutation in increasing order by performing the following operations:
- You can swap arr[i] with arr[j] if abs(i-j] = x, you can perform this operation any number of times.
- You can swap arr[i] with arr[j] if abs(i-j) lies in the range [1, n-1], you can perform this operation at most once.
Examples:
Input: arr[] = { 3, 1, 4, 2, 5 }, x = 2
Output: Yes
Explanation: we will apply the type 2 operation on indexes 2 & 3 . Then we will apply the type-1 operation till the array is not sorted.Input: arr[] = { 2, 3, 4, 1}, x = 3
Output: No
Explanation: It is impossible to sort the array because it needs more than one of type-2 operation.
Approach: To solve the problem follow the below idea:
We can place arr[i] on the index i only if abs(arr[i]-i) is divisible by x, you can observe this in example 1 as above. But if there are two elements arr[i] & arr[j] in the array such that both abs(arr[i]-i) & abs(arr[j]-j) aren’t divisible by x. But abs(arr[i]-j) & abs(arr[j]-i) are divisible by x. After swapping, we can sort this. But if there are more than two elements as above type. Then we can’t sort because we can use type-2 operation at most once.
Below are the steps to implement the above idea:
- First, we will find how many elements are in the array such that abs(arr[i]-i) isn’t divisible by x.
- If there is no element, we will print “Yes“.
- If there are exactly two elements, then we will check if we swap these two elements if after swapping, both abs(arr[i]-i) & abs(arr[j]-j) are divisible by x, then print “Yes”. else print “No”.
- If there are more than two elements, print “No” because it needs more than one of type-2 operation to sort this.
Below is the implementation of the above approach:
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Function to check can we sort the// permutation in the increasing order// bu doing these operationbool sortpermutation(int* arr, int n, int x){ int co = 0, i1, i2; for (int i = 0; i < n; i++) { // Difference between arr[i] // and (i+1) int temp = abs((i + 1) - arr[i]); // If that difference isn't // divisible by x if (temp % x != 0) { // Storing the index of // element in i1 that // difference isn't // divisible by x if (co == 0) { i1 = i; } else if (co == 1) { i2 = i; } else { co += 1; break; } co += 1; } } if (co == 0) { return true; } else if (co <= 2) { // swap that two element swap(arr[i1], arr[i2]); // Check if after swapping, // the that two element // is also divisible by x if (abs(arr[i1] - (i1 + 1)) % x == 0 && abs(arr[i2] - (i2 + 1)) % x == 0) { // If divisible, // then return true return true; } else { // If not divisible, // then return false return false; } } else { return false; }}// Driver codeint main(){ int arr[] = { 3, 1, 4, 2, 5 }; int n = sizeof(arr) / sizeof(int); int x = 2; // Function call if (sortpermutation(arr, n, x)) { cout << "Yes" << endl; } else { cout << "No" << endl; } return 0;} |
Java
// Java code for the above approachimport java.util.Arrays;class GFG { // Function to check if we can sort the // permutation in increasing order by // performing given operation public static boolean sortPermutation(int[] arr, int n, int x) { int co = 0, i1 = 0, i2 = 0; for (int i = 0; i < n; i++) { // Difference between arr[i] and (i+1) int temp = Math.abs((i + 1) - arr[i]); // If the difference isn't divisible by x if (temp % x != 0) { // Storing the index of the element in i1 if (co == 0) { i1 = i; } // Storing the index of the element in i2 else if (co == 1) { i2 = i; } // If more than 2 elements have differences // not divisible by x, return false else { return false; } co++; } } // If there are no elements with differences not // divisible by x, return true if (co == 0) { return true; } // If there are exactly 2 elements with differences // not divisible by x, swap them and check if the // resulting permutation is valid else if (co == 2) { swap(arr, i1, i2); return (Math.abs(arr[i1] - (i1 + 1)) % x == 0 && Math.abs(arr[i2] - (i2 + 1)) % x == 0); } // If there are more than 2 elements with // differences not divisible by x, return false else { return false; } } // Function to swap two elements in the array public static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } // Driver code public static void main(String[] args) { int[] arr = { 3, 1, 4, 2, 5 }; int n = arr.length; int x = 2; // Function call if (sortPermutation(arr, n, x)) { System.out.println("Yes"); } else { System.out.println("No"); } }}// This code is contibuted by shivamgupta310570 |
Python3
def sortpermutation(arr, n, x): co = 0 for i in range(n): # Difference between arr[i] and (i+1) temp = abs((i + 1) - arr[i]) # If that difference isn't divisible by x if temp % x != 0: # Storing the index of element in i1 that difference isn't divisible by x if co == 0: i1 = i elif co == 1: i2 = i else: co += 1 break co += 1 if co == 0: return True elif co <= 2: # Swap the two elements arr[i1], arr[i2] = arr[i2], arr[i1] # Check if after swapping, the two elements are also divisible by x if abs(arr[i1] - (i1 + 1)) % x == 0 and abs(arr[i2] - (i2 + 1)) % x == 0: # If divisible, return True return True else: # If not divisible, return False return False else: return False# Driver codearr = [3, 1, 4, 2, 5]n = len(arr)x = 2# Function callif sortpermutation(arr, n, x): print("Yes")else: print("No")# This code is contributed by shivamgupta0987654321 |
C#
// C# code for the above approachusing System;public class GFG { // Function to check can we sort the // permutation in the increasing order // by doing these operations static bool SortPermutation(int[] arr, int n, int x) { int co = 0, i1 = 0, i2 = 0; for (int i = 0; i < n; i++) { // Difference between arr[i] // and (i+1) int temp = Math.Abs((i + 1) - arr[i]); // If that difference isn't // divisible by x if (temp % x != 0) { // Storing the index of // element in i1 that // difference isn't // divisible by x if (co == 0) { i1 = i; } else if (co == 1) { i2 = i; } else { co += 1; break; } co += 1; } } if (co == 0) { return true; } else if (co <= 2) { // swap the two elements int temp = arr[i1]; arr[i1] = arr[i2]; arr[i2] = temp; // Check if after swapping, // the that two element // is also divisible by x if (Math.Abs(arr[i1] - (i1 + 1)) % x == 0 && Math.Abs(arr[i2] - (i2 + 1)) % x == 0) { // If divisible, // then return true return true; } else { // If not divisible, // then return false return false; } } else { return false; } } // Driver code static void Main() { int[] arr = { 3, 1, 4, 2, 5 }; int n = arr.Length; int x = 2; // Function call if (SortPermutation(arr, n, x)) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } }}// This code is contributed by Susobhan Akhuli |
Javascript
<script>// JavaScript code for the above approachfunction sortPermutation(arr, n, x) { let co = 0; let i1, i2; for (let i = 0; i < n; i++) { // Difference between arr[i] and (i+1) const temp = Math.abs(i + 1 - arr[i]); // If that difference isn't divisible by x if (temp % x !== 0) { // Storing the index of element in i1 that difference isn't divisible by x if (co === 0) { i1 = i; } else if (co === 1) { i2 = i; } else { co += 1; break; } co += 1; } } if (co === 0) { return true; } else if (co <= 2) { // Swap those two elements [arr[i1], arr[i2]] = [arr[i2], arr[i1]]; // Check if after swapping, the two elements are also divisible by x if (Math.abs(arr[i1] - (i1 + 1)) % x === 0 && Math.abs(arr[i2] - (i2 + 1)) % x === 0) { // If divisible, then return true return true; } else { // If not divisible, then return false return false; } } else { return false; }}// Driver codeconst arr = [3, 1, 4, 2, 5];const n = arr.length;const x = 2;// Function callif (sortPermutation(arr, n, x)) { document.write("Yes");} else { document.write("No");}// This code is contributed by Susobhan Akhuli</script> |
Output
Yes
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!
Share your thoughts in the comments
