aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--check_digit_eq_str_op2.c64
-rw-r--r--check_digit_eq_str_op2.py45
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"))