Dado el número entero N y el número entero S , la tarea es encontrar el número más pequeño mayor o igual que N tal que la suma de sus dígitos no exceda S.
Ejemplos:
Entrada: N = 3, S = 2
Salida: 10
Explicación: La suma de los dígitos de 10 es 1, que es menor que 2.Entrada: N = 19, S = 3
Salida: 20
Explicación: La suma de los dígitos de 20 es 2, que es menor que 3.
Enfoque: el problema se puede resolver utilizando un enfoque codicioso . Siga los pasos a continuación para resolver el problema.
- Compruebe si la suma de los dígitos de N no excede S , devuelva N .
- Inicialice una variable, digamos ans igual al número entero dado N y k con 1 para almacenar las potencias de 10 .
- Puede haber como máximo 10 dígitos en el rango de enteros.
- Iterar de i = 0 a 8 . En cada iteración, calcule el último dígito como (ans / k)%10 .
- La suma para hacer el último dígito 0 es k*((10-last_digit)%10) . Añádelo a ans .
- Comprueba la suma de dígitos de ans . Si no excede S , imprima ans y rompa. De lo contrario, actualice k como k = k*10 y repita los pasos anteriores.
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;
// Function to calculate sum
// digits of n
int sum(int n)
{
int res = 0;
while (n > 0) {
res += n % 10;
n /= 10;
}
return res;
}
// Function to find the smallest
// possible integer satisfying the
// given condition
int smallestNumber(int n, int s)
{
// If the sum of digits
// is already smaller than S
if (sum(n) <= s) {
return n;
}
// Initialize variables
int ans = n, k = 1;
for (int i = 0; i < 9; ++i) {
// Finding last kth digit
int digit = (ans / k) % 10;
// Add remaining to make digit 0
int add = k * ((10 - digit) % 10);
ans += add;
// If sum of digits
// does not exceed S
if (sum(ans) <= s) {
break;
}
// Update k
k *= 10;
}
return ans;
}
// Driver Code
int main()
{
// Given N and S
int N = 3, S = 2;
// Function call
cout << smallestNumber(N, S) << endl;
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG{
// Function to calculate sum
// digits of n
static int sum(int n)
{
int res = 0;
while (n > 0)
{
res += n % 10;
n /= 10;
}
return res;
}
// Function to find the smallest
// possible integer satisfying the
// given condition
static int smallestNumber(int n, int s)
{
// If the sum of digits
// is already smaller than S
if (sum(n) <= s)
{
return n;
}
// Initialize variables
int ans = n, k = 1;
for(int i = 0; i < 9; ++i)
{
// Finding last kth digit
int digit = (ans / k) % 10;
// Add remaining to make digit 0
int add = k * ((10 - digit) % 10);
ans += add;
// If sum of digits
// does not exceed S
if (sum(ans) <= s)
{
break;
}
// Update k
k *= 10;
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
// Given N and S
int N = 3, S = 2;
// Function call
System.out.println(smallestNumber(N, S));
}
}
// This code is contributed by akhilsaini
Python3
# Python program for the above approach # Function to calculate # sum of digits of n def sum(n): sm = 0 while(n > 0): sm += n % 10 n //= 10 return sm # Function to find the smallest # possible integer satisfying the # given condition def smallestNumber(n, s): # If sum of digits is # already smaller than s if(sum(n) <= s): return n # Initialize variables ans, k = n, 1 for i in range(9): # Find the k-th digit digit = (ans // k) % 10 # Add remaining add = k * ((10 - digit) % 10) ans += add # If sum of digits # does not exceed s if(sum(ans) <= s): break # Update K k *= 10 # Return answer return ans # Driver Code # Given N and S n, s = 3, 2 # Function call print(smallestNumber(n, s))
C#
// C# program for the above approach
using System;
class GFG{
// Function to calculate sum
// digits of n
static int sum(int n)
{
int res = 0;
while (n > 0)
{
res += n % 10;
n /= 10;
}
return res;
}
// Function to find the smallest
// possible integer satisfying the
// given condition
static int smallestNumber(int n, int s)
{
// If the sum of digits
// is already smaller than S
if (sum(n) <= s)
{
return n;
}
// Initialize variables
int ans = n, k = 1;
for(int i = 0; i < 9; ++i)
{
// Finding last kth digit
int digit = (ans / k) % 10;
// Add remaining to make digit 0
int add = k * ((10 - digit) % 10);
ans += add;
// If sum of digits
// does not exceed S
if (sum(ans) <= s)
{
break;
}
// Update k
k *= 10;
}
return ans;
}
// Driver Code
public static void Main()
{
// Given N and S
int N = 3, S = 2;
// Function call
Console.WriteLine(smallestNumber(N, S));
}
}
// This code is contributed by akhilsaini
Javascript
<script>
// javascript program for the above approach
// Function to calculate sum
// digits of n
function sum(n)
{
var res = 0;
while (n > 0)
{
res += n % 10;
n /= 10;
}
return res;
}
// Function to find the smallest
// possible integer satisfying the
// given condition
function smallestNumber(n , s)
{
// If the sum of digits
// is already smaller than S
if (sum(n) <= s)
{
return n;
}
// Initialize variables
var ans = n, k = 1;
for(i = 0; i < 9; ++i)
{
// Finding last kth digit
var digit = (ans / k) % 10;
// Add remaining to make digit 0
var add = k * ((10 - digit) % 10);
ans += add;
// If sum of digits
// does not exceed S
if (sum(ans) <= s)
{
break;
}
// Update k
k *= 10;
}
return ans;
}
// Driver Code
// Given N and S
var N = 3, S = 2;
// Function call
document.write(smallestNumber(N, S));
// This code is contributed by shikhasingrajput.
</script>
Producción:
10
Complejidad de tiempo: O(log 2 10 (N)) donde N es el número entero dado.
Complejidad espacial: O(1)