Dado un valor N positivo, necesitamos encontrar el conteo de números menores que N tales que la diferencia entre el número y la suma de sus dígitos sea mayor o igual al valor diff específico dado.
Ejemplos:
Input : N = 13, diff = 2 Output : 4 Then 10, 11, 12 and 13 satisfy the given condition shown below, 10 – sumofdigit(10) = 9 >= 2 11 – sumofdigit(11) = 9 >= 2 12 – sumofdigit(12) = 9 >= 2 13 – sumofdigit(13) = 9 >= 2 Whereas no number from 1 to 9 satisfies above equation so final result will be 4
Podemos resolver este problema observando el hecho de que para un número k menor que N,
if k – sumofdigit(k) >= diff then above equation will be true for (k+1) also because we know that sumofdigit(k+1) is not greater than sumofdigit(k) + 1 so, k + 1 - sumofdigit(k + 1) >= k - sumofdigit(k) but we know that right side of above inequality is greater than diff, so left side will also be greater than diff.
Entonces, finalmente podemos decir que si un número k satisface la condición de diferencia, entonces (k + 1) también satisfará la misma ecuación, por lo que nuestro trabajo es encontrar el número más pequeño que satisfaga la condición de diferencia, luego todos los números mayores que esto y hasta N satisfará la condición, por lo que nuestra respuesta será N, el número más pequeño que encontramos.
Podemos encontrar el número más pequeño que satisfaga esta condición mediante la búsqueda binaria, por lo que la complejidad temporal total de la solución será O (log N)
C++
/* C++ program to count total numbers which
have difference with sum of digits greater
than specific value */
#include <bits/stdc++.h>
using namespace std;
// Utility method to get sum of digits of K
int sumOfDigit(int K)
{
// loop until K is not zero
int sod = 0;
while (K)
{
sod += K % 10;
K /= 10;
}
return sod;
}
// method returns count of numbers smaller than N,
// satisfying difference condition
int totalNumbersWithSpecificDifference(int N, int diff)
{
int low = 1, high = N;
// binary search while loop
while (low <= high)
{
int mid = (low + high) / 2;
/* if difference between number and its sum
of digit is smaller than given difference
then smallest number will be on left side */
if (mid - sumOfDigit(mid) < diff)
low = mid + 1;
/* if difference between number and its sum
of digit is greater than or equal to given
difference then smallest number will be on
right side */
else
high = mid - 1;
}
// return the difference between 'smallest number
// found' and 'N' as result
return (N - high);
}
// Driver code to test above methods
int main()
{
int N = 13;
int diff = 2;
cout << totalNumbersWithSpecificDifference(N, diff);
return 0;
}
Java
/* Java program to count total numbers which
have difference with sum of digits greater
than specific value */
class Test
{
// Utility method to get sum of digits of K
static int sumOfDigit(int K)
{
// loop until K is not zero
int sod = 0;
while (K != 0)
{
sod += K % 10;
K /= 10;
}
return sod;
}
// method returns count of numbers smaller than N,
// satisfying difference condition
static int totalNumbersWithSpecificDifference(int N, int diff)
{
int low = 1, high = N;
// binary search while loop
while (low <= high)
{
int mid = (low + high) / 2;
/* if difference between number and its sum
of digit is smaller than given difference
then smallest number will be on left side */
if (mid - sumOfDigit(mid) < diff)
low = mid + 1;
/* if difference between number and its sum
of digit is greater than or equal to given
difference then smallest number will be on
right side */
else
high = mid - 1;
}
// return the difference between 'smallest number
// found' and 'N' as result
return (N - high);
}
// Driver method
public static void main(String args[])
{
int N = 13;
int diff = 2;
System.out.println(totalNumbersWithSpecificDifference(N, diff));
}
}
Python3
# Python program to count total numbers which # have difference with sum of digits greater # than specific value # Utility method to get sum of digits of K def sumOfDigit(K): # loop until K is not zero sod = 0 while (K): sod =sod + K % 10 K =K // 10 return sod # method returns count of # numbers smaller than N, # satisfying difference condition def totalNumbersWithSpecificDifference(N,diff): low = 1 high = N # binary search while loop while (low <= high): mid = (low + high) // 2 ''' if difference between number and its sum of digit is smaller than given difference then smallest number will be on left side''' if (mid - sumOfDigit(mid) < diff): low = mid + 1 # if difference between number and its sum # of digit greater than equal to given # difference then smallest number will be on # right side else: high = mid - 1 # return the difference between 'smallest number # found' and 'N' as result return (N - high) # Driver code to test above methods N = 13 diff = 2 print(totalNumbersWithSpecificDifference(N, diff)) # This code is contributed by Anant Agarwal.
C#
// C# program to count total numbers
// which have difference with sum of
// digits greater than specific value
using System;
class Test {
// Utility method to get sum
// of digits of K
static int sumOfDigit(int K)
{
// loop until K is not zero
int sod = 0;
while (K != 0)
{
sod += K % 10;
K /= 10;
}
return sod;
}
// method returns count of numbers
// smaller than N, satisfying
// difference condition
static int totalNumbersWithSpecificDifference(int N,
int diff)
{
int low = 1, high = N;
// binary search while loop
while (low <= high)
{
int mid = (low + high) / 2;
// if difference between number and
// its sum of digit is smaller than
// given difference then smallest
// number will be on left side
if (mid - sumOfDigit(mid) < diff)
low = mid + 1;
// if difference between number and
// its sum of digit is greater than
// or equal to given difference then
// smallest number will be on right side
else
high = mid - 1;
}
// return the difference between
// 'smallest number found'
// and 'N' as result
return (N - high);
}
// Driver code
public static void Main()
{
int N = 13;
int diff = 2;
Console.Write(totalNumbersWithSpecificDifference(N, diff));
}
}
// This code is contributed by nitin mittal
PHP
<?php
// PHP program to count total numbers which
// have difference with sum of digits greater
// than specific value
// method to get sum of digits of K
function sumOfDigit($K)
{
// loop until K is not zero
$sod = 0;
while ($K)
{
$sod += $K % 10;
$K /= 10;
}
return $sod;
}
// method returns count of
// numbers smaller than N,
// satisfying difference condition
function totalNumbersWithSpecificDifference($N, $diff)
{
$low = 1; $high = $N;
// binary search while loop
while ($low <= $high)
{
$mid = floor(($low + $high) / 2);
/* if difference between number and its sum
of digit is smaller than given difference
then smallest number will be on left side */
if ($mid - sumOfDigit($mid) < $diff)
$low = $mid + 1;
/* if difference between number and its sum
of digit is greater than or equal to given
difference then smallest number will be on
right side */
else
$high = $mid - 1;
}
// return the difference
// between 'smallest number
// found' and 'N' as result
return ($N - $high);
}
// Driver Code
$N = 13;
$diff = 2;
echo totalNumbersWithSpecificDifference($N, $diff);
// This code is contributed by nitin mittal
?>
Javascript
<script>
// javascript program to
// count total numbers which
// have difference with sum
// of digits greater
// than specific value
// method to get sum of digits of K
function sumOfDigit(K)
{
// loop until K is not zero
let sod = 0;
while (K)
{
sod += K % 10;
K /= 10;
}
return sod;
}
// method returns count of
// numbers smaller than N,
// satisfying difference condition
function
totalNumbersWithSpecificDifference(N, diff)
{
let low = 1;
let high = N;
// binary search while loop
while (low <= high)
{
let mid = Math.floor((low + high) / 2);
/* if difference between number and its sum
of digit is smaller than given difference
then smallest number will be on left side */
if (mid - sumOfDigit(mid) < diff)
low = mid + 1;
/* if difference between number and its sum
of digit is greater than or equal to given
difference then smallest number will be on
right side */
else
high = mid - 1;
}
// return the difference
// between 'smallest number
// found' and 'N' as result
return (N - high);
}
// Driver Code
let N = 13;
let diff = 2;
document.write(
totalNumbersWithSpecificDifference(N, diff)
);
// This code is contributed by Bobby
</script>
Producción:
4
Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA