Problem

Let’s define a “sevenish” number to be one which is either a power of 7, or the sum of unique powers of 7. The first few sevenish numbers are 1, 7, 8, 49, and so on. Create an algorithm to find the nth sevenish number.

Examples

Example 1

1
2
3

Input: n = 1
Output: 1
Explanation: The first sevenish number is the first power of 7, 7^0 = 1.

Example 2

1
2
3

Input: n = 4
Output: 49
Explanation: The fourth sevenish number is 49, as it is a direct power of 7 (7^2).

Example 3

1
2
3

Input: n = 6
Output: 56
Explanation: The six sevenish number is 56 (which is 7^0 + 7^3, i.e., 1 + 49).

Solution

Method 1 - Iteration

The sequence of sevenish numbers can be systematically constructed using powers of 7 and sums of unique powers. By iterating through combinations of powers of 7, we can populate a list of sevenish numbers in ascending order until the nth number is found. Each new “sevenish” number can be derived by adding existing sevenish numbers to the next power of 7.

Approach

The approach will follow these steps:

  1. Start with the smallest sevenish number, which is 7^0 = 1.
  2. Keep track of a list of sevenish numbers.
  3. For any new power of 7, generate additional sevenish numbers by adding it to the existing ones.
  4. Stop once we have n sevenish numbers.

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

public class Solution {

    public int nthSevenishNumber(int n) {
        List<Integer> sevenishNumbers = new ArrayList<>();
        int powerOf7 = 1;

        while (sevenishNumbers.size() < n) {
            // Create new numbers using the current power of 7
            List<Integer> newNumbers = new ArrayList<>();
            newNumbers.add(powerOf7);

            // Add sums of the current power with all previous numbers
            for (int num : sevenishNumbers) {
                newNumbers.add(num + powerOf7);
            }

            // Extend the sevenish list
            sevenishNumbers.addAll(newNumbers);

            // Update power of 7
            powerOf7 *= 7;
        }

        return sevenishNumbers.get(n - 1);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def nth_sevenish_number(self, n: int) -> int:
        # Generate powers of 7 (ascending order)
        sevenish_numbers = []
        power_of_7 = 1

        while len(sevenish_numbers) < n:
            # Add current power of 7
            new_numbers = [power_of_7]
            
            # Add sums of the current power with all previous numbers
            for num in sevenish_numbers:
                new_numbers.append(num + power_of_7)

            # Extend sevenish list and keep track of the nth one
            sevenish_numbers.extend(new_numbers)
            power_of_7 *= 7  # Move to the next power of 7

        return sevenish_numbers[n - 1]

Complexity

  • ⏰ Time complexity: O(NNNXXXNNN)
  • 🧺 Space complexity: O(NNNXXX)