Posibles cortes de un número tal que las partes máximas sean divisibles por 3

Dado un gran número N (el número de dígitos en N puede ser hasta 10 ⁵ ). La tarea es encontrar los cortes requeridos de un número tal que las partes máximas sean divisibles por 3.
Ejemplos: 
 

Input: N = 1269
Output: 3
Cut the number as 12|6|9. So, 12, 6, 9 are the 
three numbers which are divisible by 3.

Input: N = 71
Output: 0
However, we make cuts there is no such number 
that is divisible by 3. 

Enfoque: 
Calculemos los valores de la array res[0…n], donde res[i] es la respuesta para el prefijo de la longitud i. Obviamente, res[0]:=0, ya que para la string vacía (el prefijo de longitud 0) la respuesta es 0.
Para i>0 se puede encontrar res[i] de la siguiente manera: 
 

• Veamos el último dígito del prefijo de longitud i. Tiene índice i-1. O no pertenece al segmento divisible por 3, o pertenece.
• Si no pertenece, significa que no se puede usar el último dígito, por lo que res[i]=res[i-1] . Si pertenece, busque el s[j..i-1] más corto que sea divisible por 3 e intente actualizar res[i] con el valor res[j]+1 .
• Un número es divisible por 3, si y solo si la suma de sus dígitos es divisible por 3. Entonces, la tarea es encontrar el sufijo más corto de s[0…i-1] con la suma de dígitos divisible por 3. Si tal el sufijo es s[j..i-1] entonces s[0..j-1] y s[0..i-1] tienen el mismo resto de la suma de dígitos módulo 3.
• Mantengamos remIndex[0..2]- una array de longitud 3, donde remIndex[r] es la longitud del prefijo procesado más largo con la suma de dígitos igual a r módulo 3. Utilice remIndex[r]= -1 si no hay tal prefijo. Es fácil ver que j=remIndex[r] donde r es la suma de los dígitos del i-ésimo prefijo módulo 3.
• Entonces, para encontrar el j<=i-1 máximo que la substring s[j..i-1] es divisible por 3, simplemente verifique que remIndex[r] no sea igual a -1 y use j=remIndex[r], donde r es la suma de los dígitos del i-ésimo prefijo módulo 3.
• Significa que para manejar el caso en el que el último dígito pertenece a un segmento divisible por 3, intente actualizar res[i] con el valor res[remIndex[r]]+1. En otras palabras, solo haz if (remIndex[r] != -1) => res[i] = max(res[i], res[remIndex[r]] + 1).

A continuación se muestra la implementación del enfoque anterior: 
 

// CPP program to find the maximum number of
// numbers divisible by 3 in a large number
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum number of
// numbers divisible by 3 in a large number
int MaximumNumbers(string s)
{
    // store size of the string
    int n = s.length();
 
    // Stores last index of a remainder
    vector<int> remIndex(3, -1);
 
    // last visited place of remainder
    // zero is at 0.
    remIndex[0] = 0;
 
    // To store result from 0 to i
    vector<int> res(n + 1);
 
    int r = 0;
    for (int i = 1; i <= n; i++) {
 
        // get the remainder
        r = (r + s[i-1] - '0') % 3;
 
        // Get maximum res[i] value
        res[i] = res[i-1];
        if (remIndex[r] != -1)
            res[i] = max(res[i], res[remIndex[r]] + 1);
 
        remIndex[r] = i+1;
    }
 
    return res[n];
}
 
// Driver Code
int main()
{
    string s = "12345";
    cout << MaximumNumbers(s);
    return 0;
}

// Java program to find the maximum number of
// numbers divisible by 3 in a large number
import java.util.*;
 
class GFG
{
     
// Function to find the maximum number of
// numbers divisible by 3 in a large number
static int MaximumNumbers(String s)
{
    // store size of the string
    int n = s.length();
 
    // Stores last index of a remainder
    int [] remIndex={-1, -1, -1};
 
    // last visited place of remainder
    // zero is at 0.
    remIndex[0] = 0;
 
    // To store result from 0 to i
    int[] res = new int[n + 1];
 
    int r = 0;
    for (int i = 1; i <= n; i++)
    {
 
        // get the remainder
        r = (r + s.charAt(i-1) - '0') % 3;
 
        // Get maximum res[i] value
        res[i] = res[i - 1];
        if (remIndex[r] != -1)
            res[i] = Math.max(res[i],
                    res[remIndex[r]] + 1);
 
        remIndex[r] = i + 1;
    }
 
    return res[n];
}
 
// Driver Code
public static void main (String[] args)
{
    String s = "12345";
    System.out.println(MaximumNumbers(s));
}
}
 
// This code is contributed by
// chandan_jnu

# Python3 program to find the maximum
# number of numbers divisible by 3 in
# a large number
import math as mt
 
# Function to find the maximum number
# of numbers divisible by 3 in a
# large number
def MaximumNumbers(string):
 
    # store size of the string
    n = len(string)
 
    # Stores last index of a remainder
    remIndex = [-1 for i in range(3)]
 
    # last visited place of remainder
    # zero is at 0.
    remIndex[0] = 0
 
    # To store result from 0 to i
    res = [-1 for i in range(n + 1)]
 
    r = 0
    for i in range(n + 1):
         
        # get the remainder
        r = (r + ord(string[i - 1]) -
                 ord('0')) % 3
 
        # Get maximum res[i] value
        res[i] = res[i - 1]
        if (remIndex[r] != -1):
            res[i] = max(res[i], res[remIndex[r]] + 1)
 
        remIndex[r] = i + 1
     
    return res[n]
 
# Driver Code
s= "12345"
print(MaximumNumbers(s))
 
# This code is contributed
# by Mohit kumar 29

// C# program to find the maximum number of
// numbers divisible by 3 in a large number .
using System;
 
class GFG
{
     
    // Function to find the maximum number of
    // numbers divisible by 3 in a large number
    static int MaximumNumbers(String s)
    {
        // store size of the string
        int n = s.Length;
 
        // Stores last index of a remainder
        int [] remIndex = {-1, -1, -1};
 
        // last visited place of remainder
        // zero is at 0.
        remIndex[0] = 0;
 
        // To store result from 0 to i
        int[] res = new int[n + 1];
 
        int r = 0;
        for (int i = 1; i <= n; i++)
        {
 
            // get the remainder
            r = (r + s[i-1] - '0') % 3;
 
            // Get maximum res[i] value
            res[i] = res[i - 1];
            if (remIndex[r] != -1)
                res[i] = Math.Max(res[i],
                        res[remIndex[r]] + 1);
 
            remIndex[r] = i + 1;
        }
        return res[n];
    }
 
    // Driver Code
    public static void Main (String[] args)
    {
        String s = "12345";
        Console.WriteLine(MaximumNumbers(s));
    }
}
 
// This code has been contributed by
// PrinciRaj1992

<?php
// PHP program to find the maximum number of
// numbers divisible by 3 in a large number
 
// Function to find the maximum number of
// numbers divisible by 3 in a large number
function MaximumNumbers($s)
{
    // store size of the string
    $n = strlen($s) ;
 
    // Stores last index of a remainder
    $remIndex = array_fill(0,3,-1) ;
 
    // last visited place of remainder
    // zero is at 0.
    $remIndex[0] = 0;
 
    // To store result from 0 to i
    $res = array() ;
 
    $r = 0;
    for ($i = 1; $i <= $n; $i++) {
 
        // get the remainder
        $r = ($r + $s[$i-1] - '0') % 3;
 
        // Get maximum res[i] value
        $res[$i] = $res[$i-1];
        if ($remIndex[$r] != -1)
            $res[$i] = max($res[$i], $res[$remIndex[$r]] + 1);
 
        $remIndex[$r] = $i+1;
    }
 
    return $res[$n];
}
 
    // Driver Code
    $s = "12345";
    print(MaximumNumbers($s))
 
    # This code is contributed by Ryuga
?>

<script>
// Javascript program to find the maximum number of
// numbers divisible by 3 in a large number
 
// Function to find the maximum number of
// numbers divisible by 3 in a large number
function MaximumNumbers(s)
{
    // store size of the string
    let n = s.length;
   
    // Stores last index of a remainder
    let remIndex=[-1, -1, -1];
   
    // last visited place of remainder
    // zero is at 0.
    remIndex[0] = 0;
   
    // To store result from 0 to i
    let res = new Array(n + 1);
      for(let i=0;i<res.length;i++)
    {
        res[i]=0;
    }
     
    let r = 0;
    for (let i = 1; i <= n; i++)
    {
   
        // get the remainder
        r = (r + s[i-1].charCodeAt(0) - '0'.charCodeAt(0)) % 3;
   
        // Get maximum res[i] value
        res[i] = res[i - 1];
        if (remIndex[r] != -1)
            res[i] = Math.max(res[i],
                    res[remIndex[r]] + 1);
   
        remIndex[r] = i + 1;
    } 
    return res[n];
}
 
// Driver Code
let s = "12345";
document.write(MaximumNumbers(s));
 
// This code is contributed by patel2127
</script>

3

Complejidad Temporal: O(n), ya que corre un bucle de 1 a n.

Espacio Auxiliar: O(n), ya que no se ha ocupado ningún espacio extra.

Otro enfoque: 
podemos usar running_sum, que mantiene la suma de todos los enteros sucesivos, donde ninguno de los enteros individuales es divisible por 3. Podemos pasar cada entero uno por uno y hacer lo siguiente: 
 

1. Si el número entero es divisible por 3 o la suma_ejecutable no es cero y es divisible por 3, incremente el contador y restablezca la suma_ejecutable.
2. En caso de que el número entero no sea divisible por 3, mantenga un registro de la suma de todos esos números enteros sucesivos.

// C++ program to find the maximum number
// of numbers divisible by 3 in large number
#include <iostream>
using namespace std;
 
int get_max_splits(string num_string)
{
    // This will contain the count of the splits
    int count = 0, current_num;
     
    // This will keep sum of all successive
    // integers, when they are indivisible by 3
    int running_sum = 0;
    for (int i = 0; i < num_string.length(); i++)
    {
        current_num = num_string[i] - '0';
        running_sum += current_num;
         
        // This is the condition of finding a split
        if (current_num % 3 == 0 ||
        (running_sum != 0 && running_sum % 3 == 0))
        {
            count += 1;
            running_sum = 0;
        }
    }
     
    return count;
}
 
// Driver code
int main()
{
    cout << get_max_splits("12345") << endl;
    return 0;
}
 
// This code is contributed by Rituraj Jain

// Java program to find the maximum number
// of numbers divisible by 3 in large number
class GFG
{
 
static int get_max_splits(String num_String)
{
    // This will contain the count of the splits
    int count = 0, current_num;
     
    // This will keep sum of all successive
    // integers, when they are indivisible by 3
    int running_sum = 0;
    for (int i = 0; i < num_String.length(); i++)
    {
        current_num = num_String.charAt(i) - '0';
        running_sum += current_num;
         
        // This is the condition of finding a split
        if (current_num % 3 == 0 ||
        (running_sum != 0 && running_sum % 3 == 0))
        {
            count += 1;
            running_sum = 0;
        }
    }
    return count;
}
 
// Driver code
public static void main(String[] args)
{
    System.out.print(get_max_splits("12345") +"\n");
}
}
 
// This code is contributed by 29AjayKumar

# Python3 program to find the maximum
# number of numbers divisible by 3 in
# a large number
def get_max_splits(num_string):
     
    # This will contain the count of the splits
    count = 0
     
     # This will keep sum of all successive
     # integers, when they are indivisible by 3
    running_sum = 0
    for i in range(len(num_string)):
        current_num = int(num_string[i])
        running_sum += current_num
         
        # This is the condition of finding a split
        if current_num % 3 == 0 or (running_sum != 0 and running_sum % 3 == 0):
            count += 1
            running_sum = 0
    return count
 
 
print get_max_splits("12345")
 
# This code is contributed by Amit Ranjan

// C# program to find the maximum number
// of numbers divisible by 3 in large number
using System;
 
class GFG
{
 
static int get_max_splits(String num_String)
{
    // This will contain the count of the splits
    int count = 0, current_num;
     
    // This will keep sum of all successive
    // integers, when they are indivisible by 3
    int running_sum = 0;
    for (int i = 0; i < num_String.Length; i++)
    {
        current_num = num_String[i] - '0';
        running_sum += current_num;
         
        // This is the condition of finding a split
        if (current_num % 3 == 0 ||
        (running_sum != 0 && running_sum % 3 == 0))
        {
            count += 1;
            running_sum = 0;
        }
    }
    return count;
}
 
// Driver code
public static void Main(String[] args)
{
    Console.Write(get_max_splits("12345") +"\n");
}
}
 
// This code is contributed by 29AjayKumar

<?php
// PHP program to find the maximum
// number of numbers divisible by 3 in
// a large number
function get_max_splits($num_string)
{
    // This will contain the count of
    // the splits
    $count = 0;
     
    // This will keep sum of all successive
    // integers, when they are indivisible by 3
    $running_sum = 0;
    for ($i = 0; $i < strlen($num_string); $i++)
    {
        $current_num = intval($num_string[$i]);
        $running_sum += $current_num;
         
        // This is the condition of finding a split
        if ($current_num % 3 == 0 or
           ($running_sum != 0 and $running_sum % 3 == 0))
            {
                $count += 1;
                $running_sum = 0;
            }
    }
         
    return $count;
}
 
// Driver Code
print(get_max_splits("12345"));
 
// This code is contributed by mits
?>

<script>
 
// JavaScript program to find the maximum number
// of numbers divisible by 3 in large number
 
function get_max_splits(num_String)
{
    // This will contain the count of the splits
    let count = 0, current_num;
      
    // This will keep sum of all successive
    // integers, when they are indivisible by 3
    let running_sum = 0;
    for (let i = 0; i < num_String.length; i++)
    {
        current_num = num_String[i].charCodeAt(0) -
        '0'.charCodeAt(0);
        running_sum += current_num;
          
        // This is the condition of finding a split
        if (current_num % 3 == 0 ||
        (running_sum != 0 && running_sum % 3 == 0))
        {
            count += 1;
            running_sum = 0;
        }
    }
    return count;
}
 
// Driver code
document.write(get_max_splits("12345") +"<br>");
 
 
// This code is contributed by unknown2108
 
</script>

3

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(1)