K-ésimo número superior a N cuya suma de sus cifras es divisible por M

Dados los números enteros N , K y M , la tarea es encontrar el K -ésimo número mayor que N cuya suma de dígitos sea divisible por M.

Ejemplos:

Entrada: N = 6, K = 5, M = 5
Salida: 32
Explicación:
El número mayor que N = 6 con la suma de sus dígitos divisible por 5 son {14, 19, 23, 28, 32, …}. El número K , es decir, el quinto número es 32.

Entrada: N = 40, K = 4, M = 5 
Salida: 55
Explicación:
El número mayor que N = 40 con la suma de sus dígitos divisible por 5 son {41, 46, 50, 55, …}. El número K , es decir, el número 4 es 55 .

Enfoque ingenuo: el enfoque más simple es verificar cada número mayor que N y si la suma de sus dígitos es divisible por M , incrementar el contador en 1 . Siga revisando el número hasta que el contador sea igual a K

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

Enfoque Eficiente: La idea es usar Programación Dinámica y Búsqueda Binaria . Siga los pasos a continuación para resolver el problema:

  • Primero, cree una función recursiva memorizada para encontrar el número total de números enteros menores o iguales a S que tengan la suma de dígitos divisible por M como se muestra a continuación:

 Las transiciones dp serán:

dp(S, índice, suma, ajustada, M) = dp(índice+1, (suma+i)%M, ajustada, M) donde,

  • S tiene un límite dado para el cual se deben encontrar todos los números menores o iguales a S con la suma de dígitos divisible por M.
  • index es el índice actual para el que se debe colocar un dígito.
  • suma toma los valores de 0 a 4.
  • La condición base es, si el índice se vuelve mayor que la longitud de S y la suma es divisible por M, devuelve 1.
  • M es el divisor.

Si el dígito anterior ya se colocó de tal manera que se vuelve más pequeño que S, entonces 

  • apretado será igual a 0.
  • Voy a iterar de 0 a 9.

Si todos los dígitos anteriores coinciden con los dígitos correspondientes en S, entonces

  • apretado se convertirá en 1, lo que denota que el número aún no se vuelve más pequeño que S.
  • iteraré desde 0 hasta el dígito S [índice].
  • Ahora usando Binary Search , donde el límite inferior será N+1 y el límite superior será un número entero grande.
  • Inicialice una variable que quede para almacenar los números totales menores o iguales a N cuya suma de dígitos sea divisible por M .
  • Encuentra el punto medio del límite inferior y superior y luego encuentra los números menores o iguales al punto medio cuya suma de dígitos es divisible por M usando la función dp anterior. Que sea correcto .
  • Si izquierda + K es igual a derecha , actualice la respuesta como medio y establezca el límite superior como punto medio – 1 .
  • De lo contrario, si left + K es más pequeño que right, establezca el límite superior como midpoint-1 .
  • Si izquierda + K es mayor que derecha, establezca el límite inferior como punto medio+1 .
  • Repita los pasos anteriores, mientras que el límite inferior es menor o igual que el límite superior.

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;
 
// Initialize dp array
int dp[100000][100][2];
 
// Function to find the numbers <= S
// having digits sum divisible by M
int solve(string s, int index, int sum,
                    int tight, int z)
{
     
    // Base Case
    if (index >= s.size())
    {
        if (sum % z == 0)
            return 1;
             
        return 0;
    }
 
    // Visited state
    if (dp[index][sum][tight] != -1)
        return dp[index][sum][tight];
 
    // Store answer
    int ans = 0;
 
    // If number still does not
    // become smaller than S
    if (tight == 1)
    {
         
        // Find limit
        int l = s[index] - '0';
 
        // Iterate through all
        // the digits
        for(int i = 0; i <= l; i++)
        {
             
            // If current digit is limit
            if (i == l)
            {
                ans += solve(s, index + 1,
                                 (sum + i) % z, 1, z);
            }
 
            // Number becomes smaller than S
            else {
                ans += solve(s, index + 1,
                                 (sum + i) % z, 0, z);
            }
        }
    }
    else
    {
         
        // If number already becomes
        // smaller than S
        for(int i = 0; i <= 9; i++)
            ans += solve(s, index + 1,
                             (sum + i) % z, 0, z);
    }
 
    // Return and store the answer
    // for the current state
    return dp[index][sum][tight] = ans;
}
 
// Function to find the Kth number
// > N whose sum of the digits is
// divisible by M
int search(int n, int k, int z)
{
     
    // Initialize lower limit
    int low = n + 1;
 
    // Initialize upper limit
    int high = 1e9;
 
    // Mask dp states unvisited
    memset(dp, -1, sizeof(dp));
 
    // Numbers <= N except 0 with
    // digits sum divisible by M
    int left = solve(to_string(n),
                     0, 0, 1, z) - 1;
 
    // Initialize answer with -1
    int ans = -1;
    while (low <= high)
    {
         
        // Calculate mid
        int mid = low + (high - low) / 2;
 
        // Mark dp states unvisited
        memset(dp, -1, sizeof(dp));
 
        // Numbers < mid with digits
        // sum divisible by M
        int right = solve(to_string(mid),
                          0, 0, 1, z) - 1;
 
        // If the current mid is
        // satisfy the condition
        if (left + k == right)
        {
             
            // Might be the answer
            ans = mid;
 
            // Update upper limit
            high = mid - 1;
        }
        else if (left + k < right)
        {
             
            // Update upper limit
            high = mid - 1;
        }
        else
        {
             
            // Update lower limit
            low = mid + 1;
        }
    }
 
    // Return the answer
    return ans;
}
 
// Driver Code
int main()
{
     
    // Given N, K, and M
    int N = 40;
    int K = 4;
    int M = 2;
     
    // Function Call
    cout << search(N, K, M) << endl;
}
 
// This code is contributed by bolliranadheer

Java

// Java program for the above approach
 
import java.util.*;
public class Main {
 
    static int dp[][][];
 
    // Function to find the Kth number
    // > N whose sum of the digits is
    // divisible by M
    public static int search(
        int n, int k, int z)
    {
 
        // Initialize dp array
        dp = new int[100000 + 1][z][2];
 
        // Initialize lower limit
        int low = n + 1;
 
        // Initialize upper limit
        int high = Integer.MAX_VALUE / 2;
 
        // Mask dp states unvisited
        clear();
 
        // Numbers <= N except 0 with
        // digits sum divisible by M
        int left = solve(n + "", 0,
                         0, 1, z)
                   - 1;
 
        // Initialize answer with -1
        int ans = -1;
        while (low <= high) {
 
            // Calculate mid
            int mid = low + (high - low) / 2;
 
            // Mark dp states unvisited
            clear();
 
            // Numbers < mid with digits
            // sum divisible by M
            int right = solve(mid + "", 0,
                              0, 1, z)
                        - 1;
 
            // If the current mid is
            // satisfy the condition
            if (left + k == right) {
 
                // Might be the answer
                ans = mid;
 
                // Update upper limit
                high = mid - 1;
            }
            else if (left + k < right) {
 
                // Update upper limit
                high = mid - 1;
            }
            else {
 
                // Update lower limit
                low = mid + 1;
            }
        }
 
        // Return the answer
        return ans;
    }
 
    // Function to find the numbers <= S
    // having digits sum divisible by M
    public static int solve(
        String s, int index, int sum,
        int tight, int z)
    {
        // Base Case
        if (index >= s.length()) {
            if (sum % z == 0)
                return 1;
            return 0;
        }
 
        // Visited state
        if (dp[index][sum][tight] != -1)
            return dp[index][sum][tight];
 
        // Store answer
        int ans = 0;
 
        // If number still does not
        // become smaller than S
        if (tight == 1) {
 
            // Find limit
            int l = s.charAt(index) - '0';
 
            // Iterate through all
            // the digits
            for (int i = 0; i <= l; i++) {
 
                // If current digit is limit
                if (i == l) {
                    ans += solve(s, index + 1,
                                 (sum + i) % z,
                                 1, z);
                }
 
                // Number becomes smaller than S
                else {
                    ans += solve(s, index + 1,
                                 (sum + i) % z,
                                 0, z);
                }
            }
        }
        else {
 
            // If number already becomes
            // smaller than S
            for (int i = 0; i <= 9; i++)
                ans += solve(s, index + 1,
                             (sum + i) % z, 0,
                             z);
        }
 
        // Return and store the answer
        // for the current state
        return dp[index][sum][tight] = ans;
    }
 
    // Function to clear the states
    public static void clear()
    {
        for (int i[][] : dp) {
            for (int j[] : i)
                Arrays.fill(j, -1);
        }
    }
 
    // Driver Code
    public static void main(String args[])
    {
        // Given N, K, and M
        int N = 40;
        int K = 4;
        int M = 2;
 
        // Function Call
        System.out.println(search(N, K, M));
    }
}

Python3

# Python program for the
# above approach
 
# Initialize dp array
dp = [[[]]]
 
# Function to find the
# numbers <= S having
# digits sum divisible
# by M
def solve(s, index,
          sum,tight, z):
 
    # Base Case
    if (index >= len(s)):   
        if (sum % z == 0):
            return 1
 
        return 0
 
    # Visited state
    if (dp[index][sum][tight] != -1):
        return dp[index][sum][tight]
 
    # Store answer
    ans = 0
 
    # If number still does not
    # become smaller than S
    if(tight == 1):
 
        # Find limit
        l = int(ord(s[index]) -
                ord('0'))
 
        # Iterate through all
        # the digits
        for i in range(0, l + 1):
             
            # If current digit is
            # limit
            if (i == l):
             
                ans += solve(s, index + 1,
                            (sum + i) % z,
                             1, z)
             
            # Number becomes smaller
            # than S
            else:
                ans += solve(s, index + 1,
                            (sum + i) % z,
                             0, z)
 
    else:
     
        # If number already becomes
        # smaller than S
        for i in range(0,10):
         
            ans += solve(s, index + 1,
                        (sum + i) % z,
                         0, z)
     
    # Return and store the answer
    # for the current state
    dp[index][sum][tight] = ans
    return ans
 
# Function to find the Kth number
# > N whose sum of the digits is
# divisible by M
def search(n, k, z):
 
    global dp
    dp = [[[-1, -1] for j in range(z)]
                    for i in range(100001)]
 
    # Initialize lower limit
    low = n + 1
 
    # Initialize upper limit
    high = 1000000009
 
    # Numbers <= N except 0 with
    # digits sum divisible by M
    left = solve(str(n), 0,
                 0, 1, z) - 1
 
    # Initialize answer with -1
    ans = -1
    while (low <= high):
 
        # Calculate mid
        mid = low + (high -
                     low) // 2
 
        # Mark dp states unvisited
        dp = [[[-1, -1] for j in range(z)]
                        for i in range(100000)]
 
        # Numbers < mid with digits
        # sum divisible by M
        right = solve(str(mid), 0,
                      0, 1, z) - 1
 
        # If the current mid is
        # satisfy the condition
        if (left + k == right):
 
            # Might be the answer
            ans = mid
 
            # Update upper limit
            high = mid - 1
         
        elif (left + k < right):
         
            # Update upper limit
            high = mid - 1
         
        else:
 
            # Update lower limit
            low = mid + 1
 
    # Return the answer
    return ans
 
# Driver Code
if __name__ == "__main__":
     
    # Given N, K, and M
    N = 40
    K = 4
    M = 2
 
    # Function Call
    print(search(N, K, M))
 
# This code is contributed by Rutvik_56

C#

// C# program for the above approach
using System;
 
class GFG{
 
static int [,,]dp;
 
// Function to find the Kth number
// > N whose sum of the digits is
// divisible by M
public static int search(int n, int k,
                         int z)
{
     
    // Initialize dp array
    dp = new int[100000 + 1, z, 2];
 
    // Initialize lower limit
    int low = n + 1;
 
    // Initialize upper limit
    int high = int.MaxValue / 2;
 
    // Mask dp states unvisited
    Clear(z);
 
    // Numbers <= N except 0 with
    // digits sum divisible by M
    int left = solve(n + "", 0,
                     0, 1, z) - 1;
 
    // Initialize answer with -1
    int ans = -1;
    while (low <= high)
    {
         
        // Calculate mid
        int mid = low + (high - low) / 2;
         
        // Mark dp states unvisited
        Clear(z);
         
        // Numbers < mid with digits
        // sum divisible by M
        int right = solve(mid + "", 0,
                          0, 1, z) - 1;
 
        // If the current mid is
        // satisfy the condition
        if (left + k == right)
        {
             
            // Might be the answer
            ans = mid;
 
            // Update upper limit
            high = mid - 1;
        }
        else if (left + k < right)
        {
             
            // Update upper limit
            high = mid - 1;
        }
        else
        {
             
            // Update lower limit
            low = mid + 1;
        }
    }
     
    // Return the answer
    return ans;
}
 
// Function to find the numbers <= S
// having digits sum divisible by M
public static int solve(String s, int index,
                        int sum, int tight,
                        int z)
{
     
    // Base Case
    if (index >= s.Length)
    {
        if (sum % z == 0)
            return 1;
             
        return 0;
    }
 
    // Visited state
    if (dp[index, sum, tight] != -1)
        return dp[index, sum, tight];
 
    // Store answer
    int ans = 0;
 
    // If number still does not
    // become smaller than S
    if (tight == 1)
    {
         
        // Find limit
        int l = s[index] - '0';
 
        // Iterate through all
        // the digits
        for(int i = 0; i <= l; i++)
        {
             
            // If current digit is limit
            if (i == l)
            {
                ans += solve(s, index + 1,
                            (sum + i) % z,
                             1, z);
            }
             
            // Number becomes smaller than S
            else
            {
                ans += solve(s, index + 1,
                            (sum + i) % z,
                             0, z);
            }
        }
    }
    else
    {
         
        // If number already becomes
        // smaller than S
        for(int i = 0; i <= 9; i++)
            ans += solve(s, index + 1,
                        (sum + i) % z, 0,
                         z);
    }
     
    // Return and store the answer
    // for the current state
    return dp[index, sum, tight] = ans;
}
 
// Function to clear the states
public static void Clear(int z)
{
    for(int i = 0; i < 100001; i++)
    {
        for(int j = 0; j < z; j++)
        {
            for(int l = 0; l < 2; l++)
                dp[i, j, l] = -1;
        }
    }
}
 
// Driver Code
public static void Main(String []args)
{
     
    // Given N, K, and M
    int N = 40;
    int K = 4;
    int M = 2;
     
    // Function Call
    Console.WriteLine(search(N, K, M));
}
}
 
// This code is contributed by gauravrajput1

Javascript

<script>
// Javascript program for the above approach
 
let dp;
 
// Function to find the Kth number
    // > N whose sum of the digits is
    // divisible by M
function search(n,k,z)
{
    // Initialize dp array
        dp = new Array(100000 + 1);
        for(let i=0;i<100000+1;i++)
        {
            dp[i]=new Array(z);
            for(let j=0;j<z;j++)
            {
                dp[i][j]=new Array(2);
            }
        }
  
        // Initialize lower limit
        let low = n + 1;
  
        // Initialize upper limit
        let high = Math.floor(Number.MAX_VALUE / 2);
  
        // Mask dp states unvisited
        clear();
  
        // Numbers <= N except 0 with
        // digits sum divisible by M
        let left = solve(n + "", 0,
                         0, 1, z)
                   - 1;
  
        // Initialize answer with -1
        let ans = -1;
        while (low <= high) {
  
            // Calculate mid
            let mid = low + Math.floor((high - low) / 2);
  
            // Mark dp states unvisited
            clear();
  
            // Numbers < mid with digits
            // sum divisible by M
            let right = solve(mid + "", 0,
                              0, 1, z)
                        - 1;
  
            // If the current mid is
            // satisfy the condition
            if (left + k == right) {
  
                // Might be the answer
                ans = mid;
  
                // Update upper limit
                high = mid - 1;
            }
            else if (left + k < right) {
  
                // Update upper limit
                high = mid - 1;
            }
            else {
  
                // Update lower limit
                low = mid + 1;
            }
        }
  
        // Return the answer
        return ans;
}
 
// Function to find the numbers <= S
    // having digits sum divisible by M
function solve(s,index,sum,tight,z)
{
    // Base Case
        if (index >= s.length) {
            if (sum % z == 0)
                return 1;
            return 0;
        }
  
        // Visited state
        if (dp[index][sum][tight] != -1)
            return dp[index][sum][tight];
  
        // Store answer
        let ans = 0;
  
        // If number still does not
        // become smaller than S
        if (tight == 1) {
  
            // Find limit
            let l = s[index].charCodeAt(0) - '0'.charCodeAt(0);
  
            // Iterate through all
            // the digits
            for (let i = 0; i <= l; i++) {
  
                // If current digit is limit
                if (i == l) {
                    ans += solve(s, index + 1,
                                 (sum + i) % z,
                                 1, z);
                }
  
                // Number becomes smaller than S
                else {
                    ans += solve(s, index + 1,
                                 (sum + i) % z,
                                 0, z);
                }
            }
        }
        else {
  
            // If number already becomes
            // smaller than S
            for (let i = 0; i <= 9; i++)
                ans += solve(s, index + 1,
                             (sum + i) % z, 0,
                             z);
        }
  
        // Return and store the answer
        // for the current state
        return dp[index][sum][tight] = ans;
}
 
// Function to clear the states
function clear()
{
    for(let i=0;i<dp.length;i++)
    {
        for(let j=0;j<dp[i].length;j++)
        {
            for(let k=0;k<dp[i][j].length;k++)
            {
                dp[i][j][k]=-1;
            }
        }
    }
}
 
// Driver Code
// Given N, K, and M
let N = 40;
let K = 4;
let M = 2;
 
// Function Call
document.write(search(N, K, M)+"<br>");
 
// This code is contributed by patel2127
</script>
Producción

48

Complejidad de tiempo: O(log(INT_MAX))
Espacio auxiliar: O(K * M * log(INT_MAX))

Publicación traducida automáticamente

Artículo escrito por hemanthswarna1506 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 *