Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Example:
3.
Intuition
4.
Approach
5.
Algorithm
6.
Program
6.1.
Example
7.
Complexity Analysis
8.
Key Takeaways
Last Updated: Mar 27, 2024

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

gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

In arithmetic, the remainder is the integer "leftover" after dividing one integer by another to produce an integer quotient (integer division). In these types of problems, maths and implementation skills are both required. These problems are evenly asked in interviews and are easy to solve and explain. Practice is the key to solving such problems. Today, we will see one such problem based on remainder and implementation.

Problem Statement

An array of size ‘N’ containing only positive integers and a positive integer ‘K’ is given. The task is to find the minimum number of swaps required to make the remainder equal when every element and its index are divided by ‘K’.

Example:

Input: NUMS[] = {0, 0, 1, 1}, K = 2

Output: 1

Explanation: Elements at index 1 and index 2 are required to be swapped to make every element’s remainder with ‘K’ equal to its index remainder with ‘K’.

 

Input: NUMS[] = {4, 8, 7, 0, 6}, K = 3

Output: 2

Explanation: Following are the two swaps required:

  • Swap elements at index 0 and 4
  • Swap elements at index 1 and 2
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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;
}

Example

Input

5 3
1 2 1 0 0

Output

Minimum number of swaps required are: 2

Complexity Analysis

Time Complexity: O(N2)

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(N2).

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!

Previous article
Maximize score by rearranging Array such that absolute difference of first and last element is minimum
Next article
Minimize Flips to Make the Binary String as all 1s by Flipping Characters in a Substring of size K Repeatedly
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass