Dada una string numérica S , la tarea es encontrar el número mínimo y máximo de dígitos que deben eliminarse de S para que sea divisible por 3 . Si es imposible hacerlo, imprima “-1” .
Ejemplos:
Input: S = "12345" Output: Minimum: 0 Maximum: 4 Explanation: The given number 12345 is divisible by 3. Therefore, the minimum digits required to be removed to make it divisible by 3 is 0. After removing digits 1, 2, 4 and 5, only 3 remains, which is divisible by 3. Therefore, the maximum number of digits required to be removed is 4.
Input: S = "44" Output: Minimum: -1 Maximum: -1
Planteamiento: El problema se puede resolver basándose en la observación de que para que cualquier número sea divisible por 3 , la suma de los dígitos también debe ser divisible por 3. Siga los pasos a continuación para resolver este problema:
- Inserte cada dígito de la string dada en una array, digamos arr[] , como (S[i] – ‘0’) % 3 .
- Encuentra el conteo de 0 s, 1 s y 2 s en la array arr[] .
- Luego, calcule la suma de dígitos, es decir (arr[0] % 3) + (arr[1] % 3) + (arr[2] % 3)…. . Actualizar suma = suma % 3 .
- Dependiendo del valor de sum , se dan los siguientes tres casos:
- Si sum = 0: el número mínimo de dígitos que se deben eliminar es 0 .
- Si suma = 1: Se deben eliminar aquellos dígitos cuya suma de resto 1 al dividir por 3 . Por lo tanto, se deben considerar las siguientes situaciones:
- Si el conteo de 1 s es mayor o igual a 1 , entonces el número mínimo de dígitos que se deben eliminar es 1.
- Si el conteo de 2 s es mayor o igual a 2 , entonces el número mínimo de dígitos que se deben eliminar será 2 [Ya que (2 + 2) % 3 = 1] .
- Si suma = 2: Se deben eliminar aquellos dígitos cuya suma dé resto 2 al dividir por 3 . Por tanto, se dan las siguientes situaciones:
- Si el conteo de 2 s es mayor o igual a 1 , entonces el número mínimo de dígitos que se deben eliminar será 1 .
- De lo contrario, si el conteo de 1 s es mayor o igual a 2 , entonces el número mínimo de dígitos a eliminar será 2 [(1 + 1) % 3 = 2] .
- Para encontrar el número máximo de dígitos a eliminar, se deben considerar los siguientes tres casos:
- Si el conteo de 0 s es mayor o igual a 1 , entonces el número máximo de dígitos que se deben eliminar será (número de dígitos – 1) .
- Si tanto el conteo de 1 s como el de 2 s son mayores o iguales a 1 , entonces el número máximo de dígitos que se deben eliminar será (número de dígitos – 2) [(1+2) % 3 = 0] .
- Si el conteo de 1 s o 2 s es mayor o igual a 3 , entonces el máximo de dígitos que se deben eliminar será (número de dígitos – 3) [(1+1+1) % 3 = 0, (2+ 2+2) % 3 = 0] .
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 maximum and
// minimum number of digits to be
// removed to make str divisible by 3
void minMaxDigits(string str, int N)
{
// Convert the string into
// array of digits
int arr[N];
for (int i = 0; i < N; i++)
arr[i] = (str[i] - '0') % 3;
// Count of 0s, 1s, and 2s
int zero = 0, one = 0, two = 0;
// Traverse the array
for (int i = 0; i < N; i++) {
if (arr[i] == 0)
zero++;
if (arr[i] == 1)
one++;
if (arr[i] == 2)
two++;
}
// Find the sum of digits % 3
int sum = 0;
for (int i = 0; i < N; i++) {
sum = (sum + arr[i]) % 3;
}
// Cases to find minimum number
// of digits to be removed
if (sum == 0) {
cout << 0 << ' ';
}
if (sum == 1) {
if (one && N > 1)
cout << 1 << ' ';
else if (two > 1 && N > 2)
cout << 2 << ' ';
else
cout << -1 << ' ';
}
if (sum == 2) {
if (two && N > 1)
cout << 1 << ' ';
else if (one > 1 && N > 2)
cout << 2 << ' ';
else
cout << -1 << ' ';
}
// Cases to find maximum number
// of digits to be removed
if (zero > 0)
cout << N - 1 << ' ';
else if (one > 0 && two > 0)
cout << N - 2 << ' ';
else if (one > 2 || two > 2)
cout << N - 3 << ' ';
else
cout << -1 << ' ';
}
// Driver Code
int main()
{
string str = "12345";
int N = str.length();
// Function Call
minMaxDigits(str, N);
return 0;
}
Java
// Java program for the above approach
class GFG{
// Function to find the maximum and
// minimum number of digits to be
// removed to make str divisible by 3
static void minMaxDigits(String str, int N)
{
// Convert the string into
// array of digits
int arr[] = new int[N];
for(int i = 0; i < N; i++)
arr[i] = (str.charAt(i) - '0') % 3;
// Count of 0s, 1s, and 2s
int zero = 0, one = 0, two = 0;
// Traverse the array
for(int i = 0; i < N; i++)
{
if (arr[i] == 0)
zero++;
if (arr[i] == 1)
one++;
if (arr[i] == 2)
two++;
}
// Find the sum of digits % 3
int sum = 0;
for(int i = 0; i < N; i++)
{
sum = (sum + arr[i]) % 3;
}
// Cases to find minimum number
// of digits to be removed
if (sum == 0)
{
System.out.print(0 + " ");
}
if (sum == 1)
{
if ((one != 0) && (N > 1))
System.out.print(1 + " ");
else if (two > 1 && N > 2)
System.out.print(2 + " ");
else
System.out.print(-1 + " ");
}
if (sum == 2)
{
if (two != 0 && N > 1)
System.out.print(1 + " ");
else if (one > 1 && N > 2)
System.out.print(2 + " ");
else
System.out.print(-1 + " ");
}
// Cases to find maximum number
// of digits to be removed
if (zero > 0)
System.out.print(N - 1 + " ");
else if (one > 0 && two > 0)
System.out.print(N - 2 + " ");
else if (one > 2 || two > 2)
System.out.print(N - 3 + " ");
else
System.out.print(-1 + " ");
}
// Driver code
public static void main(String[] args)
{
String str = "12345";
int N = str.length();
// Function Call
minMaxDigits(str, N);
}
}
// This code is contributed by sanjoy_62
Python3
# Python3 program for the above approach
# Function to find the maximum and
# minimum number of digits to be
# removed to make str divisible by 3
def minMaxDigits(str, N):
# Convert the string into
# array of digits
arr = [0]* N
for i in range(N):
arr[i] = (ord(str[i]) -
ord('0')) % 3
# Count of 0s, 1s, and 2s
zero = 0
one = 0
two = 0
# Traverse the array
for i in range(N):
if (arr[i] == 0):
zero += 1
if (arr[i] == 1):
one += 1
if (arr[i] == 2):
two += 1
# Find the sum of digits % 3
sum = 0
for i in range(N):
sum = (sum + arr[i]) % 3
# Cases to find minimum number
# of digits to be removed
if (sum == 0):
print("0", end = " ")
if (sum == 1):
if (one and N > 1):
print("1", end = " ")
elif (two > 1 and N > 2):
print("2", end = " ")
else:
print("-1", end = " ")
if (sum == 2):
if (two and N > 1):
print("1", end = " ")
elif (one > 1 and N > 2):
print("2", end = " ")
else:
print("-1", end = " ")
# Cases to find maximum number
# of digits to be removed
if (zero > 0):
print(N - 1, end = " ")
elif (one > 0 and two > 0):
print(N - 2, end = " ")
elif (one > 2 or two > 2):
print(N - 3, end = " ")
else :
print("-1", end = " ")
# Driver Code
str = "12345"
N = len(str)
# Function Call
minMaxDigits(str, N)
# This code is contributed by susmitakundugoaldanga
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the maximum and
// minimum number of digits to be
// removed to make str divisible by 3
static void minMaxDigits(string str, int N)
{
// Convert the string into
// array of digits
int[] arr = new int[N];
for(int i = 0; i < N; i++)
arr[i] = (str[i] - '0') % 3;
// Count of 0s, 1s, and 2s
int zero = 0, one = 0, two = 0;
// Traverse the array
for(int i = 0; i < N; i++)
{
if (arr[i] == 0)
zero++;
if (arr[i] == 1)
one++;
if (arr[i] == 2)
two++;
}
// Find the sum of digits % 3
int sum = 0;
for(int i = 0; i < N; i++)
{
sum = (sum + arr[i]) % 3;
}
// Cases to find minimum number
// of digits to be removed
if (sum == 0)
{
Console.Write(0 + " ");
}
if (sum == 1)
{
if ((one != 0) && (N > 1))
Console.Write(1 + " ");
else if (two > 1 && N > 2)
Console.Write(2 + " ");
else
Console.Write(-1 + " ");
}
if (sum == 2)
{
if (two != 0 && N > 1)
Console.Write(1 + " ");
else if (one > 1 && N > 2)
Console.Write(2 + " ");
else
Console.Write(-1 + " ");
}
// Cases to find maximum number
// of digits to be removed
if (zero > 0)
Console.Write(N - 1 + " ");
else if (one > 0 && two > 0)
Console.Write(N - 2 + " ");
else if (one > 2 || two > 2)
Console.Write(N - 3 + " ");
else
Console.Write(-1 + " ");
}
// Driver code
public static void Main()
{
string str = "12345";
int N = str.Length;
// Function Call
minMaxDigits(str, N);
}
}
// This code is contributed by code_hunt
Javascript
<script>
// Javascript program for the above approach
// Function to find the maximum and
// minimum number of digits to be
// removed to make str divisible by 3
function minMaxDigits(str, N)
{
// Convert the string into
// array of digits
let arr = [];
for(let i = 0; i < N; i++)
arr[i] = (str[i] - '0') % 3;
// Count of 0s, 1s, and 2s
let zero = 0, one = 0, two = 0;
// Traverse the array
for(let i = 0; i < N; i++)
{
if (arr[i] == 0)
zero++;
if (arr[i] == 1)
one++;
if (arr[i] == 2)
two++;
}
// Find the sum of digits % 3
let sum = 0;
for(let i = 0; i < N; i++)
{
sum = (sum + arr[i]) % 3;
}
// Cases to find minimum number
// of digits to be removed
if (sum == 0)
{
document.write(0 + " ");
}
if (sum == 1)
{
if ((one != 0) && (N > 1))
document.write(1 + " ");
else if (two > 1 && N > 2)
document.write(2 + " ");
else
document.write(-1 + " ");
}
if (sum == 2)
{
if (two != 0 && N > 1)
document.write(1 + " ");
else if (one > 1 && N > 2)
document.write(2 + " ");
else
document.write(-1 + " ");
}
// Cases to find maximum number
// of digits to be removed
if (zero > 0)
document.write(N - 1 + " ");
else if (one > 0 && two > 0)
document.write(N - 2 + " ");
else if (one > 2 || two > 2)
document.write(N - 3 + " ");
else
document.write(-1 + " ");
}
// Driver code
let str = "12345";
let N = str.length;
// Function Call
minMaxDigits(str, N);
// This code is contributed by avijitmondal1998
</script>
Producción:
0 4
Complejidad de tiempo: O (log 10 N)
Espacio Auxiliar: O(log 10 N)
Publicación traducida automáticamente
Artículo escrito por PratikLath y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA