Dado un número entero N, averigüe la cantidad de números (m) que satisfacen la condición m + sum (m) + sum (sum (m)) = N, donde sum (m) denota la suma de dígitos en m. Dado N <= 10e9.
Ejemplos:
Input: 9
Output: 1
Explanation: Only 1 positive integer satisfies
the condition that is 3,
3 + sum(3) + sum(sum(3)) = 3 + 3 + 3
= 9
Input: 9939
Output: 4
Explanation: m can be 9898, 9907, 9910 and 9913.
9898 + sum(9898) + sum(sum(9898))
= 9898 + 34 + 7 = 9939.
9907 + sum(9907) + sum(sum(9907))
= 9907 + 25 + 7 = 9939.
9910 + sum(9910) + sum(sum(9910))
= 9910 + 19 + 10 = 9939.
9913 + sum(9913) + sum(sum(9913))
= 9913 + 22 + 4 = 9939.
Enfoque: Lo primero que hay que tener en cuenta es que se nos da la restricción N<=10e9. Esto significa que sum(x) puede ser como máximo 81 para cualquier número. Esto se debe a que el número más grande debajo de 10e9 es 999999999 cuyos dígitos suman 81. El caso máximo para sum(sum(x)) será 16 (siendo el número 79 <=81), por lo que al máximo 81 + 16, que es 97, debe verificarse. Solo necesitamos iterar de N – 97 a N y comprobar qué enteros satisfacen la ecuación porque ningún entero menor que N-97 puede satisfacer la ecuación y tampoco ningún entero mayor que N.
A continuación se muestra la implementación del enfoque anterior.
C++
// CPP program to count numbers
// satisfying equation.
#include <bits/stdc++.h>
using namespace std;
// function that returns sum of
// digits in a number
int sum(int n)
{
int rem = 0;
// initially sum of digits is 0
int sum_of_digits = 0;
// loop runs till all digits
// have been extracted
while (n > 0) {
// last digit from backside
rem = n % 10;
// sums up the digits
sum_of_digits += rem;
// the number is reduced to the
// number removing the last digit
n = n / 10;
}
// returns the sum of digits in a number
return sum_of_digits;
}
// function to calculate the count of
// such occurrences
int count(int n)
{
// counter to calculate the occurrences
int c = 0;
// loop to traverse from n-97 to n
for (int i = n - 97; i <= n; i++) {
// calls the function to calculate
// the sum of digits of i
int a = sum(i);
// calls the function to calculate
// the sum of digits of a
int b = sum(a);
// if the summation is equal to n
// then increase counter by 1
if ((i + a + b) == n) {
c += 1;
}
}
// returns the count
return c;
}
// driver program to test the above function
int main()
{
int n = 9939;
// calls the function to get the answer
cout << count(n) << endl;
return 0;
}
Java
// Java program to count numbers
// satisfying equation.
import java.io.*;
class GFG {
// function that returns sum of
// digits in a number
static int sum(int n)
{
int rem = 0;
// initially sum of digits is 0
int sum_of_digits = 0;
// loop runs till all digits
// have been extracted
while (n > 0)
{
// last digit from backside
rem = n % 10;
// sums up the digits
sum_of_digits += rem;
// the number is reduced to the
// number removing the last digit
n = n / 10;
}
// returns the sum of digits in a number
return sum_of_digits;
}
// function to calculate the count of
// such occurrences
static int count(int n)
{
// counter to calculate the occurrences
int c = 0;
// loop to traverse from n-97 to n
for (int i = n - 97; i <= n; i++)
{
// calls the function to calculate
// the sum of digits of i
int a = sum(i);
// calls the function to calculate
// the sum of digits of a
int b = sum(a);
// if the summation is equal to n
// then increase counter by 1
if ((i + a + b) == n)
{
c += 1;
}
}
// returns the count
return c;
}
// driver program to test the above function
public static void main (String[] args)
{
int n = 9939;
// calls the function to get the answer
System.out.println ( count(n) );
}
}
// This article is contributed by vt_m
Python3
# Python program # to count numbers # satisfying equation. # function that returns sum of # digits in a number def sum(n): rem = 0 #initially sum of digits is 0 sum_of_digits = 0 # loop runs till all digits # have been extracted while (n > 0): # last digit from backside rem = n % 10 # sums up the digits sum_of_digits += rem # the number is reduced to the # number removing the last digit n = n // 10 # returns the sum # of digits in a number return sum_of_digits # function to calculate # the count of # such occurrences def count(n): # counter to calculate the occurrences c = 0 # loop to traverse from n - 97 to n for i in range(n - 97,n+1): # calls the function to calculate # the sum of digits of i a = sum(i) # calls the function to calculate # the sum of digits of a b = sum(a) # if the summation is equal to n # then increase counter by 1 if ((i + a + b) == n): c += 1 # returns the count return c # driver program to test # the above function n = 9939 # calls the function # to get the answer print(count(n)) # This code is contributed # by Anant Agarwal.
C#
// C# program to count numbers
// satisfying equation.
using System;
class GFG {
// function that returns sum
// of digits in a number
static int sum(int n)
{
int rem = 0;
// initially sum of
// digits is 0
int sum_of_digits = 0;
// loop runs till all digits
// have been extracted
while (n > 0)
{
// last digit from
// backside
rem = n % 10;
// sums up the digits
sum_of_digits += rem;
// the number is reduced
// to the number removing
// the last digit
n = n / 10;
}
// returns the sum of
// digits in a number
return sum_of_digits;
}
// function to calculate the
// count of such occurrences
static int count(int n)
{
// counter to calculate
// the occurrences
int c = 0;
// loop to traverse from n-97 to n
for (int i = n - 97; i <= n; i++)
{
// calls the function to calculate
// the sum of digits of i
int a = sum(i);
// calls the function to calculate
// the sum of digits of a
int b = sum(a);
// if the summation is equal to n
// then increase counter by 1
if ((i + a + b) == n)
{
c += 1;
}
}
// returns the count
return c;
}
// Driver Code
public static void Main ()
{
int n = 9939;
// calling the function
Console.Write ( count(n) );
}
}
// This code is contributed by Nitin Mittal.
PHP
<?php
// PHP program to count numbers
// satisfying equation.
// function that returns sum of
// digits in a number
function sum($n)
{
$rem = 0;
// initially sum of
// digits is 0
$sum_of_digits = 0;
// loop runs till all digits
// have been extracted
while ($n > 0)
{
// last digit from backside
$rem = $n % 10;
// sums up the digits
$sum_of_digits += $rem;
// the number is reduced to the
// number removing the last digit
$n = $n / 10;
}
// returns the sum of
// digits in a number
return $sum_of_digits;
}
// function to calculate the
// count of such occurrences
function countt($n)
{
// counter to calculate
// the occurrences
$c = 0;
// loop to traverse
// from n-97 to n
for ($i = $n - 97; $i <= $n; $i++)
{
// calls the function to calculate
// the sum of digits of i
$a = sum($i);
// calls the function to calculate
// the sum of digits of a
$b = sum($a);
// if the summation is equal to n
// then increase counter by 1
if (($i + $a + $b) == $n)
{
$c += 1;
}
}
// returns the count
return $c;
}
// Driver Code
$n = 9939;
// calls the function
// to get the answer
echo countt($n) ;
//This code is contributed by nitin mittal.
?>
Javascript
<script>
// javascript program to count numbers
// satisfying equation.
// function that returns sum of
// digits in a number
function sum(n)
{
var rem = 0;
// initially sum of digits is 0
var sum_of_digits = 0;
// loop runs till all digits
// have been extracted
while (n > 0)
{
// last digit from backside
rem = n % 10;
// sums up the digits
sum_of_digits += rem;
// the number is reduced to the
// number removing the last digit
n = parseInt(n / 10);
}
// returns the sum of digits in a number
return sum_of_digits;
}
// function to calculate the count of
// such occurrences
function count(n)
{
// counter to calculate the occurrences
var c = 0;
// loop to traverse from n-97 to n
for (i = n - 97; i <= n; i++)
{
// calls the function to calculate
// the sum of digits of i
var a = sum(i);
// calls the function to calculate
// the sum of digits of a
var b = sum(a);
// if the summation is equal to n
// then increase counter by 1
if ((i + a + b) == n) {
c += 1;
}
}
// returns the count
return c;
}
// driver program to test the above function
var n = 9939;
// calls the function to get the answer
document.write(count(n));
// This code is contributed by Rajput-Ji
</script>
Producción:
4
Complejidad de tiempo : O (log 10 N + 97), ya que estamos usando dos bucles para atravesar log 10 N y 97 veces.
Espacio auxiliar : O(1), ya que no estamos utilizando ningún espacio adicional.
Este artículo es una contribución de Raja Vikramaditya . 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