Recuento de números de N dígitos que tienen la suma de dígitos pares e impares divisibles por números dados

Dados los números enteros A, B y N , la tarea es encontrar el número total de números de N dígitos cuya suma de dígitos en posiciones pares e impares sea divisible por A y B respectivamente.

Ejemplos:

Entrada: N = 2, A = 2, B = 5
Salida: 5
Explicación:
Los únicos números de 2 dígitos {50, 52, 54, 56, 58} con suma de dígitos impares igual a 5 y dígitos pares {0, 2, 4, 6, 8} divisible por 2.

Entrada: N = 2, A = 5, B = 3
Salida: 6
Explicación:
Los únicos números de dos dígitos {30, 35, 60, 65, 90, 95} tienen dígitos impares {3, 6 o 9}, que es divisible por 3 e incluso dígitos {0 o 5}, que es divisible por 5.

Enfoque ingenuo: el enfoque más simple para resolver este problema es iterar sobre todos los números de N dígitos posibles y, para cada número, verificar si la suma de los dígitos en las posiciones pares es divisible por A y la suma de los dígitos en las posiciones impares es divisible por B. O no. Si se determina que es cierto, aumente la cuenta

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

C++

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate and
// return the reverse of the number
long reverse(long num)
{
    long rev = 0;
    while (num > 0)
    {
        int r = (int)(num % 10);
        rev = rev * 10 + r;
        num /= 10;
    }
    return rev;
}
 
// Function to calculate the total
// count of N-digit numbers satisfying
// the necessary conditions
long count(int N, int A, int B)
{
     
    // Initialize two variables
    long l = (long)pow(10, N - 1),
         r = (long)pow(10, N) - 1;
 
    if (l == 1)
        l = 0;
 
    long ans = 0;
 
    for(long i = l; i <= r; i++)
    {
        int even_sum = 0, odd_sum = 0;
        long itr = 0, num = reverse(i);
 
        // Calculate the sum of odd
        // and even positions
        while (num > 0)
        {
            if (itr % 2 == 0)
                odd_sum += num % 10;
            else
                even_sum += num % 10;
                 
            num /= 10;
            itr++;
        }
         
        // Check for divisibility
        if (even_sum % A == 0 &&
             odd_sum % B == 0)
            ans++;
    }
 
    // Return the answer
    return ans;
}
 
// Driver Code
int main()
{
    int N = 2, A = 5, B = 3;
    cout << (count(N, A, B));
 
}
 
// This code is contributed by 29AjayKumar

Java

// Java Program to implement
// the above approach
class GFG {
 
    // Function to calculate and
    // return the reverse of the number
    public static long reverse(long num)
    {
        long rev = 0;
        while (num > 0) {
            int r = (int)(num % 10);
            rev = rev * 10 + r;
            num /= 10;
        }
        return rev;
    }
 
    // Function to calculate the total
    // count of N-digit numbers satisfying
    // the necessary conditions
    public static long count(int N, int A, int B)
    {
        // Initialize two variables
        long l = (long)Math.pow(10, N - 1),
             r = (long)Math.pow(10, N) - 1;
 
        if (l == 1)
            l = 0;
 
        long ans = 0;
 
        for (long i = l; i <= r; i++) {
            int even_sum = 0, odd_sum = 0;
            long itr = 0, num = reverse(i);
 
            // Calculate the sum of odd
            // and even positions
            while (num > 0) {
 
                if (itr % 2 == 0)
                    odd_sum += num % 10;
                else
                    even_sum += num % 10;
                num /= 10;
                itr++;
            }
            // Check for divisibility
            if (even_sum % A == 0
                && odd_sum % B == 0)
                ans++;
        }
 
        // Return the answer
        return ans;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int N = 2, A = 5, B = 3;
        System.out.println(count(N, A, B));
    }
}

Python3

# Python3 Program to implement
# the above approach
 
# Function to calculate and
# return the reverse of the number
def reverse(num):
     
    rev = 0;
    while (num > 0):
        r = int(num % 10);
        rev = rev * 10 + r;
        num = num // 10;
     
    return rev;
 
# Function to calculate the total
# count of N-digit numbers satisfying
# the necessary conditions
def count(N, A, B):
     
    # Initialize two variables
    l = int(pow(10, N - 1));
    r = int(pow(10, N) - 1);
    if (l == 1):
        l = 0;
 
    ans = 0;
 
    for i in range(l, r + 1):
        even_sum = 0;
        odd_sum = 0;
        itr = 0;
        num = reverse(i);
         
        # Calculate the sum of odd
        # and even positions
        while (num > 0):
 
            if (itr % 2 == 0):
                odd_sum += num % 10;
            else:
                even_sum += num % 10;
            num = num // 10;
            itr += 1;
         
        # Check for divisibility
        if (even_sum % A == 0 and
            odd_sum % B == 0):
            ans += 1;
 
    # Return the answer
    return ans;
 
# Driver Code
if __name__ == '__main__':
     
    N = 2;
    A = 5;
    B = 3;
    print(count(N, A, B));
 
# This code is contributed by gauravrajput1

C#

// C# program to implement
// the above approach
using System;
 
class GFG{
 
// Function to calculate and
// return the reverse of the number
public static long reverse(long num)
{
    long rev = 0;
    while (num > 0)
    {
        int r = (int)(num % 10);
        rev = rev * 10 + r;
        num /= 10;
    }
    return rev;
}
 
// Function to calculate the total
// count of N-digit numbers satisfying
// the necessary conditions
public static long count(int N, int A, int B)
{
     
    // Initialize two variables
    long l = (long)Math.Pow(10, N - 1),
         r = (long)Math.Pow(10, N) - 1;
 
    if (l == 1)
        l = 0;
 
    long ans = 0;
 
    for(long i = l; i <= r; i++)
    {
        int even_sum = 0, odd_sum = 0;
        long itr = 0, num = reverse(i);
 
        // Calculate the sum of odd
        // and even positions
        while (num > 0)
        {
            if (itr % 2 == 0)
                odd_sum += (int)num % 10;
            else
                even_sum += (int)num % 10;
                 
            num /= 10;
            itr++;
        }
         
        // Check for divisibility
        if (even_sum % A == 0 &&
             odd_sum % B == 0)
            ans++;
    }
 
    // Return the answer
    return ans;
}
 
// Driver Code
public static void Main(String[] args)
{
    int N = 2, A = 5, B = 3;
    Console.WriteLine(count(N, A, B));
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
// javascript Program to implement
// the above approach   
// Function to calculate and
    // return the reverse of the number
    function reverse(num) {
        var rev = 0;
        while (num > 0) {
            var r = parseInt( (num % 10));
            rev = rev * 10 + r;
            num = parseInt(num/10);
        }
        return rev;
    }
 
    // Function to calculate the total
    // count of N-digit numbers satisfying
    // the necessary conditions
    function count(N , A , B) {
        // Initialize two variables
        var l = Math.pow(10, N - 1), r = Math.pow(10, N) - 1;
 
        if (l == 1)
            l = 0;
 
        var ans = 0;
 
        for (i = l; i <= r; i++) {
            var even_sum = 0, odd_sum = 0;
            var itr = 0, num = reverse(i);
 
            // Calculate the sum of odd
            // and even positions
            while (num > 0) {
 
                if (itr % 2 == 0)
                    odd_sum += num % 10;
                else
                    even_sum += num % 10;
                num = parseInt(num/10);
                itr++;
            }
            // Check for divisibility
            if (even_sum % A == 0 && odd_sum % B == 0)
                ans++;
        }
 
        // Return the answer
        return ans;
    }
 
    // Driver Code
     
        var N = 2, A = 5, B = 3;
        document.write(count(N, A, B));
 
// This code contributed by aashish1995
</script>
Producción: 

6

 

Complejidad temporal: O((10 N – 10 N – 1 – 1) * N) 
Espacio auxiliar: O(N) 

Enfoque eficiente: para optimizar el enfoque anterior, utilice el concepto de programación dinámica .

Siga los pasos a continuación para resolver el problema:  

  • Dado que los dígitos en posiciones pares y los dígitos en posiciones impares no dependen entre sí, por lo tanto, el problema dado se puede dividir en dos subproblemas:
    • Para dígitos de posición par: Recuento total de secuencias de N/2 dígitos de 0 a 9 (se permiten repeticiones) de modo que la suma de los dígitos sea divisible por A , donde el primer dígito puede ser cero.
    • Para dígitos impares: Recuento total de secuencias de dígitos Ceil(N/2) de 0 a 9 (se permiten repeticiones) de modo que la suma de los dígitos sea divisible por B , donde el primer dígito no puede ser cero.
  • El resultado requerido es el producto de los dos anteriores.

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

C++

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate the total
// count of N-digit numbers such
// that the sum of digits at even
// positions and odd positions are
// divisible by A and B respectively
long count(int N, int A, int B)
{
    // For single digit numbers
    if (N == 1)
    {
        return 9 / B + 1;
    }
 
    // Largest possible number
    int max_sum = 9 * N;
 
    // Count of possible odd digits
    int odd_count = N / 2 + N % 2;
 
    // Count of possible even digits
    int even_count = N - odd_count;
 
    // Calculate total count of sequences of
    // length even_count with sum divisible
    // by A where first digit can be zero
    long dp[even_count][max_sum + 1] = {0};
    for (int i = 0; i <= 9; i++)
        dp[0][i % A]++;
 
    for (int i = 1; i < even_count; i++)
    {
        for (int j = 0; j <= 9; j++)
        {
            for (int k = 0; k <= max_sum; k++)
            {
                if (dp[i - 1][k] > 0)
                    dp[i][(j + k) % A] += dp[i - 1][k];
            }
        }
    }
 
    // Calculate total count of sequences of
    // length odd_count with sum divisible
    // by B where cannot be zero
    long dp1[odd_count][max_sum + 1] = {0};
    for (int i = 1; i <= 9; i++)
        dp1[0][i % B]++;
 
    for (int i = 1; i < odd_count; i++)
    {
        for (int j = 0; j <= 9; j++)
        {
            for (int k = 0; k <= max_sum; k++)
            {
                if (dp1[i - 1][k] > 0)
                    dp1[i][(j + k) % B] += dp1[i - 1][k];
            }
        }
    }
 
    // Return their product as answer
    return dp[even_count - 1][0] * dp1[odd_count - 1][0];
}
 
// Driver Code
int main()
{
    int N = 2, A = 2, B = 5;
    cout << count(N, A, B);
}
 
// This code is contributed by Rajput-Ji

Java

// Java Program to implement
// the above approach
class GFG {
 
    // Function to calculate the total
    // count of N-digit numbers such
    // that the sum of digits at even
    // positions and odd positions are
    // divisible by A and B respectively
    public static long count(int N, int A, int B)
    {
        // For single digit numbers
        if (N == 1) {
            return 9 / B + 1;
        }
 
        // Largest possible number
        int max_sum = 9 * N;
 
        // Count of possible odd digits
        int odd_count = N / 2 + N % 2;
 
        // Count of possible even digits
        int even_count = N - odd_count;
 
        // Calculate total count of sequences of
        // length even_count with sum divisible
        // by A where first digit can be zero
        long dp[][]
            = new long[even_count][max_sum + 1];
        for (int i = 0; i <= 9; i++)
            dp[0][i % A]++;
 
        for (int i = 1; i < even_count; i++) {
            for (int j = 0; j <= 9; j++) {
                for (int k = 0; k <= max_sum; k++) {
                    if (dp[i - 1][k] > 0)
                        dp[i][(j + k) % A]
                            += dp[i - 1][k];
                }
            }
        }
 
        // Calculate total count of sequences of
        // length odd_count with sum divisible
        // by B where cannot be zero
        long dp1[][]
            = new long[odd_count][max_sum + 1];
        for (int i = 1; i <= 9; i++)
            dp1[0][i % B]++;
 
        for (int i = 1; i < odd_count; i++) {
            for (int j = 0; j <= 9; j++) {
                for (int k = 0; k <= max_sum; k++) {
                    if (dp1[i - 1][k] > 0)
                        dp1[i][(j + k) % B]
                            += dp1[i - 1][k];
                }
            }
        }
 
        // Return their product as answer
        return dp[even_count - 1][0]
            * dp1[odd_count - 1][0];
    }
    // Driver Code
    public static void main(String[] args)
    {
        int N = 2, A = 2, B = 5;
        System.out.println(count(N, A, B));
    }
}

Python3

# Python 3 Program to implement
# the above approach
 
# Function to calculate the total
# count of N-digit numbers such
# that the sum of digits at even
# positions and odd positions are
# divisible by A and B respectively
def count(N, A, B):
 
    # For single digit numbers
    if (N == 1):
        return 9 // B + 1
   
    # Largest possible number
    max_sum = 9 * N
 
    # Count of possible odd digits
    odd_count = N // 2 + N % 2
 
    # Count of possible even digits
    even_count = N - odd_count
 
    # Calculate total count of
    # sequences of length even_count
    # with sum divisible by A where
    # first digit can be zero
    dp = [[0 for x in range (max_sum + 1)]
             for y in range (even_count)]
     
    for i in range(10):
        dp[0][i % A] += 1
 
    for i in range (1, even_count):
        for j in range (10):
            for k in range (max_sum + 1):
                if (dp[i - 1][k] > 0):
                    dp[i][(j + k) % A] += dp[i - 1][k]
 
    # Calculate total count of sequences of
    # length odd_count with sum divisible
    # by B where cannot be zero
    dp1 = [[0 for x in range (max_sum)]
              for y in range (odd_count)]
    for i in range (1, 10):
        dp1[0][i % B] += 1
 
    for i in range (1, odd_count): 
        for j in range (10):      
            for k in range (max_sum + 1):
                if (dp1[i - 1][k] > 0):
                    dp1[i][(j + k) % B] += dp1[i - 1][k]
            
    # Return their product as answer
    return dp[even_count - 1][0] * dp1[odd_count - 1][0]
 
# Driver Code
if __name__ == "__main__":
   
    N = 2
    A = 2
    B = 5
    print (count(N, A, B))
 
# This code is contributed by Chitranayal

C#

// C# program to implement
// the above approach
using System;
 
class GFG{
 
// Function to calculate the total
// count of N-digit numbers such
// that the sum of digits at even
// positions and odd positions are
// divisible by A and B respectively
public static long count(int N, int A, int B)
{
     
    // For single digit numbers
    if (N == 1)
    {
        return 9 / B + 1;
    }
 
    // Largest possible number
    int max_sum = 9 * N;
 
    // Count of possible odd digits
    int odd_count = N / 2 + N % 2;
 
    // Count of possible even digits
    int even_count = N - odd_count;
 
    // Calculate total count of sequences of
    // length even_count with sum divisible
    // by A where first digit can be zero
    long [,]dp = new long[even_count, max_sum + 1];
    for(int i = 0; i <= 9; i++)
        dp[0, i % A]++;
 
    for(int i = 1; i < even_count; i++)
    {
        for(int j = 0; j <= 9; j++)
        {
            for(int k = 0; k <= max_sum; k++)
            {
                if (dp[i - 1, k] > 0)
                    dp[i, (j + k) % A] += dp[i - 1, k];
            }
        }
    }
 
    // Calculate total count of sequences of
    // length odd_count with sum divisible
    // by B where cannot be zero
    long [,]dp1 = new long[odd_count, max_sum + 1];
    for(int i = 1; i <= 9; i++)
        dp1[0, i % B]++;
 
    for(int i = 1; i < odd_count; i++)
    {
        for(int j = 0; j <= 9; j++)
        {
            for(int k = 0; k <= max_sum; k++)
            {
                if (dp1[i - 1, k] > 0)
                    dp1[i, (j + k) % B] += dp1[i - 1, k];
            }
        }
    }
     
    // Return their product as answer
    return dp[even_count - 1, 0] *
           dp1[odd_count - 1, 0];
}
 
// Driver Code
public static void Main(String[] args)
{
    int N = 2, A = 2, B = 5;
     
    Console.WriteLine(count(N, A, B));
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
// JavaScript program for the above approach
 
    // Function to calculate the total
    // count of N-digit numbers such
    // that the sum of digits at even
    // positions and odd positions are
    // divisible by A and B respectively
    function count(N, A, B)
    {
        // For single digit numbers
        if (N == 1) {
            return 9 / B + 1;
        }
  
        // Largest possible number
        let max_sum = 9 * N;
  
        // Count of possible odd digits
        let odd_count = N / 2 + N % 2;
  
        // Count of possible even digits
        let even_count = N - odd_count;
  
        // Calculate total count of sequences of
        // length even_count with sum divisible
        // by A where first digit can be zero
        let dp
            = new Array(even_count);
            // Loop to create 2D array using 1D array
        for (var i = 0; i < dp.length; i++) {
            dp[i] = new Array(2);
        }
         
        for (var i = 0; i < even_count; i++) {
            for (var j = 0; j < max_sum + 1; j++) {
            dp[i][j] = 0;
        }
        }
         
        for (let i = 0; i <= 9; i++)
            dp[0][i % A]++;
  
        for (let i = 1; i < even_count; i++) {
            for (let j = 0; j <= 9; j++) {
                for (let k = 0; k <= max_sum; k++) {
                    if (dp[i - 1][k] > 0)
                        dp[i][(j + k) % A]
                            += dp[i - 1][k];
                }
            }
        }
  
        // Calculate total count of sequences of
        // length odd_count with sum divisible
        // by B where cannot be zero
        let dp1
            = new Array(odd_count);
        // Loop to create 2D array using 1D array
        for (var i = 0; i < dp1.length; i++) {
            dp1[i] = new Array(2);
        }
         
        for (var i = 0; i < odd_count; i++) {
            for (var j = 0; j < max_sum + 1; j++) {
            dp1[i][j] = 0;
        }
        }
         
        for (let i = 1; i <= 9; i++)
            dp1[0][i % B]++;
  
        for (let i = 1; i < odd_count; i++) {
            for (let j = 0; j <= 9; j++) {
                for (let k = 0; k <= max_sum; k++) {
                    if (dp1[i - 1][k] > 0)
                        dp1[i][(j + k) % B]
                            += dp1[i - 1][k];
                }
            }
        }
  
        // Return their product as answer
        return dp[even_count - 1][0]
            * dp1[odd_count - 1][0];
    }
     
// Driver Code
 
    let N = 2, A = 2, B = 5;
    document.write(count(N, A, B));
         
</script>
Producción: 

5

 

Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N 2 )

Publicación traducida automáticamente

Artículo escrito por jrishabh99 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *