Count Good Numbers LeetCode solution in C++

1
// Approach :-> This is question of combination
2
// if n as large no....
3
// 0 1 2 3 4 5 6 7 8 9 10 11 . . . . . n
4
// 5 * 4 * 5 * 4 * 5 * 4 * 5 * 4 * 5 * 4 * 5 * 4 . . . . . n/4 times of 4 and
5
// n/4 times of 5;
6
// so calculate 5*4 = 20 -------> 20 * 20 * 20 * . . . . .. n/2 times
7
// so calcultae pow(20,n/2)
8
// if n is even return pow(20,n/2)
9
// if n is odd return 5*pow(20,n/2) beacause if n is odd then one 5 is left out
10
// we can easily calculate pow(x,y) in log(y) times
11
// durign calculation take care about mod
12
class Solution {
13
 public:
14
  int mod = 1000000007;
15
  long long solve(long long val,
16
                  long long pow) { // calculatin pow in log(n) time
17
    if (pow == 0) return 1;
18

19
    if (pow % 2 == 0) {
20
      return solve((val * val) % mod, pow / 2) % mod;
21
    } else
22
      return (val * solve((val * val) % mod, pow / 2)) % mod;
23
  }
24
  int countGoodNumbers(long long n) {
25
    // even means 5 options
26
    // odd means 4 option
27

28
    long long pow = n / 2; // calculate no of times 5*4 means 20 occurs
29

30
    long long ans = solve(20, pow); // calculate power(20,pow)
31

32
    if (n % 2 == 0) { // if n is even then 5 and 4 occur same no of time n/2
33
      return ans;
34
    }
35
    return ((5 * ans) % mod); // if n is odd then 5 occurs n/2+1 times means one extra times
36
                              // so return ans*5 and don't forgot to mod
37
  }
38
};