diff options
Diffstat (limited to 'check_digit_eq_str_op2.c')
-rw-r--r-- | check_digit_eq_str_op2.c | 64 |
1 files changed, 64 insertions, 0 deletions
diff --git a/check_digit_eq_str_op2.c b/check_digit_eq_str_op2.c new file mode 100644 index 0000000..6b54de1 --- /dev/null +++ b/check_digit_eq_str_op2.c @@ -0,0 +1,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 +} |