aboutsummaryrefslogtreecommitdiff
path: root/count_good_numbers.c
blob: 639c723f312ff67ef72d8c4da80e9ad7841930bd (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 1922. Count Good Numbers
#include "leetcode.h"

/*
 * a digit string is good if the digits (0-indexed) at even indices are even and
 * the digits at odd indices are prime (2,3,5,or 7). for example 2582 is good
 * because the digits 2 and 8 at even positions are even and the digits 5 and 2
 * at odd positions are prime. however, 3245 is not good because 3 is at an even
 * index, but is not even. given an integer 'n', return the total number of good
 * digit strings of length 'n'. since the answer may be large, return it modulo
 * 1e9+7. a digit string is a string consisting of digits 0 through 9 that may
 * contain leading zeros.
 */

static int mod = 1e9 + 7;

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 a = mod_exp(5, (n + 1) / 2);
  long long b = mod_exp(4, n / 2);
  return (int)((a * b) % mod);
}

int main() {
  printf("%d\n", countGoodNumbers(1));  // expect: 5
  printf("%d\n", countGoodNumbers(4));  // expect: 400
  printf("%d\n", countGoodNumbers(50)); // expect: 564908303
}