Smallest Divisible Digit Product I – C++ Solution

Problem Description

Welcome to the world of numbers, where we often find ourselves in a pickle trying to figure out the smallest number that meets certain criteria. The problem at hand, “Smallest Divisible Digit Product I,” is like trying to find the last slice of pizza at a party—everyone wants it, but only one can have it!

In this problem, you are given two integers, n and t. Your mission, should you choose to accept it, is to find the smallest integer greater than or equal to n such that the product of its digits is divisible by t. If you can’t find such a number, well, let’s just say you might want to rethink your life choices (or throw an exception, as the code suggests).

Code Solution


class Solution {
 public:
  int smallestNumber(int n, int t) {
    for (int num = n; num < n + 10; ++num)
      if (getDigitProd(num) % t == 0)
        return num;
    throw;
  }

 private:
  int getDigitProd(int num) {
    int digitProd = 1;
    while (num > 0) {
      digitProd *= num % 10;
      num /= 10;
    }
    return digitProd;
  }
};

Approach

The approach here is straightforward yet effective. The code iterates through numbers starting from n up to n + 10. For each number, it calculates the product of its digits using the getDigitProd function. If the product is divisible by t, it returns that number. If no such number is found in the range, it throws an exception. Simple, right? Just like finding a needle in a haystack, but with a much smaller haystack!

Time and Space Complexity

Time Complexity: O(1) – The loop runs a fixed number of times (10 iterations), making it constant time.
Space Complexity: O(1) – The space used does not depend on the input size; it remains constant.

Real-World Example

Imagine you’re at a bakery, and you want to buy a cake that has a specific number of cherries on top. You start counting the cakes, but you only want those with a cherry count that is divisible by your lucky number, t. You check each cake until you find the perfect one. This is essentially what the code does—searching for the smallest number (or cake) that meets the criteria!