Given a positive integer N, the task is to find the smallest positive number made up of distinct digits having sum of its digits equal to N. If no such number exists, print “-1”.
Examples:
Input: N = 11
Output: 29
Explanation: The sum of the digits = 2 + 9 = 11 ( = N).Input: N = 46
Output: -1
Approach: The idea is based on the following observations:
- If N < 10: Required answer is N itself.
- If N > 45: Required answer is -1 as the smallest number that can be made using non-repeating digits is 123456789, whose sum of digits is 45.
- Otherwise: The answer can be obtained based on the following pattern.
Consider the following examples, to understand the pattern,
For N = 10: The output is 19.
For N = 11: The output is 29.
For N = 12: The output is 39.
For N = 13: The output is 49.
…
For N = 21: The output is 489.
For N = 22: The output is 589.
For N = 23: The output is 689.On observing the above results, it is clear that the answer contains digits in decreasing order having a difference of 1 starting from one’s digit until the digit sum is less than N.
Follow the steps below to solve the problem:
- If the given number is less than 10, then print the number itself.
- If the given number is greater than 45, then print “-1”.
- Otherwise, perform the following steps:
- Initialize a string res to store the required answer and initialize a variable, say digit, as 9.
- Iterate a loop until N ? digit and perform the following steps:
- Push digit at the starting of res.
- Decrement N by digit.
- Decrement digit by 1.
- If the value of N is found to be greater than 0, then push the character at the starting of res.
- After completing the above steps, print the value of res as the answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find smallest positive// number made up of non-repeating digits// whose sum of its digits is equal to nvoid result(int n){ if (n > 45) { // No such number exists cout << -1; return; } // Stores the required answer string res; // Store the digit at unit's place int digit = 9; // Iterate until n > digit while (n > digit) { // Push digit at the start of res res = char('0' + digit) + res; // Decrement n by digit n -= digit; // Decrement digit by 1 digit -= 1; } if (n > 0) { // Push the remaining number // as the starting digit res = char('0' + n) + res; } // Print the required number cout << res;}// Driver Codeint main(){ int N = 19; // Function Call result(N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find smallest positive// number made up of non-repeating digits// whose sum of its digits is equal to nstatic void result(int n){ if (n > 45) { // No such number exists System.out.print(-1); return; } // Stores the required answer String res=""; // Store the digit at unit's place int digit = 9; // Iterate until n > digit while (n > digit) { // Push digit at the start of res res = (char)('0' + digit) + res; // Decrement n by digit n -= digit; // Decrement digit by 1 digit -= 1; } if (n > 0) { // Push the remaining number // as the starting digit res = (char)('0' + n) + res; } // Print the required number System.out.print(res);}// Driver Codepublic static void main(String[] args){ int N = 19; // Function Call result(N);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approach# Function to find smallest positive# number made up of non-repeating digits# whose sum of its digits is equal to ndef result(n): if (n > 45): # No such number exists print(-1, end = "") return # Stores the required answer res = "" # Store the digit at unit's place digit = 9 # Iterate until n > digit while (n > digit): # Push digit at the start of res res = str(digit) + res # Decrement n by digit n -= digit # Decrement digit by 1 digit -= 1 if (n > 0): # Push the remaining number # as the starting digit res = str(n) + res # Print the required number print(res)# Driver Codeif __name__ == '__main__': N = 19 # Function Call result(N)# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;class GFG{ // Function to find smallest positive// number made up of non-repeating digits// whose sum of its digits is equal to nstatic void result(int n){ if (n > 45) { // No such number exists Console.Write(-1); return; } // Stores the required answer string res = ""; // Store the digit at unit's place int digit = 9; // Iterate until n > digit while (n > digit) { // Push digit at the start of res res = (char)('0' + digit) + res; // Decrement n by digit n -= digit; // Decrement digit by 1 digit -= 1; } if (n > 0) { // Push the remaining number // as the starting digit res = (char)('0' + n) + res; } // Print the required number Console.Write(res);} // Driver Codepublic static void Main(){ int N = 19; // Function Call result(N);}}// This code is contributed by sanjoy_62 |
Javascript
<script>// Javascript program for the above approach// Function to find smallest positive// number made up of non-repeating digits// whose sum of its digits is equal to nfunction result(n){ if (n > 45) { // No such number exists document.write(-1); } // Stores the required answer var res = ""; // Store the digit at unit's place var digit = 9; // Iterate until n > digit while (n > digit) { // Push digit at the start of res res = String.fromCharCode(48 + digit) + res; // Decrement n by digit n -= digit; // Decrement digit by 1 digit -= 1; } if (n > 0) { // Push the remaining number // as the starting digit res = String.fromCharCode(48 + n) + res; } // Print the required number document.write(res);}// Driver Codevar N = 19;// Function Callresult(N);</script> |
Output:
289
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
