Dados dos enteros positivos N y S . La tarea es minimizar el número de incrementos en N (N = N + 1) necesarios para que la suma de los dígitos de N sea menor o igual que S.
NOTA: N puede variar hasta un número de 18 dígitos y 1 <= S <= 162 .
Ejemplos:
Entrada: N = 600, S = 5
Salida: 400
Explicación: Se requiere un mínimo de 400 incrementos ya que la suma de los dígitos de 1000 (600 + 400) es menor que 5.Entrada: N = 345899211156769, S = 20
Salida: 100788843231
Explicación: Los incrementos mínimos requeridos son 100788843231.
Enfoque: La observación clave aquí es que para minimizar la suma de dígitos de cualquier número en incrementos mínimos, los dígitos que comienzan desde el lugar de la unidad deben minimizarse. Siga los pasos a continuación para resolver el problema dado.
- Para el caso base, si la suma de los dígitos de N ya es menor o igual que S , entonces la salida es 0 .
- Inicialice las variables, digamos ans = 0 y p = 1, donde ans almacenará los incrementos mínimos requeridos y p realizará un seguimiento del lugar de los dígitos, comenzando desde el lugar de la unidad.
- Ejecute un ciclo a través del número máximo de dígitos que N puede tener (es decir, 18) y encuentre el último dígito de N. Que se denote por dígito . Luego encuentre los incrementos mínimos requeridos para convertir este dígito a 0 . Denotado por decir, añadir .
- dígito = (N/p) % 10
- sumar = p * (10 – dígito)
- Incremente N y ans por add .
- Ahora comprueba si la suma de los dígitos de N es menor o igual que S.
- Si la condición es verdadera, salga del bucle y emita la respuesta.
- De lo contrario, multiplique p por 10 para acceder al penúltimo dígito desde el lugar de la unidad de N .
- El bucle se ejecuta de nuevo y se ejecutan los mismos pasos hasta que se encuentra la respuesta requerida.
- Devuelve ans como respuesta final.
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 find the sum
// of digits of N
int findSum(long long int N)
{
// Stores the sum of digits of N
int res = 0;
// Loop to extract the digits of N
// and find their sum
while (N) {
// Extracting the last digit of N
// and adding it to res
res += (N % 10);
// Update N
N /= 10;
}
return res;
}
// Function to find the minimum increments
// required to make the sum of digits of N
// less than or equal to S.
long long int minIncrements(long long int N, int S)
{
// If the sum of digits of N is less than
// or equal to S
if (findSum(N) <= S) {
// Output 0
return 0;
}
// variable to access the digits of N
long long int p = 1;
// Stores the required answer
long long int ans = 0;
// Loop to access the digits of N
for (int i = 0; i <= 18; ++i) {
// Stores the digit of N starting
// from unit's place
int digit = (N / p) % 10;
// Stores the increment required
// to make the digit 0
long long int add = p * (10 - digit);
// Update N
N += add;
// Update ans
ans += add;
// If the sum of digits of N is less than
// or equal to S
if (findSum(N) <= S) {
// Break from the loop
break;
}
// Update p to access the next digit
p = p * 10;
}
return ans;
}
// Driver Code
int main()
{
// Given N and S
long long int N = 345899211156769;
int S = 20;
// Function call
cout << minIncrements(N, S);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
public class GFG
{
// Function to find the sum
// of digits of N
static int findSum(long N)
{
// Stores the sum of digits of N
int res = 0;
// Loop to extract the digits of N
// and find their sum
while (N != 0) {
// Extracting the last digit of N
// and adding it to res
res += (N % 10);
// Update N
N /= 10;
}
return res;
}
// Function to find the minimum increments
// required to make the sum of digits of N
// less than or equal to S.
static long minIncrements(long N, int S)
{
// If the sum of digits of N is less than
// or equal to S
if (findSum(N) <= S) {
// Output 0
return 0;
}
// variable to access the digits of N
long p = 1;
// Stores the required answer
long ans = 0;
// Loop to access the digits of N
for (int i = 0; i <= 18; ++i) {
// Stores the digit of N starting
// from unit's place
long digit = (N / p) % 10;
// Stores the increment required
// to make the digit 0
long add = p * (10 - digit);
// Update N
N += add;
// Update ans
ans += add;
// If the sum of digits of N is less than
// or equal to S
if (findSum(N) <= S) {
// Break from the loop
break;
}
// Update p to access the next digit
p = p * 10;
}
return ans;
}
// Driver Code
public static void main(String args[])
{
// Given N and S
long N = 345899211156769L;
int S = 20;
// Function call
System.out.println(minIncrements(N, S));
}
}
// This code is contributed by Samim Hossain Mondal
Python3
# Python program for the above approach # Function to find the sum # of digits of N def findSum(N): # Stores the sum of digits of N res = 0; # Loop to extract the digits of N # and find their sum while (N): # Extracting the last digit of N # and adding it to res res += (N % 10); # Update N N = N // 10; return res; # Function to find the minimum increments # required to make the sum of digits of N # less than or equal to S. def minIncrements(N, S): # If the sum of digits of N is less than # or equal to S if (findSum(N) <= S): # Output 0 return 0; # variable to access the digits of N p = 1; # Stores the required answer ans = 0; # Loop to access the digits of N for i in range(0, 18): # Stores the digit of N starting # from unit's place digit = (N // p) % 10; # Stores the increment required # to make the digit 0 add = p * (10 - digit); # Update N N += add; # Update ans ans += add; # If the sum of digits of N is less than # or equal to S if (findSum(N) <= S): # Break from the loop break; # Update p to access the next digit p = p * 10; return ans; # Driver Code # Given N and S N = 345899211156769; S = 20; # Function call print(minIncrements(N, S)) # This code is contributed by saurabh_jaiswal.
C#
// C# program for the above approach
using System;
using System.Collections;
class GFG
{
// Function to find the sum
// of digits of N
static long findSum(long N)
{
// Stores the sum of digits of N
long res = 0;
// Loop to extract the digits of N
// and find their sum
while (N != 0) {
// Extracting the last digit of N
// and adding it to res
res += (N % 10);
// Update N
N /= 10;
}
return res;
}
// Function to find the minimum increments
// required to make the sum of digits of N
// less than or equal to S.
static long minIncrements(long N, long S)
{
// If the sum of digits of N is less than
// or equal to S
if (findSum(N) <= S) {
// Output 0
return 0;
}
// variable to access the digits of N
long p = 1;
// Stores the required answer
long ans = 0;
// Loop to access the digits of N
for (int i = 0; i <= 18; ++i) {
// Stores the digit of N starting
// from unit's place
long digit = (N / p) % 10;
// Stores the increment required
// to make the digit 0
long add = p * (10 - digit);
// Update N
N += add;
// Update ans
ans += add;
// If the sum of digits of N is less than
// or equal to S
if (findSum(N) <= S) {
// Break from the loop
break;
}
// Update p to access the next digit
p = p * 10;
}
return ans;
}
// Driver Code
public static void Main()
{
// Given N and S
long N = 345899211156769;
long S = 20;
// Function call
Console.Write(minIncrements(N, S));
}
}
// This code is contributed by Samim Hossain Mondal
Javascript
<script>
// Javascript program for the above approach
// Function to find the sum
// of digits of N
function findSum(N)
{
// Stores the sum of digits of N
let res = 0;
// Loop to extract the digits of N
// and find their sum
while (N) {
// Extracting the last digit of N
// and adding it to res
res += (N % 10);
// Update N
N /= 10;
}
return res;
}
// Function to find the minimum increments
// required to make the sum of digits of N
// less than or equal to S.
function minIncrements(N, S) {
// If the sum of digits of N is less than
// or equal to S
if (findSum(N) <= S) {
// Output 0
return 0;
}
// variable to access the digits of N
let p = 1;
// Stores the required answer
let ans = 0;
// Loop to access the digits of N
for (let i = 0; i <= 18; ++i) {
// Stores the digit of N starting
// from unit's place
let digit = (N / p) % 10;
// Stores the increment required
// to make the digit 0
let add = p * (10 - digit);
// Update N
N += add;
// Update ans
ans += add;
// If the sum of digits of N is less than
// or equal to S
if (findSum(N) <= S) {
// Break from the loop
break;
}
// Update p to access the next digit
p = p * 10;
}
return ans;
}
// Driver Code
// Given N and S
let N = 345899211156769;
let S = 20;
// Function call
document.write(minIncrements(N, S))
// This code is contributed by saurabh_jaiswal.
</script>
Producción
100788843231
Complejidad temporal: O(18*logN).
Espacio Auxiliar: O(1).
Publicación traducida automáticamente
Artículo escrito por anusha00466 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA