diff options
-rw-r--r-- | check_digit_eq_str_op2.c | 64 | ||||
-rw-r--r-- | check_digit_eq_str_op2.py | 45 |
2 files changed, 109 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 +} diff --git a/check_digit_eq_str_op2.py b/check_digit_eq_str_op2.py new file mode 100644 index 0000000..cfa1f53 --- /dev/null +++ b/check_digit_eq_str_op2.py @@ -0,0 +1,45 @@ +# 3463. Check If Digits Are Equal in String After Operations II +""" +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. +""" + + +class Solution(object): + def hasSameDigits(self, s): + """ + :type s: str + :rtype: bool + """ + + def fac(a, mod): + cnt = 0 + while a > 0 and a % mod == 0: + cnt += 1 + a //= mod + return a % mod, cnt + + def test(mod): + n, res, r, c = len(s), 0, 1, 0 + for i in range(n - 1): + if c == 0: + res += r * (int(s[i]) - int(s[i + 1])) + rr, cc = fac(n - 2 - i, mod) + r = r * rr % mod + c += cc + rr, cc = fac(i + 1, mod) + r = r * pow(rr, mod - 2, mod) % mod + return res % mod == 0 + + return test(2) and test(5) + + +if __name__ == "__main__": + obj = Solution() + print(obj.hasSameDigits(s="3902")) + print(obj.hasSameDigits(s="34789")) |