aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-04-12 21:43:56 -0600
committerJack Sangdahl <[email protected]>2025-04-12 21:43:56 -0600
commite5d733871eda3cb090b121b0d1a6c904fb6bb71c (patch)
treed97e9f567d8c84750113974d0f0fc7fd3ccf94a2
parente5068470c3758c57f1b59c7dde1d32670a5a12c9 (diff)
downloadleetcode-e5d733871eda3cb090b121b0d1a6c904fb6bb71c.tar.gz
leetcode-e5d733871eda3cb090b121b0d1a6c904fb6bb71c.zip
1922. count good numbers
-rw-r--r--count_good_numbers.c21
-rw-r--r--count_good_numbers.py19
2 files changed, 29 insertions, 11 deletions
diff --git a/count_good_numbers.c b/count_good_numbers.c
index 86432c4..639c723 100644
--- a/count_good_numbers.c
+++ b/count_good_numbers.c
@@ -12,17 +12,24 @@
* contain leading zeros.
*/
-const int MOD = 1e9 + 7;
+static int mod = 1e9 + 7;
-long long _pow(long long a, long long b) {
- if (!b)
- return 1;
- return b % 2 ? a * _pow(a, b - 1) % MOD : _pow((a * a) % MOD, b / 2);
+long long mod_exp(long long n, long long e) {
+ int res = 1;
+ n %= mod;
+ while (e > 0) {
+ if (e & 1)
+ res = res * n % mod;
+ e >>= 1;
+ n = n * n % mod;
+ }
+ return res;
}
int countGoodNumbers(long long n) {
- long long odd = n / 2, even = n - odd;
- return _pow(20, odd) * ((n % 2) ? 5 : 1) % MOD;
+ long long a = mod_exp(5, (n + 1) / 2);
+ long long b = mod_exp(4, n / 2);
+ return (int)((a * b) % mod);
}
int main() {
diff --git a/count_good_numbers.py b/count_good_numbers.py
index 93455c9..17243a6 100644
--- a/count_good_numbers.py
+++ b/count_good_numbers.py
@@ -13,15 +13,26 @@ contain leading zeros.
class Solution(object):
+ mod = 10**9 + 7
+
+ def mod_exp(self, n, e):
+ res = 1
+ n %= self.mod
+ while e > 0:
+ if e % 2 == 1:
+ res = (res * n) % self.mod
+ n = (n * n) % self.mod
+ e //= 2
+ return res
+
def countGoodNumbers(self, n):
"""
:type n: int
:rtype: int
"""
- cnt, x = 5 ** (n % 2), 20
- for _ in range(n // 2):
- cnt = cnt * x % (10**9 + 7)
- return cnt
+ a = self.mod_exp(5, (n + 1) // 2)
+ b = self.mod_exp(4, n // 2)
+ return (a * b) % self.mod
if __name__ == "__main__":