Given a positive number N. We need to find number(s) such that sum of digits of those numbers to themselves is equal to N. If no such number is possible print -1. Here N ![\in [1, 1000000000]](https://neveropen.co.za/wp-content/uploads/2023/10/neveropen_quicklatex.com-a1185ce5f0b3708f280fa7f2ad459cc7_l3.png "Rendered by QuickLaTeX.com")
Examples:
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
Method 1 : (Naive Approach)
We have already discussed the approach here. The approach might not work for N as large as 
.
Method 2 : (Efficient)
It is a fact that for a number X < = 1000000000, the sum of digits never exceeds 100. Using this piece of information, we can iterate over all possibilities in the range 0 to 100 on both the sides of the number and check if the number X is equal to N – sum of digits of X. All the possibilities will be covered in this range.
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 xint 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 accordinglyvoid 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 Functionint 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) = Nimport java.util.*;import java.lang.*;import java.io.*;class neveropen { // 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) = Nusing 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 xfunction 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 Codelet N = 100000001;compute(N);// This code is contributed by susmitakundugoaldanga</script> |
Output:
X = 100000000 X = 99999937
The maximum complexity of this approach can be 
where len is the number of digits in the number max(len) = 9. Thus the complexity can almost be said to be 
Approach#2: Using binary search
this approach to solve this problem is to use binary search. We can start with the middle value between 1 and N, and then we can check if the sum of this number and its digit sum is equal to N. If it is not, we can use binary search to find a number that satisfies the condition.
Algorithm
1. Define a function “find_number_with_digit_sum” that takes an integer “N” as input.
2. Define a function “check_number_with_digit_sum” that takes a number “X” and an integer “N” as input, and checks if the sum of “X” and its digit sum is equal to “N”. Return True if the condition is satisfied, False otherwise.
3. Set “low” to 1 and “high” to N.
4. While “low” is less than or equal to “high”:
a. Calculate the middle value “mid” between “low” and “high”.
b. If “check_number_with_digit_sum(mid, N)” returns True, return “mid”.
c. If “mid” plus its digit sum is less than “N”, set “low” to “mid” + 1.
d. Otherwise, set “high” to “mid” – 1.
5. If no number was found, return -1.
C++
#include <iostream>using namespace std;// Function to calculate the sum of the digits of a numberint digit_sum(int n) { int sum = 0; while (n > 0) { sum += n % 10; // Add the last digit of n to the sum n /= 10; // Remove the last digit of n } return sum;}// Function to check if a number X has the desired digit sum Nbool check_number_with_digit_sum(int X, int N) { return X + digit_sum(X) == N; // Return true if X + its digit sum equals N}// Function to find the smallest number that has the desired digit sum Nint find_number_with_digit_sum(int N) { int low = 1, high = N; // Set the search range to [1, N] while (low <= high) { // Perform binary search until the range is empty int mid = (low + high) / 2; // Calculate the midpoint of the range if (check_number_with_digit_sum(mid, N)) { // Check if the midpoint has the desired digit sum return mid; // Return the midpoint if it does } else if (mid + digit_sum(mid) < N) { // If the midpoint has a digit sum less than N low = mid + 1; // Search the upper half of the range } else { // If the midpoint has a digit sum greater than or equal to N high = mid - 1; // Search the lower half of the range } } return -1; // If no number with the desired digit sum is found, return -1}int main() { int N = 100000001; // Choose a desired digit sum cout << find_number_with_digit_sum(N) << endl; // Find the smallest number with that digit sum and output it return 0;} |
Python3
def digit_sum(n): sum = 0 while n > 0: sum += n % 10 n //= 10 return sumdef check_number_with_digit_sum(X, N): return X + digit_sum(X) == Ndef find_number_with_digit_sum(N): low, high = 1, N while low <= high: mid = (low + high) // 2 if check_number_with_digit_sum(mid, N): return mid elif mid + digit_sum(mid) < N: low = mid + 1 else: high = mid - 1 return -1N = 100000001print(find_number_with_digit_sum(N)) |
Output
99999937
Time Complexity: O(log10(N) * log10(X)), where X is the answer.
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
