Minimize Swaps to Make Remainder Equal When an Element and its Index is Divided by K

Intuition

The above problem should be solved with a greedy approach easily as we are asked to find the minimum swaps to reach the desired result. So at first, we will always try to find the pairs of elements, such that both reach their accurate positions after swapping. In this way, we can make two elements reach their position with one swap leading us to find minimum swaps to reach the desired outcome.

Approach

First, we need to check if the task can be completed after performing any number of swaps. So we can use a 2-D vector to store the frequencies of (index % K) and (element % K) separately for every index 0 to N. And then compare the frequencies, and if any of the counts are not equal, then the task cannot be completed with any number of swaps.

If all the frequencies match, then perform the below algorithm.

Algorithm

• Declare a variable ‘COUNT’ to store total number of swaps required.
• Iterate through the array NUMS[] for every index i, 0 to N - 1
• Check if (NUMS[i] % K) is equal to (i % K), then continue to next index
• Else run a second loop for every index j from i + 1 to N - 1, to find a suitable index where 

i % K == NUMS[j] % K and j % K == NUMS[i] % K  

• If such index is found, then swap and increase the variable count
• Else again run a second loop for every index j from i + 1 to N - 1 to find an index where

i % K == NUMS[j] % K 

• And swap and increase the variable ‘COUNT’.

Program

#include <iostream>
#include <vector>
 
using namespace std;
 
// Function to check if the remainders can be made equal by swapping.
bool isSwapPossible(vector<int>& NUMS, int K)
{
      // 2-D vector to store the count of different remainders with ‘K’.
      vector<vector<int>> remCount(K, vector<int>(2));
 
      // Traversing the array to store the count of different remainders with ‘K’.
      for (int i = 0; i < NUMS.size(); i++)
      {
            // Remainder when index divided by ‘K’.
            remCount[i % K][0]++;
 
            // Remainder when an element is divided by ‘K’.
            remCount[NUMS[i] % K][1]++;
      }
 
      // Traversing to compare counts of remainder with ‘K’.
      for (int i = 0; i < K; i++)
      {
            // Concluding if the count of the remainder of the element is not equal to that of index.
            if (remCount[i % K][0] != remCount[i % K][1])
                  return false;
      }
 
      // Returning true otherwise.
      return true;
}
 
// Function to count the minimum number of swaps required.
int minSwaps(vector<int>& NUMS, int K)
{
      // Storing the size of NUMS.
      int N = NUMS.size();
 
      // Variable to store count of swaps.
      int count = 0;
 
      // Traversing through the array to make every element's remainder equal to its index's remainder.
      for (int i = 0; i < N; i++)
      {
            // Continuing the traversal if already equal.
            if (NUMS[i] % K == i % K)
                  continue;
 
            // Finding a suitable index to swap with the current index.
            for (int j = i + 1; j < N; j++)
            {
                  if (i % K == NUMS[j] % K && j % K == NUMS[i] % K)
                  {
                        swap(NUMS[i], NUMS[j]), count++;
                        break;
                  }
            }
 
            // Checking if already swapped.
            if (NUMS[i] % K == i % K)
                  continue;
 
            // Finding any element whose remainder is equal to current index remainder.
            for (int j = i + 1; j < N; j++)
            {
                  if (i % K == NUMS[j] % K)
                  {
                        swap(NUMS[i], NUMS[j]), count++;
                        break;
                  }
            }
      }
 
      // Returning the final count of swaps.
      return count;
}
 
// Main function
int main()
{
      // Taking input for size of array and the integer ‘K’.
      int N, K;
      cin >> N >> K;
 
      // Taking input of the array NUMS.
      vector<int> NUMS(N);
      for (int i = 0; i < N; i++)
            cin >> NUMS[i];
 
      // Checking if the desired result is possible through swapping.
      bool check = isSwapPossible(NUMS, K);
 
      // If it is not possible with any number of swaps.
      if (!check)
      {
            // Output when not possible with any number of swaps.
            cout << "Not possible to make remainders equal";
      }
      else
      {
            // Storing the minimum number of swaps.
            int ans = minSwaps(NUMS, K);
 
            // Final Output.
            cout << "Minimum number of swaps required are: " << ans;
      }
 
      return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Example

Input

5 3
1 2 1 0 0

Output

Minimum number of swaps required are: 2

Complexity Analysis

Time Complexity: O(N²)

Explanation: Due to the presence of two nested loops while finding the suitable element to swap, the total time taken becomes N * N, i.e., O(N²).

Auxiliary Space: O(2 * K)

Explanation: To check if the solution exists, the use of a 2-D vector occupies O(2 * K) space.

Check out this problem - First And Last Occurrences Of X

Key Takeaways

The given problem is an interesting mathematical problem involving the concepts of greedy algorithms and implementation. Our practice platform Coding Ninjas Studio is full of such amazing problems intended to teach you new concepts of competitive programming and enhance your problem-solving skills. Head over to our library section for many such interesting blogs. Keep practicing and growing.

Happy Coding!