Dados dos enteros M y K , la tarea es encontrar el K-ésimo número más pequeño con suma de dígitos como M .
Ejemplos:
Entrada: M = 5, K = 3
Salida: 23
La secuencia de números que comienza en 1 con suma de dígitos como 5 es la siguiente:
5
14
23
32
41
Entonces, el tercer número más pequeño es 23
Entrada: M = 4, K = 1
Salida: 4
Enfoque: Necesitamos encontrar la secuencia de números comenzando desde 1 con la suma de dígitos como m.
- Escriba una función recursiva que aumente los números hasta que la suma de los dígitos del número sea igual a nuestra suma M requerida .
- Para eso, comience siempre desde 0 y verifique el número de un solo dígito que sumará M
- Tomemos un ejemplo para sum = 5, por lo que comenzaremos desde 0 y subiremos a 5 en un solo dígito, ya que 6 excede la suma requerida
- Ahora del 5 nos moveremos al número de dos dígitos 10 y subiremos al 14 porque la suma de los dígitos de 14 es 5 y 15 excederá la suma requerida y así sucesivamente, luego nos moveremos en 20 y esto continúa hacia arriba. a 50 porque después de 50 hasta 99 la suma de los dígitos de cada número será mayor que 5, así que lo omitiremos.
- Ahora nos moveremos en tres dígitos 100, 101, 102,… y de igual manera esta operación se irá realizando hasta que la suma de los dígitos del número sea igual a 15.
- Seguiremos insertando los elementos en un conjunto cuya suma de dígitos sea igual a M .
for(int i=0;i<=min(left, 9LL);i++){
dfs(num*10+i, left-i, ct+1);
}
Para encontrar el k-ésimo más pequeño, necesitamos ordenar la secuencia, por lo que será mejor si almacenamos los números en un conjunto en C++ , ya que los números en un conjunto están ordenados.
Tenga en cuenta que este enfoque no funcionará para valores de entrada más grandes.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2005;
set<int> ans;
// Recursively moving to add
// all the numbers upto a limit
// with sum of digits as m
void dfs(int num, int left, int ct)
{
// Max number of digits allowed in
// a number for this implementation
if (ct >= 15)
return;
if (left == 0)
ans.insert(num);
for (int i = 0; i <= min(left, 9LL); i++)
dfs(num * 10 + i, left - i, ct + 1);
}
// Function to return the kth number
// with sum of digits as m
int getKthNum(int m, int k)
{
dfs(0, m, 0);
int ct = 0;
for (auto it : ans) {
ct++;
// The kth smallest number is found
if (ct == k) {
return it;
}
}
return -1;
}
// Driver code
int main()
{
int m = 5, k = 3;
cout << getKthNum(m, k);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
static int N = 2005;
static Set<Integer> ans = new LinkedHashSet<Integer>();
// Recursively moving to add
// all the numbers upto a limit
// with sum of digits as m
static void dfs(int num, int left, int ct)
{
// Max number of digits allowed in
// a number for this implementation
if (ct >= 15)
return;
if (left == 0)
ans.add(num);
for (int i = 0; i <= Math.min(left, 9); i++)
dfs(num * 10 + i, left - i, ct + 1);
}
// Function to return the kth number
// with sum of digits as m
static int getKthNum(int m, int k)
{
dfs(0, m, 0);
int ct = 0;
for (int it : ans)
{
ct++;
// The kth smallest number is found
if (ct == k)
{
return it;
}
}
return -1;
}
// Driver code
public static void main(String[] args)
{
int m = 5, k = 3;
System.out.println(getKthNum(m, k));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation of the approach # define long long N = 2005 ans = dict() # Recursively moving to add # all the numbers upto a limit # with sum of digits as m def dfs(n, left, ct): # Max nber of digits allowed in # a nber for this implementation if (ct >= 15): return if (left == 0): ans[n] = 1 for i in range(min(left, 9) + 1): dfs(n * 10 + i, left - i, ct + 1) # Function to return the kth number # with sum of digits as m def getKthNum(m, k): dfs(0, m, 0) c = 0 for it in sorted(ans.keys()): c += 1 # The kth smallest number is found if (c == k): return it return -1 # Driver code m = 5 k = 3 print(getKthNum(m, k)) # This code is contributed by Mohit Kumar
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
static int N = 2005;
static HashSet<int> ans = new HashSet<int>();
// Recursively moving to add
// all the numbers upto a limit
// with sum of digits as m
static void dfs(int num, int left, int ct)
{
// Max number of digits allowed in
// a number for this implementation
if (ct >= 15)
return;
if (left == 0)
ans.Add(num);
for (int i = 0;
i <= Math.Min(left, 9); i++)
dfs(num * 10 + i, left - i, ct + 1);
}
// Function to return the kth number
// with sum of digits as m
static int getKthNum(int m, int k)
{
dfs(0, m, 0);
int ct = 0;
foreach (int it in ans)
{
ct++;
// The kth smallest number is found
if (ct == k)
{
return it;
}
}
return -1;
}
// Driver code
public static void Main(String[] args)
{
int m = 5, k = 3;
Console.WriteLine(getKthNum(m, k));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the approach
let N = 2005;
let ans = new Set();
// Recursively moving to add
// all the numbers upto a limit
// with sum of digits as m
function dfs(num,left,ct)
{
// Max number of digits allowed in
// a number for this implementation
if (ct >= 15)
return;
if (left == 0)
ans.add(num);
for (let i = 0; i <= Math.min(left, 9); i++)
dfs(num * 10 + i, left - i, ct + 1);
}
// Function to return the kth number
// with sum of digits as m
function getKthNum(m,k)
{
dfs(0, m, 0);
let ct = 0;
for (let it of ans.values())
{
ct++;
// The kth smallest number is found
if (ct == k)
{
return it;
}
}
return -1;
}
// Driver code
let m = 5, k = 3;
document.write(getKthNum(m, k));
// This code is contributed by unknown2108
</script>
Producción:
23