# Smallest positive number made up of non-repeating digits whose sum of digits is N

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:**

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the **Essential Maths for CP Course** at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

Input:N = 11Output:29Explanation:The sum of the digits = 2 + 9 = 11 ( = N).

Input:N = 46Output:-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**.

- Push
- 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.

- Initialize a string

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 n` `void` `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 Code` `int` `main()` `{` ` ` `int` `N = 19;` ` ` `// Function Call` ` ` `result(N);` ` ` `return` `0;` `}` |

## Java

`// Java program for the above approach` `import` `java.util.*;` `class` `GFG` `{` `// Function to find smallest positive` `// number made up of non-repeating digits` `// whose sum of its digits is equal to n` `static` `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 Code` `public` `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 n` `def` `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 Code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` ` ` `N ` `=` `19` ` ` `# Function Call` ` ` `result(N)` `# This code is contributed by mohit kumar 29` |

## C#

`// C# program for the above approach` `using` `System;` `class` `GFG` `{` ` ` `// Function to find smallest positive` `// number made up of non-repeating digits` `// whose sum of its digits is equal to n` `static` `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 Code` `public` `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 n` `function` `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 Code` `var` `N = 19;` `// Function Call` `result(N);` `</script>` |

**Output:**

289

**Time Complexity:** O(N)**Auxiliary Space:** O(N)