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 theint 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 Codeint 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 approachimport 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 thedef 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 Coden = 71345ans = minDigits(n)if (ans == 10 ** 9): print(-1)else: print(ans)# This code is contributed by Saurabh Jaiswal; |
C#
// C# program for the above approachusing System;using System.Collections;class GFG{// Function to find thestatic 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 Codepublic 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> |
Output
3
Time Complexity: O(N2)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
