1.
Introduction
2.
Problem statement
2.1.
Sample Examples
3.
Approach
3.1.
Steps of algorithm
3.2.
Implementation in C++
3.3.
Complexity Analysis
4.
4.1.
What is the use of the prev permutation function in C++?
4.2.
How to find the old permutations of a string?
4.3.
What are the types of permutations?
4.4.
How to calculate the factorial of a number?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

# Minimum Adjacent Swaps of the Digits Required to Make N Divisible by K

## Introduction

This problem is loosely based on the concept of obtaining certain permutations of an array and therefore before directly jumping to the question, let’s understand one of the essential functions that help in the determination of the possible Permutation of string or array  called the next_permutation function.

next_permutation:

It rearranges the elements into the next lexicographically greater permutation in the range [first, last]. A permutation is each one of the possible arrangements the elements can take.

It returns a true if the function can rearrange the object as a lexicographically greater permutation, else it returns a false.

(Also see Data Structures)

## Problem statement

We are given a number N and a number K. Our task is to find the minimum adjacent swaps of the digits required to make N divisible by K.

### Sample Examples

Example 1:

``````Input: N = 234567, K = 5
Output: 2

Explanation
Swap the 4th and 5th digits, N = 234657
Swap the 5th and last digits, N = 234675``````

Example 2:

``````Input: N= 4350609, K = 100
Output: 3

Explanation
Swap the last and second last digits, N = 4350690
Swap the 4th and 5th digits, N = 4356090
Swap the 5th and 6th digits, N = 4356900``````

Also see, Euclid GCD Algorithm

## Approach

The idea is straightforward, generate all the possible permutations of the given number N.

Check for every permutation; if it is divisible by K or not.

If the current permutation is divisible by K, then count the minimum swaps to make the permutation from the given number. Else move to another permutation of the number.

Calculate the minimum of all of these count values. Finally, return the value of minimum adjacent swaps.

To generate all the possible permutations, we will use the next_permutation function.

### Steps of algorithm

minimum_swaps():

• Convert the given number N to a string of characters using the to_string() function.
• Create a mnm_swaps = 0 variable to store the result.
• Sort the number string in non-decreasing order using the sort function.
• Iterate through all the permutations of the number string using the next_permutation.
• If the current permutation is divisible by K, count the minimum swaps required to make the permutation from the number string. Else move to the next greater permutation.
• Update the current minimum swaps in the mnm_swaps variable.
• Return the value of the mnm_swaps.

count_swaps():

• For the first and second strings, use pointers i and j, respectively. Set i and j to 0 to begin.
• Iterate over the first string and increment the value to j to find the position j where str1[j] = str2[i]. Continue swapping adjacent elements j and j – 1 and decrementing j until it equals i.
• Now the ith element of the first string is equal to the second string, increment the value of i.
• This technique will yield the minimum number of steps as there are no unnecessary swaps.

Below is the implementation of the above approach:

### Implementation in C++

``````#include <bits/stdc++.h>
using namespace std;

int count_swaps(string str1, string str2, int size)
{
int i = 0, j = 0;

int swaps = 0;

while (i < size)
{
j = i;

while (str1[j] != str2[i])
{
j = j + 1;
}

while (i < j)
{
char tmp = str1[j];
str1[j] = str1[j - 1];
str1[j - 1] = tmp;
j = j - 1;
swaps = swaps + 1;
}

i = i + 1;
}

return swaps;
}

int minimum_swaps(int N, int K)
{
string num_str = to_string(N);

sort(num_str.begin(), num_str.end());

int mnm_swaps = INT_MAX;

do {
if (stoi(num_str) % K == 0)

mnm_swaps = min(mnm_swaps, count_swaps(to_string(N), num_str, num_str.length()));
} while (next_permutation(num_str.begin(), num_str.end()));

return mnm_swaps;
}

int main()
{
int N = 4350609;
int K = 100;
cout << minimum_swaps(N, K);

return 0;
}``````

Output:

``3``

### Complexity Analysis

Time complexity: O((logN)!*(logN)^2)

Since we are using the next permutation function having a time complexity of O(d!*d) and for every permutation, we are checking the minimum number of swaps required which take O(d) time where d is the maximum number of digits in N.

So, the overall time complexity of the algorithm will be O(d!*d*d) -> O((d*log10)! *(d *log10)^2) -> O((log10^d)! * (log10^d)^2) -> O((logN)!*(logN)^2).

Space complexity: O(logN), as we are using a string of size d.

So, the space complexity of the algorithm -> O(d) -> O(d*log10) -> O(log10^d) = O(logN) where, d is the maximum number of digits in N and N is the given number.
Check out this problem - Maximum Product Subarray

### What is the use of the prev permutation function in C++?

The prev permutation() function in C++ is used to reorder the elements in the range [first, last) into the previous lexicographically ordered permutation. Each of several possible ways to order or arrange a set or number of things is defined as a permutation.

### How to find the old permutations of a string?

The steps to find the previous permutation are as follows:

• Find the largest index i such that str[i – 1] > str[i].
• Find the largest index j where j >= i and str[j] = str[i – 1].
• Str[j] and str[i – 1] should be swapped.
• Reverse the sub-array starting at str[i].

### What are the types of permutations?

Permutation can be divided into the following categories:

• Permutation in which repetition is prohibited.
• Permutation in which repetition is allowed.
• The permutation of non-distinct objects.
• Circular permutation.

### How to calculate the factorial of a number?

The product of all positive integers less than or equal to a given positive integer is known as the factorial of that number. It is denoted by that integer and an exclamation point.

Factorial(n) = n! = n * (n-1) * (n-2) * (n-3) ……… * 1.

## Conclusion

This article discussed the next_permutation function and the approach to finding the minimum adjacent swaps of the digits required to make N divisible by K using the next permutation function and its C++ code.

Want to brainstorm more? Go and check out these recommended articles:

What are you waiting for? Let's move towards practicing more questions:

Check out some of the amazing Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, etc. along with some Contests and Interview Experiences only on Coding Ninjas Studio

Cheers!