Medium
Smallest Greater Multiple Made of Two Digits — C++
Full explanation · Time O(1) · Space O(1)
// Time: sum(O(l * 2^l) for l in range(1, 11)) = O(20 * 2^10) = O(1)
// Space: O(1)
class Solution {
public:
int findInteger(int k, int digit1, int digit2) {
static const int MAX_NUM_OF_DIGITS = 10;
if (digit1 < digit2) {
swap(digit1, digit2);
}
for (int l = 1, total = 2; l <= MAX_NUM_OF_DIGITS; ++l, total <<= 1) {
for (int mask = 0; mask < total; ++mask) {
int64_t curr = 0;
for (int bit = total >> 1; bit; bit >>= 1) {
curr = curr * 10 + ((mask & bit) ? digit1 : digit2);
}
if (k < curr && curr <= numeric_limits<int>::max() && curr % k == 0) {
return curr;
}
}
}
return -1;
}
};