Input: s ="34789"Output: falseExplanation:
* Initially,`s = "34789"`.* After the first operation,`s = "7157"`.* After the second operation,`s = "862"`.* After the third operation,`s = "48"`.* Since `'4' != '8'`, the output is`false`.
After repeatedly applying the operation, the final two digits can be expressed as a linear combination of the original digits, with coefficients determined by binomial coefficients modulo 10. We can precompute these coefficients and use them to compute the final two digits efficiently, even for large strings.
classSolution {
public:bool isEqual(string s) {
int n = s.size();
vector<int> arr(n);
for (int i =0; i < n; ++i) arr[i] = s[i] -'0';
vector<int> C(n, 1);
for (int i =1; i < n-1; ++i) C[i] = (1LL* C[i-1] * (n-2-i+1) / i) %10;
int l =0, r =0;
for (int i =0; i < n; ++i) {
int c1 = (i <= n-2) ? C[i] :0;
int c2 = (i-1>=0&& i-1<= n-2) ? C[i-1] :0;
l = (l + c1 * arr[i]) %10;
r = (r + c2 * arr[i]) %10;
}
return l == r;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
classSolution {
publicbooleanisEqual(String s) {
int n = s.length();
int[] arr =newint[n];
for (int i = 0; i < n; ++i) arr[i]= s.charAt(i) -'0';
int[] C =newint[n];
C[0]= 1;
for (int i = 1; i < n-1; ++i) C[i]= (int)((long)C[i-1]* (n-2-i+1) / i % 10);
int l = 0, r = 0;
for (int i = 0; i < n; ++i) {
int c1 = (i <= n-2) ? C[i] : 0;
int c2 = (i-1 >= 0 && i-1 <= n-2) ? C[i-1] : 0;
l = (l + c1 * arr[i]) % 10;
r = (r + c2 * arr[i]) % 10;
}
return l == r;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
classSolution:
defisEqual(self, s: str) -> bool:
n = len(s)
arr = [int(c) for c in s]
C = [1] * n
for i in range(1, n-1):
C[i] = (C[i-1] * (n-2-i+1) // i) %10 l = r =0for i in range(n):
c1 = C[i] if i <= n-2else0 c2 = C[i-1] if0<= i-1<= n-2else0 l = (l + c1 * arr[i]) %10 r = (r + c2 * arr[i]) %10return l == r
classSolution {
funisEqual(s: String): Boolean {
val n = s.length
val arr = s.map { it - '0' }
val C = IntArray(n) { 1 }
for (i in1 until n-1) C[i] = (C[i-1] * (n-2-i+1) / i) % 10var l = 0; var r = 0for (i in0 until n) {
val c1 = if (i <= n-2) C[i] else0val c2 = if (i-1in0..(n-2)) C[i-1] else0 l = (l + c1 * arr[i]) % 10 r = (r + c2 * arr[i]) % 10 }
return l == r
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
impl Solution {
pubfnis_equal(s: String) -> bool {
let n = s.len();
let arr: Vec<u8>= s.bytes().map(|b| b -b'0').collect();
letmut c =vec![1u64; n];
for i in1..n-1 {
c[i] = c[i-1] * (n asu64-2- i asu64+1) / i asu64%10;
}
let (mut l, mut r) = (0u64, 0u64);
for i in0..n {
let c1 =if i <= n-2 { c[i] } else { 0 };
let c2 =if i >0&& i-1<= n-2 { c[i-1] } else { 0 };
l = (l + c1 * arr[i] asu64) %10;
r = (r + c2 * arr[i] asu64) %10;
}
l == r
}
}