Dado un número positivo N. Necesitamos encontrar números tales que la suma de los dígitos de esos números entre sí sea igual a N. Si no es posible tal número, imprima -1. aquí norte ![\en [1, 1000000000]](https://www.geeksforgeeks.org/wp-content/ql-cache/quicklatex.com-a1185ce5f0b3708f280fa7f2ad459cc7_l3.png "Procesado por QuickLaTeX.com")
Ejemplos:
Input : N = 21
Output : X = 15
Explanation : X + its digit sum
= 15 + 1 + 5
= 21
Input : N = 5
Output : -1
Input : N = 100000001
Output : X = 99999937
X = 100000000
Método 1: (Enfoque ingenuo)
Ya hemos discutido el enfoque aquí . El enfoque podría no funcionar para N tan grande como 
.
Método 2: (Eficiente)
Es un hecho que para un número X < = 1000000000, la suma de dígitos nunca excede 100. Usando esta información, podemos iterar sobre todas las posibilidades en el rango de 0 a 100 en ambos lados de el número y verifique si el número X es igual a N – suma de dígitos de X. Todas las posibilidades estarán cubiertas en este rango.
C++
// CPP program to find x such that
// X + sumOfDigits(X) = N
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <vector>
using namespace std;
// Computing the sum of digits of x
int sumOfDigits(long int x)
{
int sum = 0;
while (x > 0) {
sum += x % 10;
x /= 10;
}
return sum;
}
// Checks for 100 numbers on both left
// and right side of the given number to
// find such numbers X such that X +
// sumOfDigits(X) = N and updates the answer
// vector accordingly
void compute(vector<long int>& answer, long int n)
{
// Checking for all possibilities of
// the answer
for (int i = 0; i <= 100; i++) {
// Evaluating the value on the left
// side of the given number
long int valueOnLeft = abs(n - i) +
sumOfDigits(abs(n - i));
// Evaluating the value on the right
// side of the given number
long int valueOnRight = n + i + sumOfDigits(n + i);
// Checking the condition of equality
// on both sides of the given number N
// and updating the answer vector
if (valueOnLeft == n)
answer.push_back(abs(n - i));
if (valueOnRight == n)
answer.push_back(n + i);
}
}
// Driver Function
int main()
{
long int N = 100000001;
vector<long int> answer;
compute(answer, N);
// If no solution exists, print -1
if (answer.size() == 0)
cout << -1;
else {
// If one or more solutions are possible,
// printing them!
for (auto it = answer.begin(); it != answer.end(); ++it)
cout << "X = " << (*it) << endl;
}
return 0;
}
Java
// Java program to find x such that
// X + sumOfDigits(X) = N
import java.util.*;
import java.lang.*;
import java.io.*;
class GeeksforGeeks {
// Computing the sum of digits of x
static int sumOfDigits(long x)
{
int sum = 0;
while (x > 0) {
sum += (x % 10);
x /= 10;
}
return sum;
}
// Checks for 100 numbers on both left
// and right side of the given number to
// find such numbers X such that
// X + sumOfDigits(X) = N and prints solution.
static void compute(long n)
{
long answer[] = new long[100];
int pos = 0;
// Checking for all possibilities of the answer
// in the given range
for (int i = 0; i <= 100; i++) {
// Evaluating the value on the left side of the
// given number
long valueOnLeft = Math.abs(n - i) +
sumOfDigits(Math.abs(n - i));
// Evaluating the value on the right side of the
// given number
long valueOnRight = (n + i) + sumOfDigits(n + i);
if (valueOnRight == n)
answer[pos++] = (n + i);
if (valueOnLeft == n)
answer[pos++] = Math.abs(n - i);
}
if (pos == 0)
System.out.print(-1);
else
for (int i = 0; i < pos; i++)
System.out.println("X = " + answer[i]);
}
// Driver Function
public static void main(String[] args)
{
long N = 100000001;
compute(N);
}
}
Python3
# Python3 program to find x such that
# X + sumOfDigits(X) = N
# Computing the sum of digits of x
def sumOfDigits(x):
sum = 0;
while (x > 0):
sum += (x % 10);
x = int(x / 10);
return sum;
# Checks for 100 numbers on both left
# and right side of the given number
# to find such numbers X such that
# X + sumOfDigits(X) = N and prints
# solution.
def compute(n):
answer = [];
pos = 0;
# Checking for all possibilities
# of the answer in the given range
for i in range(101):
# Evaluating the value on the
# left side of the given number
valueOnLeft = (abs(n - i) +
sumOfDigits(abs(n - i)));
# Evaluating the value on the right
# side of the given number
valueOnRight = (n + i) + sumOfDigits(n + i);
if (valueOnRight == n):
answer.append(n + i);
if (valueOnLeft == n):
answer.append(abs(n - i));
if (len(answer)== 0):
print(-1);
else:
for i in range(len(answer)):
print("X =", answer[i]);
# Driver Code
N = 100000001;
compute(N);
# This code is contributed
# by mits
C#
// C# program to find x such that
// X + sumOfDigits(X) = N
using System;
public class GFG{
// Computing the sum of digits of x
static int sumOfDigits(long x)
{
int sum = 0;
while (x > 0) {
sum += (int)(x % 10);
x /= 10;
}
return sum;
}
// Checks for 100 numbers on both left
// and right side of the given number to
// find such numbers X such that
// X + sumOfDigits(X) = N and prints solution.
static void compute(long n)
{
long []answer = new long[100];
int pos = 0;
// Checking for all possibilities of the answer
// in the given range
for (int i = 0; i <= 100; i++) {
// Evaluating the value on the left side of the
// given number
long valueOnLeft = Math.Abs(n - i) +
sumOfDigits(Math.Abs(n - i));
// Evaluating the value on the right side of the
// given number
long valueOnRight = (n + i) + sumOfDigits(n + i);
if (valueOnRight == n)
answer[pos++] = (n + i);
if (valueOnLeft == n)
answer[pos++] = Math.Abs(n - i);
}
if (pos == 0)
Console.Write(-1);
else
for (int i = 0; i < pos; i++)
Console.WriteLine("X = " + answer[i]);
}
// Driver Function
static public void Main (){
long N = 100000001;
compute(N);
}
}
PHP
<?php
// PHP program to find x such that
// X + sumOfDigits(X) = N
// Computing the sum of digits of x
function sumOfDigits($x)
{
$sum = 0;
while ($x > 0)
{
$sum += ($x % 10);
$x = (int)$x / 10;
}
return $sum;
}
// Checks for 100 numbers on both left
// and right side of the given number
// to find such numbers X such that
// X + sumOfDigits(X) = N and prints
// solution.
function compute($n)
{
$answer = array(0);
$pos = 0;
// Checking for all possibilities
// of the answer in the given range
for ($i = 0; $i <= 100; $i++)
{
// Evaluating the value on the
// left side of the given number
$valueOnLeft = abs($n - $i) +
sumOfDigits(abs($n - $i));
// Evaluating the value on the right
// side of the given number
$valueOnRight = ($n + $i) + sumOfDigits($n + $i);
if ($valueOnRight == $n)
$answer[$pos++] = ($n + $i);
if ($valueOnLeft == $n)
$answer[$pos++] =abs($n - $i);
}
if ($pos == 0)
echo (-1),"\n";
else
for ($i = 0; $i < $pos; $i++)
echo "X = ", $answer[$i], "\n";
}
// Driver Code
$N = 100000001;
compute($N);
// This code is contributed
// by Sach_Code
?>
Javascript
<script>
// JavaScript program to find x such that
// X + sumOfDigits(X) = N
// Computing the sum of digits of x
function sumOfDigits(x)
{
let sum = 0;
while (x > 0)
{
sum += (x % 10);
x = Math.floor(x / 10);
}
return sum;
}
// Checks for 100 numbers on both left
// and right side of the given number to
// find such numbers X such that
// X + sumOfDigits(X) = N and prints solution.
function compute(n)
{
let answer = [];
let pos = 0;
// Checking for all possibilities
// of the answer in the given range
for(let i = 0; i <= 100; i++)
{
// Evaluating the value on the
// left side of the given number
let valueOnLeft = Math.abs(n - i) +
sumOfDigits(Math.abs(n - i));
// Evaluating the value on the right
// side of the given number
let valueOnRight = (n + i) +
sumOfDigits(n + i);
// Checking the condition of equality
// on both sides of the given number N
// and updating the answer vector
if (valueOnRight == n)
answer[pos++] = (n + i);
if (valueOnLeft == n)
answer[pos++] = Math.abs(n - i);
}
if (pos == 0)
document.write(-1);
else
for(let i = 0; i < pos; i++)
document.write("X = " + answer[i] + "<br/>");
}
// Driver Code
let N = 100000001;
compute(N);
// This code is contributed by susmitakundugoaldanga
</script>
Producción:
X = 100000000 X = 99999937
La complejidad máxima de este enfoque puede ser 
donde len es el número de dígitos en el número max(len) = 9. Por lo tanto, casi se puede decir que la complejidad es 