Dado un número N , la tarea es encontrar la cantidad mínima de dígitos que se deben eliminar del número para que el número sea divisible por 25.
Entrada: N = 71345
Salida: 3
Explicación: Después de quitar 1, 3 y 5, el número se convierte en 75 y es divisible por 25.Entrada: N = 32505
Salida: 1
Explicación: Después de quitar 5 del último, el número se convierte en 3250 y es divisible por 25.
Planteamiento: Un número es divisible por 25 si sus dos últimas cifras son “00” o el número formado por sus dos últimas cifras es divisible por 25, como se explica en Comprobar si un número grande es divisible por 25 o no . Ahora, en este problema, verifique esta condición para todos los pares posibles en N y encuentre la cantidad mínima de dígitos que deben eliminarse. Si se encuentra que cualquier par de elementos satisface la condición anterior, entonces se puede formar un número que tenga estos dos elementos como los últimos dígitos, y luego será un múltiplo de 25.
A continuación se muestra la implementación del enfoque anterior:
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
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por hrithikgarg03188 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA