Count of digits to be removed to make a number divisible by 25
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++ 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 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
# 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# 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.
<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)
Optimized Approach
This solution leverages a more efficient approach by directly searching for valid pairs of digits from the end of the number that would form a number divisible by 25, thus reducing the complexity.
A number is divisible by 25 if its last two digits are either 00, 25, 50, or 75. Instead of checking all pairs, we can directly look for these specific pairs from the end of the number and calculate the minimum digits to remove.
Approach Explanation:
- Convert the number to a string to easily manipulate and access individual digits.
- Check for valid pairs (00, 25, 50, 75) from the end of the number.
- Calculate the number of digits to remove to form the valid pair at the end.
- Track the minimum number of digits removed for all valid pairs.
Code Explanation:
- Convert the number to a string for easy access to digits.
- Iterate through the string to find positions of valid pairs.
- Compute the digits to remove and track the minimum.
public class MinDigits {
// Helper function to find the minimum digits to remove
// for a specific pair
private static int findMinRemovals(String s,
String pair, int N)
{
int pos2 = s.lastIndexOf(
pair.charAt(1)); // Find the last occurrence of
// the second digit in the pair
if (pos2 == -1) {
return Integer
.MAX_VALUE; // If the second digit is not
// found, return a large value
}
int pos1 = s.lastIndexOf(
pair.charAt(0),
pos2 - 1); // Find the last occurrence of the
// first digit before pos2
if (pos1 == -1) {
return Integer
.MAX_VALUE; // If the first digit is not
// found before pos2, return a
// large value
}
return (N - pos2 - 1)
+ (pos2 - pos1
- 1); // Calculate the removals needed
}
public static int minDigits(int n)
{
String s = Integer.toString(
n); // Convert the number to a string
int N = s.length(); // Get the length of the string
int minRemovals
= Integer
.MAX_VALUE; // Initialize the minimum
// removals to a large value
// Check for all valid pairs
String[] validPairs
= { "00", "25", "50",
"75" }; // Valid pairs to form numbers
// ending with 00, 25, 50, 75
for (String pair : validPairs) {
minRemovals = Math.min(
minRemovals,
findMinRemovals(
s, pair, N)); // Find the minimum
// removals for each pair
}
return minRemovals == Integer.MAX_VALUE
? -1
: minRemovals; // Return -1 if no valid pair is
// found
}
public static void main(String[] args)
{
int n = 71345;
System.out.println(minDigits(
n)); // Driver code to test the function
}
}
def minDigits(n):
s = str(n)
N = len(s)
min_removals = float('inf')
# Helper function to find the minimum digits to remove for a specific pair
def find_min_removals(pair):
pos2 = s.rfind(pair[1])
if pos2 == -1:
return float('inf')
pos1 = s.rfind(pair[0], 0, pos2)
if pos1 == -1:
return float('inf')
return (N - pos2 - 1) + (pos2 - pos1 - 1)
# Check for all valid pairs
valid_pairs = ['00', '25', '50', '75']
for pair in valid_pairs:
min_removals = min(min_removals, find_min_removals(pair))
return min_removals if min_removals != float('inf') else -1
# Driver Code
n = 71345
print(minDigits(n))
class MinDigits {
// Helper function to find the minimum digits to remove
// for a specific pair
static findMinRemovals(s, pair, N) {
let pos2 = s.lastIndexOf(pair.charAt(1));
if (pos2 === -1) {
// If the second digit is not found, return a large value
return Number.MAX_SAFE_INTEGER;
}
// Find the last occurrence of the first digit before pos2
let pos1 = s.lastIndexOf(pair.charAt(0), pos2 - 1);
if (pos1 === -1) {
// If the first digit is not found before pos2, return a large value
return Number.MAX_SAFE_INTEGER;
}
return (N - pos2 - 1) + (pos2 - pos1 - 1); // Calculate the removals needed
}
static minDigits(n) {
let s = n.toString(); // Convert the number to a string
let N = s.length; // Get the length of the string
// Initialize the minimum removals to a large value
let minRemovals = Number.MAX_SAFE_INTEGER;
// Check for all valid pairs
// Valid pairs to form numbers ending with 00, 25, 50, 75
const validPairs = ["00", "25", "50", "75"];
for (let pair of validPairs) {
// Find the minimum removals for each pair
minRemovals = Math.min(minRemovals, this.findMinRemovals(s, pair, N));
}
// Return -1 if no valid pair is found
return minRemovals === Number.MAX_SAFE_INTEGER ? -1 : minRemovals;
}
}
// Driver code to test the function
let n = 71345;
console.log(MinDigits.minDigits(n));
Output
3
Time Complexity: O(N)
Space Complexity: O(1)