Dado un número natural N y un número entero L , la tarea es encontrar la cuenta de números, menores o iguales a N, tal que la diferencia entre el número y la suma de sus dígitos no sea menor que L.
Ejemplos:
Input: N = 1500, L = 30 Output: 1461 Input: N = 1546300, L = 30651 Output: 1515631
Enfoque:
Nuestra solución depende de una simple observación de que si un número, digamos X, es tal que la diferencia de X y sumOfDigits(X) es menor o igual que L, entonces X+1 también es un número válido. Por lo tanto, tenemos que encontrar un mínimo tal X usando la búsqueda binaria .
Implementación:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the
// sum of digits
int sumOfDigits(long long n)
{
long long sum = 0;
while (n > 0) {
sum += n % 10;
n /= 10;
}
return sum;
}
// Function to count the numbers
long long countDigits(long long num, long long limit)
{
long long left = 1, right = num, result = 0;
// use binary search
while (left <= right) {
long long mid = (right + left) / 2;
// Check if you are at a valid number or not
if ((mid - sumOfDigits(mid)) >= limit) {
// update the answer at each valid step
result = num - mid + 1;
right = mid - 1;
}
else {
left = mid + 1;
}
}
// return the answer
return result;
}
// Driver code
int main()
{
// Get the value of N and L
long long N = 1546300, L = 30651;
// Count the numbers
cout << countDigits(N, L);
return 0;
}
Java
// Java implementation of above approach
class GFG
{
// Function to calculate the
// sum of digits
static long sumOfDigits( long n )
{
long sum = 0;
while (n > 0)
{
sum += n % 10;
n /= 10;
}
return sum;
}
// Function to count the numbers
static long countDigits(long num, long limit)
{
long left = 1, right = num, result = 0;
// use binary search
while (left <= right)
{
long mid = (right + left) / 2;
// Check if you are at a valid number or not
if ((mid - sumOfDigits(mid)) >= limit)
{
// update the answer at each valid step
result = num - mid + 1;
right = mid - 1;
}
else
{
left = mid + 1;
}
}
// return the answer
return result;
}
// Driver code
public static void main(String []args)
{
// Get the value of N and L
long N = 1546300, L = 30651;
// Count the numbers
System.out.println(countDigits(N, L));
}
}
// This code is contributed by ihritik
Python3
# Python3 program for above approach # Function to calculate the sum of digits def sumOfDigits(n): sum = 0 while (n > 0): sum += n % 10 n = int(n / 10) return sum # Function to count the numbers def countDigits(num, limit): left = 1 right = num result = 0 # use binary search while (left <= right): mid = int((right + left) / 2) # Check if you are at a valid number or not if ((mid - sumOfDigits(mid)) >= limit): # update the answer at each valid step result = num - mid + 1 right = mid - 1 else: left = mid + 1 # return the answer return result # Driver code if __name__ == '__main__': # Get the value of N and L N = 1546300 L = 30651 # Count the numbers print(countDigits(N, L)) # This code is contributed by # Surendra_Gangwar
C#
// C# implementation of above approach
using System;
class GFG
{
// Function to calculate the
// sum of digits
static long sumOfDigits( long n )
{
long sum = 0;
while (n > 0)
{
sum += n % 10;
n /= 10;
}
return sum;
}
// Function to count the numbers
static long countDigits(long num, long limit)
{
long left = 1, right = num, result = 0;
// use binary search
while (left <= right) {
long mid = (right + left) / 2;
// Check if you are at a valid number or not
if ((mid - sumOfDigits(mid)) >= limit)
{
// update the answer at each valid step
result = num - mid + 1;
right = mid - 1;
}
else
{
left = mid + 1;
}
}
// return the answer
return result;
}
// Driver code
public static void Main()
{
// Get the value of N and L
long N = 1546300, L = 30651;
// Count the numbers
Console.WriteLine(countDigits(N, L));
}
}
// This code is contributed by ihritik
PHP
<?php
// PHP implementation of the above approach
// Function to calculate the
// sum of digits
function sumOfDigits($n)
{
$sum = 0;
while ($n > 0)
{
$sum += $n % 10;
$n /= 10;
}
return $sum;
}
// Function to count the numbers
function countDigits($num, $limit)
{
$left = 1;
$right = $num;
$result = 0;
// use binary search
while ($left <= $right)
{
$mid = floor(($right + $left) / 2);
// Check if you are at a valid number or not
if (($mid - sumOfDigits($mid)) >= $limit)
{
// update the answer at each valid step
$result = $num - $mid + 1;
$right = $mid - 1;
}
else
{
$left = $mid + 1;
}
}
// return the answer
return $result;
}
// Driver code
// Get the value of N and L
$N = 1546300;
$L = 30651;
// Count the numbers
echo countDigits($N, $L);
// This code is contributed by Ryuga
?>
Javascript
<script>
// JavaScript implementation of above approach
// Function to calculate the
// sum of digits
function sumOfDigits(n)
{
let sum = 0;
while (n > 0)
{
sum += n % 10;
n = parseInt(n / 10, 10);
}
return sum;
}
// Function to count the numbers
function countDigits(num, limit)
{
let left = 1, right = num, result = 0;
// use binary search
while (left <= right) {
let mid = parseInt((right + left) / 2, 10);
// Check if you are at a valid number or not
if ((mid - sumOfDigits(mid)) >= limit)
{
// update the answer at each valid step
result = num - mid + 1;
right = mid - 1;
}
else
{
left = mid + 1;
}
}
// return the answer
return result;
}
// Get the value of N and L
let N = 1546300, L = 30651;
// Count the numbers
document.write(countDigits(N, L));
</script>
Producción:
1515631
Complejidad de tiempo : O(log N)
Espacio auxiliar : O(1)
Publicación traducida automáticamente
Artículo escrito por NaimishSingh y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA