Dado un número N , la tarea es contar el número mínimo de dígitos que se quitarán de N para hacerlo divisible por 4 .
Ejemplos:
Entrada: N = 12367
Salida: 1
Explicación: Quitar 7 del número 1236 hace que el número sea divisible por 4. Por lo tanto, la cantidad mínima de dígitos que se quitarán es 1.Entrada: N = 243775
Salida: 4
Enfoque: La idea se basa en la regla básica de divisibilidad por 4 de que si el número formado por los dos últimos dígitos de un número es divisible por 4, entonces el número original es divisible por 4 . Ahora, la idea es comprobar desde el último si el número formado por dos dígitos es divisible por 4 o no. Siga los pasos a continuación para resolver el problema:
- Convierta el número N en una string y guárdelo en S .
- Inicialice una variable ans con la longitud de la string S , para almacenar la cantidad mínima de eliminaciones requeridas.
- Atraviese la string S desde el final usando la variable i .
- Iterar sobre el rango [i – 1, 0] usando la variable j .
- Si el número formado por S[j] y S[i] es divisible por 4, realice los siguientes pasos:
- Almacene el número de dígitos entre el índice i y j en una variable, digamos K1 , que es igual a (i – j – 1) y almacene el número de dígitos que preceden al índice i en una variable, digamos K2 , que es igual a (N – yo – 1) . La suma de K1 y K2 representa el número de dígitos que se eliminarán de modo que S[j] y S[i] se conviertan en los dos últimos dígitos del nuevo número.
- Si el valor de (K1 + K2) es menor que el valor de ans , actualice ans a (K1 + K2) .
- Si el número formado por S[j] y S[i] es divisible por 4, realice los siguientes pasos:
- Iterar sobre el rango [i – 1, 0] usando la variable j .
- Después de recorrer la string, si el valor de ans aún no ha cambiado, verifique si algún S[i] es divisible por 4. Si es cierto, actualice ans como (longitud de S – 1) .
- Después de completar los pasos anteriores, imprima el valor de ans como resultado.
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 count the minimum number
// of digits required to be removed to
// make a given number divisible by 4
void minimumDeletions(string s)
{
// Store the size of the string
int n = s.length();
// Stores the required result
int ans = n;
// Check for every pair of digits
// if the number formed by them
// is divisible by 4 or not
for (int i = n - 1; i >= 0; i--) {
// Store s[i] in a variable
int t = s[i] - '0';
// If it is divisible by 2
if (t % 2 == 0) {
for (int j = i - 1;
j >= 0; j--) {
// Store the number formed
// by s[j] and s[i]
int num = (s[j] - '0')
* 10
+ t;
// Check if it is
// divisible by 4
if (num % 4 == 0) {
// Store the number of digits
// required to be deleted
int k1 = i - j - 1;
int k2 = n - i - 1;
// Update ans
ans = min(ans,
k1 + k2);
}
}
}
}
// If value of ans is unchanged, then
// check if any s[i] is divisible by 4
if (ans == n) {
for (int i = 0; i < n; i++) {
int num = s[i] - '0';
// If true, update ans to n - 1
if (num % 4 == 0) {
ans = n - 1;
}
}
}
// Print the result
cout << ans;
}
// Driver Code
int main()
{
string str = "12367";
minimumDeletions(str);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to count the minimum number
// of digits required to be removed to
// make a given number divisible by 4
static void minimumDeletions(String s)
{
// Store the size of the string
int n = s.length();
// Stores the required result
int ans = n;
// Check for every pair of digits
// if the number formed by them
// is divisible by 4 or not
for (int i = n - 1; i >= 0; i--) {
// Store s[i] in a variable
int t = s.charAt(i) - '0';
// If it is divisible by 2
if (t % 2 == 0) {
for (int j = i - 1; j >= 0; j--) {
// Store the number formed
// by s[j] and s[i]
int num = (s.charAt(j) - '0') * 10 + t;
// Check if it is
// divisible by 4
if (num % 4 == 0) {
// Store the number of digits
// required to be deleted
int k1 = i - j - 1;
int k2 = n - i - 1;
// Update ans
ans = Math.min(ans, k1 + k2);
}
}
}
}
// If value of ans is unchanged, then
// check if any s[i] is divisible by 4
if (ans == n) {
for (int i = 0; i < n; i++) {
int num = s.charAt(i) - '0';
// If true, update ans to n - 1
if (num % 4 == 0) {
ans = n - 1;
}
}
}
// Print the result
System.out.println(ans);
}
// Driver Code
static public void main(String[] args)
{
String str = "12367";
minimumDeletions(str);
}
}
// This code is contributed by ukasp.
Python3
# Python3 program for the above approach
# Function to count the minimum number
# of digits required to be removed to
# make a given number divisible by 4
def minimumDeletions(s):
# Store the size of the string
n = len(s)
# Stores the required result
ans = n
# Check for every pair of digits
# if the number formed by them
# is divisible by 4 or not
for i in range(n - 1, -1, -1):
# Store s[i] in a variable
t = ord(s[i]) - ord('0')
# If it is divisible by 2
if (t % 2 == 0):
for j in range(i - 1, -1, -1):
# Store the number formed
# by s[j] and s[i]
num = (ord(s[j]) - ord('0'))* 10 + t
# Check if it is
# divisible by 4
if (num % 4 == 0):
# Store the number of digits
# required to be deleted
k1 = i - j - 1
k2 = n - i - 1
# Update ans
ans = min(ans, k1 + k2)
# If value of ans is unchanged, then
# check if any s[i] is divisible by 4
if (ans == n):
for i in range(n):
num = ord(s[i]) - ord('0')
# If true, update ans to n - 1
if (num % 4 == 0):
ans = n - 1
# Print the result
print (ans)
# Driver Code
if __name__ == '__main__':
str = "12367"
minimumDeletions(str)
# This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
class GFG
{
// Function to count the minimum number
// of digits required to be removed to
// make a given number divisible by 4
static void minimumDeletions(string s)
{
// Store the size of the string
int n = s.Length;
// Stores the required result
int ans = n;
// Check for every pair of digits
// if the number formed by them
// is divisible by 4 or not
for (int i = n - 1; i >= 0; i--) {
// Store s[i] in a variable
int t = s[i] - '0';
// If it is divisible by 2
if (t % 2 == 0) {
for (int j = i - 1;
j >= 0; j--) {
// Store the number formed
// by s[j] and s[i]
int num = (s[j] - '0')
* 10
+ t;
// Check if it is
// divisible by 4
if (num % 4 == 0) {
// Store the number of digits
// required to be deleted
int k1 = i - j - 1;
int k2 = n - i - 1;
// Update ans
ans = Math.Min(ans,
k1 + k2);
}
}
}
}
// If value of ans is unchanged, then
// check if any s[i] is divisible by 4
if (ans == n) {
for (int i = 0; i < n; i++) {
int num = s[i] - '0';
// If true, update ans to n - 1
if (num % 4 == 0) {
ans = n - 1;
}
}
}
// Print the result
Console.WriteLine(ans);
}
// Driver Code
static public void Main()
{
string str = "12367";
minimumDeletions(str);
}
}
// This code is contributed by sanjoy_62.
Javascript
<script>
// Javascript program for the above approach
// Function to count the minimum number
// of digits required to be removed to
// make a given number divisible by 4
function minimumDeletions(s)
{
// Store the size of the string
let n = s.length;
// Stores the required result
let ans = n;
// Check for every pair of digits
// if the number formed by them
// is divisible by 4 or not
for(let i = n - 1; i >= 0; i--)
{
// Store s[i] in a variable
let t = s[i] - '0';
// If it is divisible by 2
if (t % 2 == 0)
{
for(let j = i - 1;
j >= 0; j--)
{
// Store the number formed
// by s[j] and s[i]
let num = (s[j] - '0') * 10 + t;
// Check if it is
// divisible by 4
if (num % 4 === 0)
{
// Store the number of digits
// required to be deleted
let k1 = i - j - 1;
let k2 = n - i - 1;
// Update ans
ans = Math.min(ans,
k1 + k2);
}
}
}
}
// If value of ans is unchanged, then
// check if any s[i] is divisible by 4
if (ans === n)
{
for(let i = 0; i < n; i++)
{
let num = s[i] - '0';
// If true, update ans to n - 1
if (num % 4 === 0)
{
ans = n - 1;
}
}
}
// Print the result
document.write(ans);
}
// Driver Code
let str = "12367";
minimumDeletions(str);
// This code is contributed by Manoj.
</script>
Producción:
1
Complejidad de Tiempo: O((log 10 N) 2 )
Espacio Auxiliar: O (1)
Publicación traducida automáticamente
Artículo escrito por rohitmanathiya y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA