Minimum number of given moves required to make N divisible by 25 using C++.

Problem statement

Given a number N without leading zeros. The task is to find the minimum number of moves required to make N divisible by 25. At each move, one can swap any two adjacent digits and make sure that at any time number must not contain any leading zeros. If it is not possible to make N divisible by 25 then print -1

If N = 5071 then 4 moves are required to make it divisible by 25

5071 → 5701 → 7501 → 7510 → 7150

Algorithm

1. Iterate over all pairs of digits in the number. Let the first digit in the pair is at position ‘i’ and the second is at position ‘j’. 2. Place these digits to the last two positions in the number 3. If the number has a leading zero. Find the leftmost nonzero digit and move it to the first position. 4. If the current number is divisible by 25 then update the answer with the number of swaps

Example

#include <iostream> #include <algorithm> #include <string> #include <climits> using namespace std; int requiredMoves(long long n){    string str = to_string(n);    int ans = INT_MAX;    int len = str.size();    for (int i = 0; i < len; ++i) {       for (int j = 0; j < len; ++j) {          if (i == j)             continue;       string temp = str;       int cnt = 0;       for (int k = i; k < len - 1; ++k) {          swap(temp[k], temp[k + 1]);          ++cnt;       }       for (int k = j - (j > i); k < len - 2; ++k) {          swap(temp[k], temp[k + 1]);          ++cnt;       }       int pos = -1;       for (int k = 0; k < len; ++k) {          if (temp[k] != '0') {             pos = k;             break;          }       }       for (int k = pos; k > 0; --k) {          swap(temp[k], temp[k - 1]);          ++cnt;       }       long long num = atoll(temp.c_str());       if (num % 25 == 0)          ans = min(ans, cnt);       }    }    if (ans == INT_MAX)       return -1;    return ans; } int main(){    int n = 5071;    cout << "Minimum required moves: " << requiredMoves(n) << endl;    return 0; }

Output

When you compile and execute the above program. It generates the following output −

Minimum required moves: 4