Número de dígitos a eliminar para hacer un número divisible por 3

Dado un número muy grande (1 <= num <= 10^1000), imprima el número de dígitos que deben eliminarse para que el número sea exactamente divisible por 3. Si no es posible, imprima -1.

Ejemplos: 

Input: num = "1234"
Output: 1
Explanation: we need to remove one 
digit that is 1 or 4, to make the
number divisible by 3.on 

Input: num = "11"
Output: -1
Explanation: It is not possible to 
remove any digits and make it divisible
by 3. 

La idea se basa en el hecho de que un número es múltiplo de 3 si y solo si la suma de sus dígitos es múltiplo de 3 (ver esto para más detalles).
Una observación importante utilizada aquí es que la respuesta es como máximo 2 si existe una respuesta. Así que aquí están las únicas opciones para la función: 

1. La suma de dígitos ya es igual a 0 módulo 3. Por lo tanto, no tenemos que borrar ningún dígito.
2. Existe tal dígito que es igual a suma módulo 3. Entonces solo tenemos que borrar un solo dígito
3. Todos los dígitos no son divisibles por 3 ni iguales a la suma módulo 3. Entonces, dos de esos dígitos sumarán el número, que es igual a la suma módulo 3, (2+2) mod 3=1, (1+1) mod 3= 2

// CPP program to find the minimum number of
// digits to be removed to make a large number
// divisible by 3.
#include <bits/stdc++.h>
using namespace std;
 
// function to count the no of removal of digits
// to make a very large number divisible by 3
int divisible(string num)
{
    int n = num.length();
 
    // add up all the digits of num
    int sum = accumulate(begin(num),
                         end(num), 0) - '0' * 1;
 
    // if num is already is divisible by 3
    // then no digits are to be removed
    if (sum % 3 == 0)
        return 0;
 
    // if there is single digit, then it is
    // not possible to remove one digit.
    if (n == 1)
        return -1;
 
    // traverse through the number and find out
    // if any number on removal makes the sum
    // divisible by 3
    for (int i = 0; i < n; i++)
        if (sum % 3 == (num[i] - '0') % 3)
            return 1;
 
    // if there are two numbers then it is
    // not possible to remove two digits.
    if (n == 2)
        return -1;
 
    // Otherwise we can always make a number
    // multiple of 2 by removing 2 digits.
    return 2;
}
 
// Driver Code
int main()
{
    string num = "1234";
    cout << divisible(num);
    return 0;
}

// Java program to find the
// minimum number of digits
// to be removed to make a
// large number divisible by 3.
import java.io.*;
 
// function to count the no
// of removal of digits
// to make a very large
// number divisible by 3
class GFG {
    static int divisible(String num)
    {
        int n = num.length();
 
        // add up all the
        // digits of num
        int sum = 0;
        for (int i = 0; i < n; i++)
            sum += (int)(num.charAt(i));
 
        // if num is already is
        // divisible by 3 then
        // no digits are to be
        // removed
        if (sum % 3 == 0)
            return 0;
 
        // if there is single digit,
        // then it is not possible
        // to remove one digit.
        if (n == 1)
            return -1;
 
        // traverse through the number
        // and find out if any number
        // on removal makes the sum
        // divisible by 3
        for (int i = 0; i < n; i++)
            if (sum % 3 == (num.charAt(i) - '0') % 3)
                return 1;
 
        // if there are two numbers
        // then it is not possible
        // to remove two digits.
        if (n == 2)
            return -1;
 
        // Otherwise we can always
        // make a number multiple
        // of 2 by removing 2 digits.
        return 2;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        String num = "1234";
        System.out.println(divisible(num));
    }
}
 
// This code is contributed by Raj

# Python3 program to find the
# minimum number of digits to
# be removed to make a large
# number divisible by 3.
 
# function to count the
# no of removal of digits
# to make a very large
# number divisible by 3
 
 
def divisible(num):
    n = len(num)
 
    # add up all the digits of num
    sum_ = 0
    for i in range(n):
        sum_ += int(num[i])
 
    # if num is already is
    # divisible by 3 then no
    # digits are to be removed
    if (sum_ % 3 == 0):
        return 0
 
    # if there is single digit,
    # then it is not possible
    # to remove one digit.
    if (n == 1):
        return -1
 
    # traverse through the number
    # and find out if any number
    # on removal makes the sum
    # divisible by 3
    for i in range(n):
        if (sum_ % 3 == int(num[i]) % 3):
            return 1
 
    # if there are two numbers
    # then it is not possible
    # to remove two digits.
    if (n == 2):
        return -1
 
    # Otherwise we can always
    # make a number multiple of
    # 2 by removing 2 digits.
    return 2
 
 
# Driver Code
if __name__ == '__main__':
    num = "1234"
    print(divisible(num))
 
# This code is contributed by mits

// C# program to find the
// minimum number of digits
// to be removed to make a
// large number divisible by 3.
using System;
 
// function to count the no
// of removal of digits
// to make a very large
// number divisible by 3
class GFG {
    static int divisible(String num)
    {
        int n = num.Length;
 
        // add up all the
        // digits of num
        int sum = 0;
        for (int i = 0; i < n; i++)
            sum += (int)(num[i]);
 
        // if num is already is
        // divisible by 3 then
        // no digits are to be
        // removed
        if (sum % 3 == 0)
            return 0;
 
        // if there is single digit,
        // then it is not possible
        // to remove one digit.
        if (n == 1)
            return -1;
 
        // traverse through the number
        // and find out if any number
        // on removal makes the sum
        // divisible by 3
        for (int i = 0; i < n; i++)
            if (sum % 3 == (num[i] - '0') % 3)
                return 1;
 
        // if there are two numbers
        // then it is not possible
        // to remove two digits.
        if (n == 2)
            return -1;
 
        // Otherwise we can always
        // make a number multiple
        // of 2 by removing 2 digits.
        return 2;
    }
 
    // Driver Code
    public static void Main()
    {
        string num = "1234";
        Console.WriteLine(divisible(num));
    }
}
 
// This code is contributed by mits

<?php
// PHP program to find the
// minimum number of digits to
// be removed to make a large
// number divisible by 3.
 
// function to count the
// no of removal of digits
// to make a very large
// number divisible by 3
 
function divisible($num)
{
    $n = strlen($num);
 
    // add up all the digits of num
    $sum = ($num); ($num); 0 - '0';
 
    // if num is already is
    // divisible by 3 then no
    // digits are to be removed
    if ($sum % 3 == 0)
        return 0;
 
    // if there is single digit,
    // then it is not possible
    // to remove one digit.
    if ($n == 1)
        return -1;
 
    // traverse through the number
    // and find out if any number
    // on removal makes the sum
    // divisible by 3
    for ($i = 0; $i < $n; $i++)
        if ($sum % 3 == ($num[$i] - '0') % 3)
            return 1;        
 
    // if there are two numbers
    // then it is not possible
    // to remove two digits.
    if ($n == 2)
        return -1;
 
    // Otherwise we can always
    // make a number multiple of
    // 2 by removing 2 digits.
    return 2;
}
 
// Driver Code
$num = "1234";
echo divisible($num);
 
// This code is contributed by ajit
?>

<script>
 
// JavaScript program to find the minimum number of
// digits to be removed to make a large number
// divisible by 3.
 
// function to count the no of removal of digits
// to make a very large number divisible by 3
function divisible(num)
{
    let n = num.length;
 
    // add up all the digits of num
    let sum = 0;
    for (let i = 0; i < n; i++)
            sum += (num.charAt(i));
 
    // if num is already is divisible by 3
    // then no digits are to be removed
    if (sum % 3 == 0)
        return 0;
 
    // if there is single digit, then it is
    // not possible to remove one digit.
    if (n == 1)
        return -1;
 
    // traverse through the number and find out
    // if any number on removal makes the sum
    // divisible by 3
    for (let i = 0; i < n; i++)
        if (sum % 3 == (num.charAt(i) - '0') % 3)
            return 1;
 
    // if there are two numbers then it is
    // not possible to remove two digits.
    if (n == 2)
        return -1;
 
    // Otherwise we can always make a number
    // multiple of 2 by removing 2 digits.
    return 2;
}
 
// Driver Code
 
    let num = "1234";
    document.write(divisible(num));
 
 
// This code is contributed by Surbhi Tyagi.
 
</script>

Producción : 

1

Complejidad de tiempo : O (N), ya que estamos usando un bucle para atravesar N veces.

Espacio auxiliar : O(1), ya que no estamos utilizando ningún espacio adicional.

Este artículo es una contribución de Striver . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.