Skip to content

← leetcode

Count Good Numbers

· Medium

LeetCode problem 1922

The solution is quite straightforward; very quickly, running through a few cases, you realize that there is a simple pattern:

cases:
1: 5
2: 4*5
3: 5*4*5
4: 4*5*4*5
5: 5*4*5*4*5
6: etc.

However, iterating from 1 to 10^15 would take an extremely long time, so iterating through the bits of n seemed to make more logical sense. The logic is:

  • if the bit at position i is 1, then multiply ans by 20^i
  • if the bit at position i is 0, then continue.

The main problem is integer overflow, but that can be negated with a simple long long.

code

class Solution {
public:
    int countGoodNumbers(long long n) {
        long long ans = 1;
        long long curr_multiplier = 20;
        if (n % 2 == 1) {
            ans = 5;
        }
        n >>= 1;
        for (long long i = n; i > 0; i >>= 1) {
            if (i%2 == 1) {
                ans = (ans * curr_multiplier) % (long long)(1e9+7);
            }
            curr_multiplier = (curr_multiplier * curr_multiplier) % (long long)(1e9 + 7);
        }
        return (int)ans;
    }
};

complexity

  • Time: O(log n)
  • Space: O(1)