aboutsummaryrefslogtreecommitdiff
path: root/check_digit_eq_str_op2.c
blob: 6b54de10822192afa2dbf64ceac633b3eaa0b087 (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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// 3463. Check If Digits Are Equal in String After Operations II
#include "leetcode.h"

/*
 * you are given a string 's' consisting of digits. perform the following
 * operation repeatedly until the string has exactly two digits: for each pair
 * of consecutive digits in 's', starting from the first digit, calculate a new
 * digit as the sum of the two digits modulo 10. replace 's' with the sequence
 * of newly calculated digits, maintaining the order in which they are computed.
 * return 'true' if the final two digits in 's' are the same; otherwise return
 * false.
 */

static inline int gcd(int a, int b) {
  while (b) {
    a ^= b ^= a ^= b;
    b %= a;
  }
  return a;
}

static inline void fac(int a, int mod, int *r, int *cnt) {
  int num = 0;
  while (a && !(a % mod)) {
    num++;
    a /= mod;
  }
  *r = a % mod;
  *cnt = num;
}

static inline int inv_mod(int a, int mod) {
  for (int i = 1; i < mod; i++)
    if ((a * i) % mod == 1)
      return i;
  return 0;
}

static bool test(int mod, char *s) {
  int n = strlen(s), res = 0, r = 1, c = 0;
  for (int i = 0; i < n - 1; i++) {
    if (!c) {
      res = (res + r * ((s[i] - '0') - (s[i + 1] - '0'))) % mod;
      if (res < 0)
        res += mod;
    }
    int rr, cc;
    fac(n - 2 - i, mod, &rr, &cc);
    r = (r * rr) % mod;
    c += cc;
    fac(i + 1, mod, &rr, &cc);
    r = (r * inv_mod(rr, mod)) % mod;
    c -= cc;
  }
  return !(res % mod);
}

bool hasSameDigits(char *s) { return test(2, s) && test(5, s); }

int main() {
  char *s1 = "3902", *s2 = "34789";
  printf("%d\n", hasSameDigits(s1)); // expect: 1
  printf("%d\n", hasSameDigits(s2)); // expect: 0
}