Minimum number of given moves required to make N divisible by 25

0 0 9 minutes read

Given a number N(1 ? N ? 10¹⁸) 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.
Examples:

Input: N = 7560
Output: 1
swap(5, 6) and N becomes 7650 which is divisible by 25
Input: N = 100
Output: 0

Approach: 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. Let’s place these digits to the last two positions in the number. But, now the number can contain a leading zero. Find the leftmost non-zero digit and move it to the first position. Then if the current number is divisible by 25 try to update the answer with the number of swaps. The minimum number of swaps across all of these operations is the required answer.
Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the minimum number 
// of moves required to make n divisible 
// by 25
int minMoves(long long n)
{
 
    // Convert number into string
    string s = to_string(n);
 
    // To store required answer
    int ans = INT_MAX;
 
    // Length of the string
    int len = s.size();
 
    // To check all possible pairs
    for (int i = 0; i < len; ++i) {
        for (int j = 0; j < len; ++j) {
            if (i == j)
                continue;
 
            // Make a duplicate string
            string t = s;
            int cur = 0;
 
            // Number of swaps required to place
            // ith digit in last position
            for (int k = i; k < len - 1; ++k) {
                swap(t[k], t[k + 1]);
                ++cur;
            }
 
            // Number of swaps required to place
            // jth digit in 2nd last position
            for (int k = j - (j > i); k < len - 2; ++k) {
                swap(t[k], t[k + 1]);
                ++cur;
            }
 
            // Find first non zero digit
            int pos = -1;
            for (int k = 0; k < len; ++k) {
                if (t[k] != '0') {
                    pos = k;
                    break;
                }
            }
 
            // Place first non zero digit
            // in the first position
            for (int k = pos; k > 0; --k) {
                swap(t[k], t[k - 1]);
                ++cur;
            }
 
            // Convert string to number
            long long nn = atoll(t.c_str());
 
            // If this number is divisible by 25
            // then cur is one of the possible answer
            if (nn % 25 == 0)
                ans = min(ans, cur);
        }
    }
 
    // If not possible
    if (ans == INT_MAX)
        return -1;
 
    return ans;
}
 
// Driver code
int main()
{
    long long n = 509201;
    cout << minMoves(n);
    return 0;
}

Java

// Java implementation of the approach
import java.io.*;
class GFG
{
     
    // Function to return the minimum number 
    // of moves required to make n divisible 
    // by 25
    static int minMoves(int n)
    {
     
        // Convert number into string
        String s = Integer.toString(n);
         
        // To store required answer
        int ans = Integer.MAX_VALUE;
     
        // Length of the string
        int len = s.length();
     
        // To check all possible pairs
        for (int i = 0; i < len; ++i) 
        {
            for (int j = 0; j < len; ++j) 
            {
                if (i == j)
                    continue;
     
                // Make a duplicate string
                char t [] = s.toCharArray();
                int cur = 0;
     
                // Number of swaps required to place
                // ith digit in last position
                for (int k = i; k < len - 1; ++k) 
                {
                    swap(t, k, k + 1);
                    ++cur;
                }
     
                // Number of swaps required to place
                // jth digit in 2nd last position
                for (int k = j - ((j > i)? 1 : 0 ); k < len - 2; ++k) 
                {
                    swap(t, k, k + 1);
                    ++cur;
                }
     
                // Find first non zero digit
                int pos = -1;
                for (int k = 0; k < len; ++k)
                {
                    if (t[k] != '0') 
                    {
                        pos = k;
                        break;
                    }
                }
     
                // Place first non zero digit
                // in the first position
                for (int k = pos; k > 0; --k) 
                {
                    swap(t, k, k - 1);
                    ++cur;
                }
     
                // Convert string to number
                long nn = Integer.parseInt(String.valueOf(t));
     
                // If this number is divisible by 25
                // then cur is one of the possible answer
                if (nn % 25 == 0)
                    ans = Math.min(ans, cur);
            }
        }
     
        // If not possible
        if (ans == Integer.MAX_VALUE)
            return -1;
     
        return ans;
    }
     
    static void swap(char t [], int i, int j) 
    { 
        char temp = t[i]; 
        t[i] = t[j]; 
        t[j] = temp; 
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int n = 509201;
        System.out.println(minMoves(n));
    }
}
 
// This code is contributed by Archana_Kumari

Python3

# Python3 implementation of the approach
import sys
 
# Function to return the minimum number 
# of moves required to make n divisible 
# by 25
def minMoves(n):
 
    # Convert number into string
    s = str(n);
 
    # To store required answer
    ans = sys.maxsize;
 
    # Length of the string
    len1 = len(s);
 
    # To check all possible pairs
    for i in range(len1): 
        for j in range(len1): 
            if (i == j):
                continue;
 
            # Make a duplicate string
            t = s;
            cur = 0;
 
            # Number of swaps required to place
            # ith digit in last position
            list1 = list(t);
            for k in range(i,len1 - 1):
                e = list1[k];
                list1[k] = list1[k + 1];
                list1[k + 1] = e;
                cur += 1;
            t = ''.join(list1);
 
            # Number of swaps required to place
            # jth digit in 2nd last position
            list1 = list(t);
            for k in range(j - (j > i),len1 - 2): 
                e = list1[k];
                list1[k] = list1[k + 1];
                list1[k + 1] = e;
                cur += 1;
            t = ''.join(list1);
 
            # Find first non zero digit
            pos = -1;
            for k in range(len1): 
                if (t[k] != '0'): 
                    pos = k;
                    break;
 
            # Place first non zero digit
            # in the first position
            for k in range(pos,0,-1):
                e = list1[k];
                list1[k] = list1[k + 1];
                list1[k + 1] = e;
                cur += 1;
            t = ''.join(list1);
 
 
            # Convert string to number
            nn = int(t);
 
            # If this number is divisible by 25
            # then cur is one of the possible answer
            if (nn % 25 == 0):
                ans = min(ans, cur);
 
    # If not possible
    if (ans == sys.maxsize):
        return -1;
 
    return ans;
 
# Driver code
n = 509201;
print(minMoves(n));
 
# This code is contributed
# by chandan_jnu

C#

// C# implementation of the approach
using System;
 
class GFG
{
     
    // Function to return the minimum number 
    // of moves required to make n divisible 
    // by 25
    static int minMoves(int n)
    {
     
        // Convert number into string
        string s = n.ToString();
         
        // To store required answer
        int ans = Int32.MaxValue;
     
        // Length of the string
        int len = s.Length;
     
        // To check all possible pairs
        for (int i = 0; i < len; ++i) 
        {
            for (int j = 0; j < len; ++j) 
            {
                if (i == j)
                    continue;
     
                // Make a duplicate string
                char[] t = s.ToCharArray();
                int cur = 0;
     
                // Number of swaps required to place
                // ith digit in last position
                for (int k = i; k < len - 1; ++k) 
                {
                    swap(t, k, k + 1);
                    ++cur;
                }
     
                // Number of swaps required to place
                // jth digit in 2nd last position
                for (int k = j - ((j > i)? 1 : 0 ); k < len - 2; ++k) 
                {
                    swap(t, k, k + 1);
                    ++cur;
                }
     
                // Find first non zero digit
                int pos = -1;
                for (int k = 0; k < len; ++k)
                {
                    if (t[k] != '0') 
                    {
                        pos = k;
                        break;
                    }
                }
     
                // Place first non zero digit
                // in the first position
                for (int k = pos; k > 0; --k) 
                {
                    swap(t, k, k - 1);
                    ++cur;
                }
     
                // Convert string to number
                int nn = Convert.ToInt32(new String(t));
     
                // If this number is divisible by 25
                // then cur is one of the possible answer
                if (nn % 25 == 0)
                    ans = Math.Min(ans, cur);
            }
        }
     
        // If not possible
        if (ans == Int32.MaxValue)
            return -1;
     
        return ans;
    }
     
    static void swap(char []t, int i, int j) 
    { 
        char temp = t[i]; 
        t[i] = t[j]; 
        t[j] = temp; 
    }
     
    // Driver code
    static void Main()
    {
        int n = 509201;
        Console.WriteLine(minMoves(n));
    }
}
 
// This code is contributed by mits

PHP

<?php
// PHP implementation of the approach
 
// Function to return the minimum number 
// of moves required to make n divisible 
// by 25
function minMoves($n)
{
 
    // Convert number into string
    $s = strval($n);
 
    // To store required answer
    $ans = PHP_INT_MAX;
 
    // Length of the string
    $len = strlen($s);
 
    // To check all possible pairs
    for ($i = 0; $i < $len; ++$i) 
    {
        for ($j = 0; $j < $len; ++$j) 
        {
            if ($i == $j)
                continue;
 
            // Make a duplicate string
            $t = $s;
            $cur = 0;
 
            // Number of swaps required to place
            // ith digit in last position
            for ($k = $i;$k < $len - 1; ++$k) 
            {
                $e=$t[$k];
                $t[$k]=$t[$k + 1];
                $t[$k+1]=$e;
                ++$cur;
            }
 
            // Number of swaps required to place
            // jth digit in 2nd last position
            for ($k = $j - ($j > $i); 
                 $k < $len - 2; ++$k) 
            {
                $e = $t[$k];
                $t[$k] = $t[$k + 1];
                $t[$k + 1] = $e;
                ++$cur;
            }
 
            // Find first non zero digit
            $pos = -1;
            for ($k = 0; $k < $len; ++$k) 
            {
                if ($t[$k] != '0') 
                {
                    $pos = $k;
                    break;
                }
            }
 
            // Place first non zero digit
            // in the first position
            for ($k = $pos; $k > 0; --$k) 
            {
                $e = $t[$k];
                $t[$k] = $t[$k + 1];
                $t[$k + 1] = $e;
                ++$cur;
            }
 
            // Convert string to number
            $nn = intval($t);
 
            // If this number is divisible by 25
            // then cur is one of the possible answer
            if ($nn % 25 == 0)
                $ans = min($ans, $cur);
        }
    }
 
    // If not possible
    if ($ans == PHP_INT_MAX)
        return -1;
 
    return $ans;
}
 
// Driver code
$n = 509201;
echo minMoves($n);
 
// This code is contributed
// by chandan_jnu
?>

Javascript

<script>
    // Javascript implementation of the approach
     
    // Function to return the minimum number 
    // of moves required to make n divisible 
    // by 25
    function minMoves(n)
    {
       
        // Convert number into string
        let s = n.toString();
           
        // To store required answer
        let ans = Number.MAX_VALUE;
       
        // Length of the string
        let len = s.length;
       
        // To check all possible pairs
        for (let i = 0; i < len; ++i) 
        {
            for (let j = 0; j < len; ++j) 
            {
                if (i == j)
                    continue;
       
                // Make a duplicate string
                let t = s.split('');
                let cur = 0;
       
                // Number of swaps required to place
                // ith digit in last position
                for (let k = i; k < len - 1; ++k) 
                {
                    swap(t, k, k + 1);
                    ++cur;
                }
       
                // Number of swaps required to place
                // jth digit in 2nd last position
                for (let k = j - ((j > i)? 1 : 0 ); k < len - 2; ++k) 
                {
                    swap(t, k, k + 1);
                    ++cur;
                }
       
                // Find first non zero digit
                let pos = -1;
                for (let k = 0; k < len; ++k)
                {
                    if (t[k] != '0') 
                    {
                        pos = k;
                        break;
                    }
                }
       
                // Place first non zero digit
                // in the first position
                for (let k = pos; k > 0; --k) 
                {
                    swap(t, k, k - 1);
                    ++cur;
                }
       
                // Convert string to number
                let nn = parseInt(t.join(""));
       
                // If this number is divisible by 25
                // then cur is one of the possible answer
                if (nn % 25 == 0)
                    ans = Math.min(ans, cur);
            }
        }
       
        // If not possible
        if (ans == Number.MAX_VALUE)
            return -1;
       
        return ans;
    }
       
    function swap(t, i, j) 
    { 
        let temp = t[i]; 
        t[i] = t[j]; 
        t[j] = temp; 
    }
     
    let n = 509201;
      document.write(minMoves(n));
 
// This code is contributed by mukesh07.
</script>

Output:

Time Complexity: O(|n|³)
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 zambiatek!