Given a number N, the task is to find the minimum number of digits that needs to be removed from the number so that the number will become divisible by 25.
Input: N = 71345
Output: 3
Explanation: After removing 1, 3 and 4, the number becomes 75 and it is divisible by 25.Input: N = 32505
Output: 1
Explanation: After removing 5 from last, number becomes 3250 and it is divisible by 25.
Approach: A number is divisible by 25 if its last two digits are “00” or the number formed by its last two digits is divisible by 25, as explained in Check if a large number is divisible by 25 or not. Now, in this problem, check this condition for all possible pairs in N and find the minimum number of digits that need to be removed. If any pair of elements is found to satisfy the above condition, then a number can be formed having these two elements as the last digits, and then it will be a multiple of 25.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the int minDigits( int n) { vector< char > str; // Convert number into string int i = 0; while (n != 0) { int rem = n % 10; // convert int into char // by adding '0' char ch = (rem + '0' ); str.push_back(ch); n /= 10; } // Reverse string reverse(str.begin(), str.end()); int ans = INT_MAX; int N = str.size(); for ( int i = 0; i < N; i++) { for ( int j = i + 1; j < N; j++) { // Number formed by // last two digits int num = (str[i] - '0' ) * 10 + (str[j] - '0' ); if (num % 25 == 0) { // Count of unwanted digits // between i and j int a = j - i - 1; // Count of unwanted // digits after j int b = N - (j + 1); ans = min(ans, a + b); } } } return ans; } // Driver Code int main() { int n = 71345; int ans = minDigits(n); if (ans == INT_MAX) { cout << -1; } else { cout << ans; } return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to find the static int minDigits( int n) { Vector<Character> str = new Vector<Character>(); // Convert number into String int i = 0 ; while (n != 0 ) { int rem = n % 10 ; // convert int into char // by adding '0' char ch = ( char ) (rem + '0' ); str.add(ch); n /= 10 ; } // Reverse String Collections.reverse(str); int ans = Integer.MAX_VALUE; int N = str.size(); for (i = 0 ; i < N; i++) { for ( int j = i + 1 ; j < N; j++) { // Number formed by // last two digits int num = (str.get(i) - '0' ) * 10 + (str.get(j) - '0' ); if (num % 25 == 0 ) { // Count of unwanted digits // between i and j int a = j - i - 1 ; // Count of unwanted // digits after j int b = N - (j + 1 ); ans = Math.min(ans, a + b); } } } return ans; } // Driver Code public static void main(String[] args) { int n = 71345 ; int ans = minDigits(n); if (ans == Integer.MAX_VALUE) { System.out.print(- 1 ); } else { System.out.print(ans); } } } // This code is contributed by 29AjayKumar |
Python3
# Python code for the above approach # Function to find the def minDigits(n): str = [] # Convert number into string i = 0 while (n ! = 0 ): rem = n % 10 # convert int into char # by adding '0' ch = chr (rem + ord ( '0' )) str .append(ch) n = (n / / 10 ) # Reverse string str .reverse() ans = 10 * * 9 N = len ( str ) for i in range (N): for j in range (i + 1 , N): # Number formed by # last two digits num = ( ord ( str [i]) - ord ( '0' )) * 10 + ( ord ( str [j]) - ord ( '0' )) if (num % 25 = = 0 ): # Count of unwanted digits # between i and j a = j - i - 1 # Count of unwanted # digits after j b = N - (j + 1 ) ans = min (ans, a + b) return ans # Driver Code n = 71345 ans = minDigits(n) if (ans = = 10 * * 9 ): print ( - 1 ) else : print (ans) # This code is contributed by Saurabh Jaiswal; |
C#
// C# program for the above approach using System; using System.Collections; class GFG { // Function to find the static int minDigits( int n) { ArrayList str = new ArrayList(); // Convert number into string while (n != 0) { int rem = n % 10; // convert int into char // by adding '0' char ch = ( char )(rem + '0' ); str.Add(ch); n /= 10; } // Reverse string str.Reverse(); int ans = Int32.MaxValue; int N = str.Count; for ( int i = 0; i < N; i++) { for ( int j = i + 1; j < N; j++) { // Number formed by // last two digits int num = (( char )str[i] - '0' ) * 10 + (( char )str[j] - '0' ); if (num % 25 == 0) { // Count of unwanted digits // between i and j int a = j - i - 1; // Count of unwanted // digits after j int b = N - (j + 1); ans = Math.Min(ans, a + b); } } } return ans; } // Driver Code public static void Main() { int n = 71345; int ans = minDigits(n); if (ans == Int32.MaxValue) { Console.Write(-1); } else { Console.Write(ans); } } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach // Function to find the function minDigits(n) { let str = []; // Convert number into string let i = 0; while (n != 0) { let rem = n % 10; // convert int into char // by adding '0' let ch = String.fromCharCode(rem + '0' .charCodeAt(0)); str.push(ch); n = Math.floor(n / 10) } // Reverse string str.reverse(); let ans = Number.MAX_VALUE; let N = str.length; for (let i = 0; i < N; i++) { for (let j = i + 1; j < N; j++) { // Number formed by // last two digits let num = (str[i].charCodeAt(0) - '0' .charCodeAt(0)) * 10 + (str[j].charCodeAt(0) - '0' .charCodeAt(0)); if (num % 25 == 0) { // Count of unwanted digits // between i and j let a = j - i - 1; // Count of unwanted // digits after j let b = N - (j + 1); ans = Math.min(ans, a + b); } } } return ans; } // Driver Code let n = 71345; let ans = minDigits(n); if (ans == Number.MAX_VALUE) { document.write(-1); } else { document.write(ans); } // This code is contributed by Potta Lokesh </script> |
3
Time Complexity: O(N2)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!