Check if digits are equal in string after operations ii

Math String Combinatorics Number Theory

14.2% acceptance

Feb 25, 2026

104

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.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn has_same_digits(s: String) -> bool {
    let n = s.len();
    let d: Vec<i64> = s.bytes().map(|b| (b - b'0') as i64).collect();
    if n <= 2 { return d[0] == d[1]; }
    let m = n - 2;

    // We need C(m, i) mod 10 for i in 0..=m.
    // Use Lucas' theorem + CRT instead of building the full Pascal row (O(n) vs O(n^2)).
    //
    // C(m, i) mod 2  : by Lucas mod 2, equals 1 iff (i & m) == i
    // C(m, i) mod 5  : by Lucas mod 5, = product of C(m_j, i_j) mod 5
    //                  where m_j, i_j are base-5 digits
    // CRT             : combine (mod 2, mod 5) -> mod 10

    // C(a, b) mod 5 for a,b in 0..5  (b > a => 0)
    const C5: [[i64; 5]; 5] = [
      [1, 0, 0, 0, 0],
      [1, 1, 0, 0, 0],
      [1, 2, 1, 0, 0],
      [1, 3, 3, 1, 0],
      [1, 4, 1, 4, 1], // C(4,2)=6 mod5=1
    ];

    // CRT table: crt[x mod 2][x mod 5] => x mod 10
    const CRT: [[i64; 5]; 2] = [
      [0, 6, 2, 8, 4], // even
      [5, 1, 7, 3, 9], // odd
    ];

    // Base-5 digits of m (up to 8 digits since 5^8 = 390625 > 10^5)
    let mut m5 = [0usize; 8];
    let mut tmp = m;
    for j in 0..8 { m5[j] = tmp % 5; tmp /= 5; }

    // Compute C(m, i) mod 10 via Lucas + CRT, then dot-product with digits
    let weighted_sum = |offset: usize| -> i64 {
      let mut total = 0i64;
      for i in 0..=m {
        // mod 2 via Lucas
        let c2 = ((i & m) == i) as usize;
        // mod 5 via Lucas
        let mut i_tmp = i;
        let mut p5 = 1i64;
        for j in 0..8 {
          let ij = i_tmp % 5;
          i_tmp /= 5;
          let c = C5[m5[j]][ij];
          if c == 0 { p5 = 0; break; }
          p5 = p5 * c % 5;
        }
        let c10 = CRT[c2][p5 as usize];
        total = (total + d[i + offset] * c10) % 10;
      }
      total
    };

    weighted_sum(0) == weighted_sum(1)
  }
}