Given an array arr[]. The task is to minimize the number of swaps required such that for each i in arr[], arr[i]%3 = i%3. If such rearrangement is not possible, print -1.
Examples:
Input: arr[ ] = {4, 3, 5, 2, 9, 7}
Output: 3
Explanation: Following are the operations performed in arr[]
Initially, index % 3 = {0, 1, 2, 0, 1, 2} and arr[i] % 3 = {1, 0, 2, 2, 0, 1}.
swap arr[0] and arr[1] updates arr[] to arr[] % 3 = {0, 1, 2, 2, 0, 1}
swap arr[3] and arr[4] updates arr[] to arr[] % 3 = {0, 1, 2, 0, 2, 1}
swap arr[4] and arr[5] updates arr[] to arr[] % 3 = {0, 1, 2, 0, 1, 2}
Therefore, 3 swaps are required to get the resultant array which is minimum possible.Input: arr[] = {0, 1, 2, 3, 4}
Output: 0
Approach: This problem is implementation-based and related to modulo properties. Follow the steps below to solve the given problem.
- Iterate the array with i from i = 0 to i=n-1
- if arr[i] % 3 equals 0 then, continue.
- else, find the index j from i+1 to n-1, where i % 3 = arr[j] % 3 and j % 3 = arr[i] % 3.
- With above step move two array elements at their wanted positions.
- If no such j is found, then find an index k form i+1 to n-1, where i % 3 = arr[k] % 3, and swap the elements.
- The base case will be count of indices such that index%3 = arr[i] % 3.
- Return the final count as the required answer.
Below is the implementation of the above approach:
C++
// C++ Program for above approach#include <iostream>using namespace std;// Function to swap two array elements.void swapping(int arr[], int i, int j){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;}// Function to count the Swaps required such that// for all i in arr[] arr[]% 3 = i % 3int CountMinSwaps(int arr[], int n){ // index_mod_i = count of indexes which // give i on modulo 3: index%3==i int index_mod_0 = 0, index_mod_1 = 0, index_mod_2 = 0; // array_mod_i = count of array elements // which give i on modulo 3: arr[i]%3==i int array_mod_0 = 0, array_mod_1 = 0, array_mod_2 = 0; int i, j, count = 0; for (i = 0; i < n; i++) { if (i % 3 == 0) index_mod_0 += 1; else if (i % 3 == 1) index_mod_1 += 1; else if (i % 3 == 2) index_mod_2 += 1; if (arr[i] % 3 == 0) array_mod_0 += 1; else if (arr[i] % 3 == 1) array_mod_1 += 1; else if (arr[i] % 3 == 2) array_mod_2 += 1; } // check for base condition. if (index_mod_0 != array_mod_0 || index_mod_1 != array_mod_1 || index_mod_2 != array_mod_2) return -1; // count the swaps now. for (i = 0; i < n; i++) { // If already in right format // Then goto next index if (i % 3 == arr[i] % 3) continue; int index_org = i % 3; int array_org = arr[i] % 3; // Initially set swapped to false bool swapped = false; for (j = i + 1; j < n; j++) { int index_exp = j % 3; int array_exp = arr[j] % 3; if (index_org == array_exp && array_org == index_exp) { swapping(arr, i, j); // Set swapped to true to make sure // any value is swapped swapped = true; // Increment the count count += 1; break; } } // Check if element is swapped or not if (swapped == false) { for (j = i + 1; j < n; j++) { int array_exp = arr[j] % 3; if (index_org == array_exp) { // Swap indices i and j swapping(arr, i, j); // Increment the count of swaps count += 1; break; } } } } // Return the final result return count;}// Driver Codeint main(){ int arr[6] = { 4, 3, 5, 2, 9, 7 }; int n = sizeof(arr) / sizeof(arr[0]); int swaps = CountMinSwaps(arr, n); cout << swaps << endl;} |
Java
// Java code for the above approachimport java.io.*;class GFG { // Function to swap two array elements.static void swapping(int arr[], int i, int j){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;}// Function to count the Swaps required such that// for all i in arr[] arr[]% 3 = i % 3static int CountMinSwaps(int arr[], int n){ // index_mod_i = count of indexes which // give i on modulo 3: index%3==i int index_mod_0 = 0, index_mod_1 = 0, index_mod_2 = 0; // array_mod_i = count of array elements // which give i on modulo 3: arr[i]%3==i int array_mod_0 = 0, array_mod_1 = 0, array_mod_2 = 0; int i, j, count = 0; for (i = 0; i < n; i++) { if (i % 3 == 0) index_mod_0 += 1; else if (i % 3 == 1) index_mod_1 += 1; else if (i % 3 == 2) index_mod_2 += 1; if (arr[i] % 3 == 0) array_mod_0 += 1; else if (arr[i] % 3 == 1) array_mod_1 += 1; else if (arr[i] % 3 == 2) array_mod_2 += 1; } // check for base condition. if (index_mod_0 != array_mod_0 || index_mod_1 != array_mod_1 || index_mod_2 != array_mod_2) return -1; // count the swaps now. for (i = 0; i < n; i++) { // If already in right format // Then goto next index if (i % 3 == arr[i] % 3) continue; int index_org = i % 3; int array_org = arr[i] % 3; // Initially set swapped to false boolean swapped = false; for (j = i + 1; j < n; j++) { int index_exp = j % 3; int array_exp = arr[j] % 3; if (index_org == array_exp && array_org == index_exp) { swapping(arr, i, j); // Set swapped to true to make sure // any value is swapped swapped = true; // Increment the count count += 1; break; } } // Check if element is swapped or not if (swapped == false) { for (j = i + 1; j < n; j++) { int array_exp = arr[j] % 3; if (index_org == array_exp) { // Swap indices i and j swapping(arr, i, j); // Increment the count of swaps count += 1; break; } } } } // Return the final result return count;} public static void main (String[] args) { int arr[] = { 4, 3, 5, 2, 9, 7 }; int n = arr.length; int swaps = CountMinSwaps(arr, n); System.out.println(swaps ); }}// This code is contributed by Potta Lokesh |
Python3
# python Program for above approach# Function to swap two array elements.def swapping(arr, i, j): temp = arr[i] arr[i] = arr[j] arr[j] = temp# Function to count the Swaps required such that# for all i in arr[] arr[]% 3 = i % 3def CountMinSwaps(arr, n): # index_mod_i = count of indexes which # give i on modulo 3: index%3==i index_mod_0 = 0 index_mod_1 = 0 index_mod_2 = 0 # array_mod_i = count of array elements # which give i on modulo 3: arr[i]%3==i array_mod_0 = 0 array_mod_1 = 0 array_mod_2 = 0 count = 0 for i in range(0, n): if (i % 3 == 0): index_mod_0 += 1 elif (i % 3 == 1): index_mod_1 += 1 elif (i % 3 == 2): index_mod_2 += 1 if (arr[i] % 3 == 0): array_mod_0 += 1 elif (arr[i] % 3 == 1): array_mod_1 += 1 elif (arr[i] % 3 == 2): array_mod_2 += 1 # check for base condition. if (index_mod_0 != array_mod_0 or index_mod_1 != array_mod_1 or index_mod_2 != array_mod_2): return -1 # count the swaps now. for i in range(0, n): # If already in right format # Then goto next index if (i % 3 == arr[i] % 3): continue index_org = i % 3 array_org = arr[i] % 3 # Initially set swapped to false swapped = False for j in range(i+1, n): index_exp = j % 3 array_exp = arr[j] % 3 if (index_org == array_exp and array_org == index_exp): swapping(arr, i, j) # Set swapped to true to make sure # any value is swapped swapped = True # Increment the count count += 1 break # Check if element is swapped or not if (swapped == False): for j in range(i+1, n): array_exp = arr[j] % 3 if (index_org == array_exp): # Swap indices i and j swapping(arr, i, j) # Increment the count of swaps count += 1 break # Return the final result return count# Driver Codeif __name__ == "__main__": arr = [4, 3, 5, 2, 9, 7] n = len(arr) swaps = CountMinSwaps(arr, n) print(swaps) # This code is contributed by rakeshsahni |
C#
// C# code for the above approachusing System;class GFG{ // Function to swap two array elements. static void swapping(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } // Function to count the Swaps required such that // for all i in arr[] arr[]% 3 = i % 3 static int CountMinSwaps(int[] arr, int n) { // index_mod_i = count of indexes which // give i on modulo 3: index%3==i int index_mod_0 = 0, index_mod_1 = 0, index_mod_2 = 0; // array_mod_i = count of array elements // which give i on modulo 3: arr[i]%3==i int array_mod_0 = 0, array_mod_1 = 0, array_mod_2 = 0; int i, j, count = 0; for (i = 0; i < n; i++) { if (i % 3 == 0) index_mod_0 += 1; else if (i % 3 == 1) index_mod_1 += 1; else if (i % 3 == 2) index_mod_2 += 1; if (arr[i] % 3 == 0) array_mod_0 += 1; else if (arr[i] % 3 == 1) array_mod_1 += 1; else if (arr[i] % 3 == 2) array_mod_2 += 1; } // check for base condition. if (index_mod_0 != array_mod_0 || index_mod_1 != array_mod_1 || index_mod_2 != array_mod_2) return -1; // count the swaps now. for (i = 0; i < n; i++) { // If already in right format // Then goto next index if (i % 3 == arr[i] % 3) continue; int index_org = i % 3; int array_org = arr[i] % 3; // Initially set swapped to false Boolean swapped = false; for (j = i + 1; j < n; j++) { int index_exp = j % 3; int array_exp = arr[j] % 3; if (index_org == array_exp && array_org == index_exp) { swapping(arr, i, j); // Set swapped to true to make sure // any value is swapped swapped = true; // Increment the count count += 1; break; } } // Check if element is swapped or not if (swapped == false) { for (j = i + 1; j < n; j++) { int array_exp = arr[j] % 3; if (index_org == array_exp) { // Swap indices i and j swapping(arr, i, j); // Increment the count of swaps count += 1; break; } } } } // Return the final result return count; } public static void Main() { int[] arr = { 4, 3, 5, 2, 9, 7 }; int n = arr.Length; int swaps = CountMinSwaps(arr, n); Console.Write(swaps); }}// This code is contributed by Saurabh Jaiswal |
Javascript
<script> // JavaScript Program for above approach // Function to swap two array elements. const swapping = (arr, i, j) => { let temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } // Function to count the Swaps required such that // for all i in arr[] arr[]% 3 = i % 3 const CountMinSwaps = (arr, n) => { // index_mod_i = count of indexes which // give i on modulo 3: index%3==i let index_mod_0 = 0, index_mod_1 = 0, index_mod_2 = 0; // array_mod_i = count of array elements // which give i on modulo 3: arr[i]%3==i let array_mod_0 = 0, array_mod_1 = 0, array_mod_2 = 0; let i, j, count = 0; for (i = 0; i < n; i++) { if (i % 3 == 0) index_mod_0 += 1; else if (i % 3 == 1) index_mod_1 += 1; else if (i % 3 == 2) index_mod_2 += 1; if (arr[i] % 3 == 0) array_mod_0 += 1; else if (arr[i] % 3 == 1) array_mod_1 += 1; else if (arr[i] % 3 == 2) array_mod_2 += 1; } // check for base condition. if (index_mod_0 != array_mod_0 || index_mod_1 != array_mod_1 || index_mod_2 != array_mod_2) return -1; // count the swaps now. for (i = 0; i < n; i++) { // If already in right format // Then goto next index if (i % 3 == arr[i] % 3) continue; let index_org = i % 3; let array_org = arr[i] % 3; // Initially set swapped to false let swapped = false; for (j = i + 1; j < n; j++) { let index_exp = j % 3; let array_exp = arr[j] % 3; if (index_org == array_exp && array_org == index_exp) { swapping(arr, i, j); // Set swapped to true to make sure // any value is swapped swapped = true; // Increment the count count += 1; break; } } // Check if element is swapped or not if (swapped == false) { for (j = i + 1; j < n; j++) { let array_exp = arr[j] % 3; if (index_org == array_exp) { // Swap indices i and j swapping(arr, i, j); // Increment the count of swaps count += 1; break; } } } } // Return the final result return count; } // Driver Code let arr = [4, 3, 5, 2, 9, 7]; let n = arr.length; let swaps = CountMinSwaps(arr, n); document.write(swaps); // This code is contributed by rakeshsahni</script> |
Output:
3
Time Complexity: O(N2), Where N is the size of arr[].
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!
