aboutsummaryrefslogtreecommitdiff
path: root/count_good_numbers.c
blob: 86432c43e3e680cf6097d0c8e57e720c8504553d (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
// 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.
 */

const 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);
}

int countGoodNumbers(long long n) {
  long long odd = n / 2, even = n - odd;
  return _pow(20, odd) * ((n % 2) ? 5 : 1) % MOD;
}

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