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