Do you think IIT Guwahati certified course can help you in your career?
Introduction
Binary search is an important topic when it comes to technical interviews. It’s usually an easy topic, but when it’s clubbed with other topics such as recursion and memoization, the difficulty level increases for sure. But we are here to make your life easier, and in this blog, we will see the question Nth Number. We recommend you to first try the question on your own at Coding Ninjas Studio and then return to this blog if you feel stuck.
Understanding the Problem
We have been given a number ‘N,’ and we have to return the Nth number from a series of numbers in which every number has a digit sum of 10. (For example, 19, 1 + 9=10).
Let’s understand this further by the following example.
N = 4
Now, the first four numbers having a sum of digits equal to 10 are 19, 28, 37, and 46. Therefore, our answer would be 46.
Brute Force
Brute force is very straightforward. We will start iterating from 1 and check for each number whether the sum of its digits is 10. If it is, then we will increment the ‘COUNTER’ (variable to keep count). When the counter becomes equal to ‘N’, we will return that number.
Below is the code for your reference.
#include <iostream>
using namespace std;
// Function to calculate sum of digits of a number.
int sumOfDigits(long long number)
{
int sum = 0;
while (number > 0)
{
sum += (int)(number % 10);
number /= 10;
}
return sum;
}
long long nthNumberWithSum10(long long n)
{
long number = 1;
int counter = 0;
while (true)
{
// If the sum is equal to 10 then increase the counter.
if (sumOfDigits(number) == 10)
{
counter++;
}
// If the Nth number has been found.
if (counter == n)
{
break;
}
number++;
}
return number;
}
int main()
{
long long n;
// Taking user input.
cin >> n;
// Calling the function and printing the answer.
cout << nthNumberWithSum10(n);
}
You can also try this code with Online C++ Compiler
O(M), where ‘M’ is the Nth Number which has a sum of digits equal to 10. As even in the worst case, we will be iterating from 1 to ‘M’.
Space Complexity
O(1), As we are not using any extra space.
As the value of M can be very large(long long), the above solution will cause TLE, and thus we have to look for an alternative solution.
Binary Search
This is different from our traditional binary search. First, we will maintain a variable, ‘ANS’ initialized with LONG_MAX. We will perform a binary search with start, ST = 1 to END = maximum possible number (LONG_MAX). At every step, we will calculate the ‘MID’ (mid-value in binary search) and check if the count of numbers from 1 to ‘MID’ with the sum of digits 10 is ‘N’, if it is ‘N’, we will update our answer, i.e., min(ANS, MID) ’ else we will check if the count is greater than ‘N’ or less than ‘N’ and change the ‘ST’ and ‘END’ of binary search respectively:
ST = ST and END = MID - 1, if the count is greater than ‘N’.
ST = MID + 1 and END = END, if the count is less than ‘N’.
To count all numbers less than a given number, M’ with digit sum 10. We iterate the number by replacing its digits starting from 1 until it becomes equal to 'M'. We will also increase the count if this number satisfies the property of having a digit sum equal to 10. To iterate the number, begin with the most significant digit and set all possible digits there before calling for the next most significant bit.
Let's say M = 586.
Now, with the most significant digit = 5, we'll set a variable, TIGHT = 1 that will notify us that the current digit's limit equals the value of that bit in ‘M’, allowing us to iterate over all possible values. As a result, we can choose the most significant digits as 0,1,2,3, and we will update the limit if we choose 5. We can iterate on the next bits in the same way.
Below is the code for the above approach.
#include<iostream>
#include <vector>
#include <climits>
#include<string>
using namespace std;
// Function to count the number of integers smaller than or equals to ‘MID’ with digit sum = 10
long long countNumbersWithSum10(int pos, bool tight, int sum, string &s) {
// Base Case.
if (sum > 10 || pos == s.length()) {
return sum == 10;
}
long long ans = 0;
// The maximum limit of digit.
int en = 9;
// ‘TIGHT = true’ shows that we are at the first digit in the given number.
if (tight) {
en = s[pos] - '0';
}
// Using recursion for calling the function for next digits.
for (int i = 0; i <= en; i++) {
ans += countNumbersWithSum10(pos + 1, tight & (i == en), (sum + i), s);
}
return ans;
}
// Function to find the Nth number with digit sum as 10.
long long nthNumberWithSum10(long long n) {
// Setting boundaries of binary search.
long long st = 0, end = LLONG_MAX;
long long ans = LLONG_MAX;
while (st <= end) {
long long mid = ((end - st) / 2) + st;
string s = to_string(mid);
// Count number of integers smaller than or equal to ‘MID’ with digit sum = 10.
long long count = countNumbersWithSum10(0, true, 0, s);
/*If it’s greater than or equal to ‘N’, then it could be a possible answer.*/
if (count >= n) {
ans = min(ans, mid);
end = mid - 1;
} else {
st = mid + 1;
}
}
return ans;
}
int main() {
long long n;
// Taking input.
cin >> n;
// Printing the answer.
cout << nthNumberWithSum10(n);
}
You can also try this code with Online C++ Compiler
O((10 ^ LEN) * Log(MAX)), where ‘MAX’ is the maximum possible value for the Nth Number and ‘LEN’ is the length of ‘MAX,’ i.e., number of digits in the ‘MAX’ number.
As even in the worst case, we will be checking for each possible digit (0 - 9) for an index in the ‘MAX’ and recursively solving the problem for the next digits.
Space Complexity
O(LEN), where ‘LEN’ is the maximum possible length for the Nth number. As in the worst case, we will be storing the number in an array(its digits).
Binary Search Plus Memoization
Even after applying binary search, we can clearly see that we are doing calculations repetitively. For example, let’s say we have calculated the count of numbers with a sum of digits equal to 10 (from 1 to 50). In this case, ‘MID’ was 50, and now we notice that the count is greater than ‘N’, then what will we do? We will reduce the value of ‘END’ and will again calculate the count from (1 to 48) as the new ‘END’ would be 49 (‘MID - 1’). Thus we will be again calculating the count for 1 to 49, which we had already calculated when we were calculating the count in the range of 1 to 50. Thus we will use memoization and will create a ‘DP’ array that will store the answers for these subproblems and avoid re-calculation.
You will get a better understanding of the following code.
#include<iostream>
#include <vector>
#include <climits>
#include<string>
using namespace std;
/* Function will count the number of integers smaller than or equals to mid with digit sum = 10 */
long long countNumbersWithSum10(int pos, int tight, int sum, string & s, vector < vector < vector < long long >>> & dp) {
// Base case.
if (sum > 10 || pos == s.size()) {
return sum == 10;
}
// Memoization condition.
long long &ans = dp[pos][tight][sum];
if (ans != -1) {
return ans;
}
ans = 0;
// The maximum limit of digit.
int en = 9;
// 'TIGHT = true' shows that we are at the first digit in the given number.
if (tight) {
en = s[pos] - '0';
}
// Using recursion for calling the function for next digits.
for (int i = 0; i <= en; i++) {
ans += countNumbersWithSum10(pos + 1, tight & (i == en), (sum + i), s,dp);
}
return ans;
}
// Final answer would be returned by this function.
long long nthNumberWithSum10(long long n) {
// Setting boundaries of binary search.
long long st = 0, end = LLONG_MAX;
long long ans = LLONG_MAX;
while (st <= end) {
long long mid = ((end - st) / 2) + st;
vector < vector < vector < long long >>> dp(20, vector < vector < long long >> (2, vector < long long > (11, -1)));
string s = to_string(mid);
// Count number of integers smaller than or equal to 'MID' with digit sum = 10.
long long count = countNumbersWithSum10(0, true, 0, s,dp);
/*If it's greater than or equal to 'N', then it could be a possible answer.*/
if (count >= n) {
ans = min(ans, mid);
end = mid - 1;
} else {
st = mid + 1;
}
}
return ans;
}
int main() {
long long n;
// Taking input.
cin >> n;
// Printing the answer.
cout << nthNumberWithSum10(n);
}
You can also try this code with Online C++ Compiler
O((10 * LEN) * log(MAX)), where ‘MAX’ is the maximum possible value for the Nth Number and ‘LEN’ is the length of ‘MAX’ number, i.e., number of digits in the ‘MAX’ number.
As even in the worst case, we will be calculating all entries in the DP matrix of dimension LEN * 10 * 2.
Space Complexity
O(LEN * 10), where ‘LEN’ is the maximum possible length for the Nth number i.e., the number of digits in the ‘MAX’ number.
Even in the worst case, we will be storing the number in an array of size LEN * K.
To understand it better and know proper code implementation, you should watch this video as this problem was asked in many companies.
Key Takeaways
We learned to solve the problem Nth number by every method possible, i.e., from brute force to the most efficient one (binary search and memoization). Now you must be on cloud nine after learning this new and amazing technique, But this is not all, and you should not stop here, so head over to our practice platform Coding Ninjas Studio to practice top problems and many more. Till then, Happy Coding!
24+ registered 
