Check if it is possible to sort an array with conditional swapping of elements at distance K
Given an array arr[] of n elements, we have to swap an index i with another index i + k any number of times and check whether it is possible to sort the given array arr[]. If it is then print “yes” otherwise print “no”.
Examples:
Input: K = 2, arr = [4, 3, 2, 6, 7]
Output: Yes
Explanation:
Choose index i = 0 and swap index i with i + k then the array becomes [2, 3, 4, 6, 7] which is sorted hence the output is “yes”.
Input : K = 2, arr = [4, 2, 3, 7, 6]
Output : No
Explanation:
It is not possible to obtain sorted array.
Approach:
To solve the problem mentioned above we have to take the elements starting from index 0 and add the multiples of K to it, that is 0, 0 + k, 0 + (2*k), and so on. Swap these positions for all the indexes from 0 to K-1 and check if the final array is sorted. If it is, then return “yes” otherwise “no”.
Below is the implementation of the above approach:
C++
// CPP implementation to Check if it is possible to sort an// array with conditional swapping of elements at distance K#include <bits/stdc++.h>using namespace std;// Function for finding if it possible// to obtain sorted array or notbool fun(int arr[], int n, int k){ vector<int> v; // Iterate over all elements until K for (int i = 0; i < k; i++) { // Store elements as multiples of K for (int j = i; j < n; j += k) { v.push_back(arr[j]); } // Sort the elements sort(v.begin(), v.end()); int x = 0; // Put elements in their required position for (int j = i; j < n; j += k) { arr[j] = v[x]; x++; } v.clear(); } // Check if the array becomes sorted or not for (int i = 0; i < n - 1; i++) { if (arr[i] > arr[i + 1]) return false; } return true;}// Driver codeint main(){ int arr[] = { 4, 2, 3, 7, 6 }; int K = 2; int n = sizeof(arr) / sizeof(arr[0]); if (fun(arr, n, K)) cout << "yes" << endl; else cout << "no" << endl; return 0;} |
Java
// Java implementation to check if it // is possible to sort an array with // conditional swapping of elements// at distance K import java.lang.*;import java.io.*;import java.util.*;class GFG{ // Function for finding if it possible // to obtain sorted array or not public static boolean fun(int[] arr, int n, int k){ Vector<Integer> v = new Vector<Integer>(); // Iterate over all elements until K for(int i = 0; i < k; i++) { // Store elements as multiples of K for(int j = i; j < n; j += k) { v.add(arr[j]); } // Sort the elements Collections.sort(v); int x = 0; // Put elements in their // required position for(int j = i; j < n; j += k) { arr[j] = v.get(x); x++; } v.clear(); } // Check if the array becomes // sorted or not for(int i = 0; i < n - 1; i++) { if (arr[i] > arr[i + 1]) { return false; } } return true;}// Driver code public static void main (String args[]){ int[] arr = { 4, 2, 3, 7, 6 }; int K = 2; int n = arr.length; if (fun(arr, n, K)) { System.out.println("yes"); } else { System.out.println("no"); }}}// This code is contributed by sayesha |
Python3
# Python3 implementation to Check if it is possible to sort an# array with conditional swapping of elements at distance K# Function for finding if it possible# to obtain sorted array or notdef fun(arr, n, k): v = [] # Iterate over all elements until K for i in range(k): # Store elements as multiples of K for j in range(i, n, k): v.append(arr[j]); # Sort the elements v.sort(); x = 0 # Put elements in their required position for j in range(i, n, k): arr[j] = v[x]; x += 1 v = [] # Check if the array becomes sorted or not for i in range(n - 1): if (arr[i] > arr[i + 1]): return False return True# Driver codearr= [ 4, 2, 3, 7, 6 ]K = 2;n = len(arr)if (fun(arr, n, K)): print("yes")else: print("no") # This code is contributed by apurva raj |
C#
// C# implementation to check if it // is possible to sort an array with // conditional swapping of elements// at distance K using System;using System.Collections.Generic;class GFG{ // Function for finding if it possible // to obtain sorted array or not public static bool fun(int[] arr, int n, int k){ List<int> v = new List<int>(); // Iterate over all elements until K for(int i = 0; i < k; i++) { // Store elements as multiples of K for(int j = i; j < n; j += k) { v.Add(arr[j]); } // Sort the elements v.Sort(); int x = 0; // Put elements in their // required position for(int j = i; j < n; j += k) { arr[j] = v[x]; x++; } v.Clear(); } // Check if the array becomes // sorted or not for(int i = 0; i < n - 1; i++) { if (arr[i] > arr[i + 1]) { return false; } } return true;}// Driver code public static void Main(String []args){ int[] arr = {4, 2, 3, 7, 6}; int K = 2; int n = arr.Length; if (fun(arr, n, K)) { Console.WriteLine("yes"); } else { Console.WriteLine("no"); }}}// This code is contributed by shikhasingrajput |
Javascript
<script>// JavaScript implementation to // Check if it is possible to sort an// array with conditional swapping of // elements at distance K// Function for finding if it possible// to obtain sorted array or notfunction fun(arr, n, k){ let v = []; // Iterate over all elements until K for (let i = 0; i < k; i++) { // Store elements as multiples of K for (let j = i; j < n; j += k) { v.push(arr[j]); } // Sort the elements v.sort(); let x = 0; // Put elements in their required position for (let j = i; j < n; j += k) { arr[j] = v[x]; x++; } v = []; } // Check if the array becomes sorted or not for (let i = 0; i < n - 1; i++) { if (arr[i] > arr[i + 1]) return false; } return true;}// Driver code let arr = [ 4, 2, 3, 7, 6 ]; let K = 2; let n = arr.length; if (fun(arr, n, K)) document.write("yes"); else document.write("no");</script> |
Output:
no
Time Complexity: O(k*n*log(n))
Auxiliary Space: O(n)
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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
