Skip to content

2847. Smallest Number With Given Digit Product 👍

  • Time: $O(\log n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
 public:
  string smallestNumber(long long n) {
    if (n <= 9)
      return to_string(n);

    string ans;

    for (int divisor = 9; divisor > 1; --divisor)
      while (n % divisor == 0) {
        ans += to_string(divisor);
        n /= divisor;
      }

    return n > 1 ? "-1" : string{ans.rbegin(), ans.rend()};
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
  public String smallestNumber(long n) {
    if (n <= 9)
      return Long.toString(n);

    StringBuilder ans = new StringBuilder();

    for (int divisor = 9; divisor > 1; --divisor)
      while (n % divisor == 0) {
        ans.append(Integer.toString(divisor));
        n /= divisor;
      }

    return n > 1 ? "-1" : ans.reverse().toString();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
  def smallestNumber(self, n: int) -> str:
    if n <= 9:
      return str(n)

    ans = []

    for divisor in range(9, 1, -1):
      while n % divisor == 0:
        ans.append(str(divisor))
        n //= divisor

    return '-1' if n > 1 else ''.join(reversed(ans))