Conteo de diferentes números divisibles por 3 que se pueden obtener cambiando como máximo un dígito

Dada una string str que representa un número que tiene N dígitos, la tarea es calcular el número de formas de hacer que el número dado sea divisible por 3 cambiando como máximo un dígito del número.

Ejemplos:

Entrada: str[] = “23”
Salida: 7
Explicación: A continuación se muestran los números que se pueden hacer a partir de la string que son divisibles por 3 – 03, 21, 24, 27, 33, 63, 93
1.Cambie 2 a 0 (0+3)=3 divisible por 3
2. Cambia 3 a 1 (2+1)=3 divisible por 3
3 cambia 3 a 4 (2+4)=6 divisible por 3
4 cambia 2 a 3 la suma es 6 divisible por 3
Del mismo modo, hay un total de 7 formas de hacer que el número dado sea divisible por 3

Entrada: str[] = “235”
Salida: 9

Planteamiento: La idea es muy simple para resolver este problema. Calcule la suma de los dígitos de un número dado y luego, para cada índice, elimine ese dígito y pruebe todos los dígitos posibles del 0 al 9 y vea si la suma es divisible por 3 o no. Siga los pasos a continuación para resolver el problema:

• Inicialice la variable sum como 0 para almacenar la suma de los dígitos del número.
• Iterar sobre un rango [0, N] usando la variable i y realizar los siguientes pasos:
  • Agregue el valor del dígito en el i-ésimo índice en la suma variable.
• Inicialice la variable count como 0 para almacenar la respuesta.
• Si el número en sí es divisible por 3, incremente la cuenta en uno.
• Iterar sobre un rango [0, N] usando la variable i y realizar los siguientes pasos:
  • Inicialice la variable resting_sum como sum-(number.charAt(i)-48).
  • Iterar sobre un rango [0, 9] usando la variable j y realizar los siguientes pasos:
    • Sume el valor de j a la variable suma_restante y si la suma_restante es divisible por 3 y j no es igual al dígito en el índice i-ésimo , entonces sume el valor de contar por 1.
• Después de realizar los pasos anteriores, imprima el valor de conteo como respuesta.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
  
// Function to count the number of
// possible numbers divisible by 3
void findCount(string number)
{
  
    // Calculate the sum
    int sum = 0;
    for (int i = 0; i < number.length(); ++i) {
        sum += number[i] - 48;
    }
  
    // Store the answer
    int count = 0;
  
    // Consider the edge case when
    // the number itself is divisible by 3
    // The count will be added by 1
    if (sum % 3 == 0)
        count++;
  
    // Iterate over the range
    for (int i = 0; i < number.length(); ++i) {
  
        // Decreasing the sum
        int remaining_sum = sum - (number[i] - 48);
  
        // Iterate over the range
        for (int j = 0; j <= 9; ++j) {
  
            // Checking if the new sum
            // is divisible by 3 or not
            if ((remaining_sum + j) % 3 == 0
                && j != number[i] - 48) {
  
                // If yes increment
                // the value of the count
                ++count;
            }
        }
    }
    cout << count;
}
  
// Driver Code
int main()
{
    // Given number
    string number = "235";
  
    findCount(number);
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.util.*;
  
class GFG {
  
    // Function to count the number of
    // possible numbers divisible by 3
    public static void findCount(String number)
    {
  
        // Calculate the sum
        int sum = 0;
        for (int i = 0; i < number.length(); ++i) {
            sum += number.charAt(i) - 48;
        }
  
        // Store the answer
        int count = 0;
        if (sum % 3 == 0)
            count++;
  
        // Iterate over the range
        for (int i = 0; i < number.length(); ++i) {
  
            // Decreasing the sum
            int remaining_sum
                = sum - (number.charAt(i) - 48);
  
            // Iterate over the range
            for (int j = 0; j <= 9; ++j) {
  
                // Checking if the new sum
                // is divisible by 3 or not
                if ((remaining_sum + j) % 3 == 0
                    && j != number.charAt(i) - 48) {
  
                    // If yes increment
                    // the value of the count
                    ++count;
                }
            }
        }
        System.out.println(count);
    }
  
    // Driver Code
    public static void main(String[] args)
    {
        // Given number
        String number = "235";
  
        findCount(number);
    }
}

# Python program for the above approach
  
# Function to count the number of
# possible numbers divisible by 3
  
  
def findCount(number):
  
    # Calculate the sum
    sum = 0
    for i in range(len(number)):
        sum += int(number[i]) - 48
  
    # Store the answer
    count = 0
    if(sum % 3 == 0):
      count += 1
  
    # Iterate over the range
    for i in range(len(number)):
  
        # Decreasing the sum
        remaining_sum = sum - (int(number[i]) - 48)
  
        # Iterate over the range
        for j in range(10):
  
            # Checking if the new sum
            # is divisible by 3 or not
            if ((remaining_sum + j) % 3 == 0 and j != int(number[i]) - 48):
  
                # If yes increment
                # the value of the count
                count += 1
  
    print(count)
  
# Driver Code
  
  
# Given number
number = "235"
findCount(number)

// C# program for the above approach
using System;
using System.Collections.Generic;
  
class GFG {
  
    // Function to count the number of
    // possible numbers divisible by 3
    static void findCount(string number)
    {
  
        // Calculate the sum
        int sum = 0;
        for (int i = 0; i < number.Length; ++i) {
            sum += (int)number[i] - 48;
        }
  
        // Store the answer
        int count = 0;
        if (sum % 3 == 0)
            count++;
  
        // Iterate over the range
        for (int i = 0; i < number.Length; ++i) {
  
            // Decreasing the sum
            int remaining_sum = sum - ((int)number[i] - 48);
  
            // Iterate over the range
            for (int j = 0; j <= 9; ++j) {
  
                // Checking if the new sum
                // is divisible by 3 or not
                if ((remaining_sum + j) % 3 == 0
                    && j != number[i] - 48) {
  
                    // If yes increment
                    // the value of the count
                    ++count;
                }
            }
        }
        Console.Write(count);
    }
  
    // Driver Code
    public static void Main()
    {
  
        // Given number
        string number = "235";
  
        findCount(number);
    }
}

<script>
// Javascript program for the above approach
  
// Function to count the number of
// possible numbers divisible by 3
function findCount(number) {
  // Calculate the sum
  let sum = 0;
  for (let i = 0; i < number.length; ++i) {
    sum += number[i] - 48;
  }
  
  // Store the answer
  let count = 0;
  if(sum % 3 == 0) count++;
  // Iterate over the range
  for (let i = 0; i < number.length; ++i) {
    // Decreasing the sum
    let remaining_sum = sum - (number[i] - 48);
  
    // Iterate over the range
    for (let j = 0; j <= 9; ++j) {
      // Checking if the new sum
      // is divisible by 3 or not
      if ((remaining_sum + j) % 3 == 0 && j != number[i] - 48) {
        // If yes increment
        // the value of the count
        ++count;
      }
    }
  }
  document.write(count);
}
  
// Driver Code
  
// Given number
let number = "235";
  
findCount(number);
  
// This code is contributed by gfgking
  
</script>

9

Complejidad temporal: O(N)
Espacio auxiliar: O(1)