Problem

A number is considered perfect if its digits sum up to exactly 10.

Given a positive integer n, return the n-th perfect number.

Examples

Example 1:

1
2

Input: n = 1
Output: 19

Example 2:

1
2

Input: n = 2
Output: 28

Solution

Method 1 - Brute Force

Keep on generating the numbers with sum of digits as 10, and when count is n, return the number.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {

	public int getNthPerfectNumber(int n) {
		int count = 0;
		int num = 19; // first perfect number is 19
		while (count < n) {
			if (isPerfect(num)) {
				count++;
			}

			num++;
		}

		return num - 1;
	}

	public boolean isPerfect(int num) {
		int sum = 0;

		while (num > 0) {
			sum += num % 10;
			num /= 10;
		}

		return sum == 10;
	}

}

Complexity

  • ⏰ Time complexity: O(n * log_10(n))
  • 🧺 Space complexity: O(1)

Method 2 - Slightly more efficient

Lets look at some numbers in series - 19, 28, 37, 46… and so on. It becomes apparent that they differ by multiple of 9. But, not every number in this sequence adds up to 10—the number 100 being a case in point. Therefore, rather than evaluating each number individually, we begin the sequence at 19 and increase in steps of 9.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {

	public int getNthPerfectNumber(int n) {
		int count = 0;
		int num = 19; // first perfect number is 19
		while (count < n) {
			if (isPerfect(num)) {
				count++;
			}

			num += 9;
		}

		return num - 9;
	}

	public boolean isPerfect(int num) {
		int sum = 0;

		while (num > 0) {
			sum += num % 10;
			num /= 10;
		}

		return sum == 10;
	}

}

Complexity

  • ⏰ Time complexity: O(n * log_10(n))
  • 🧺 Space complexity: O(1)