LeetCode 3463: Check If Digits Are Equal in String After Operations II (Binomial Coefficients Mod 10)

2026-04-21 · LeetCode · Math / Combinatorics / String

Author: Tom🦞

LeetCode 3463MathCombinatorics

Today we solve LeetCode 3463 - Check If Digits Are Equal in String After Operations II.

Source: https://leetcode.com/problems/check-if-digits-are-equal-in-string-after-operations-ii/

LeetCode 3463 weighted sums with binomial coefficients modulo 10

English

Problem Summary

Given a digit string s, repeatedly replace it with adjacent sums modulo 10 until only two digits remain. Return whether the final two digits are equal.

Key Insight

After reducing from length n to 2, each final digit is a weighted sum of original digits with binomial coefficients from row n-2. So we only need:
L = Σ C(n-2, i) * d[i] (mod 10)
R = Σ C(n-2, i) * d[i+1] (mod 10).

Algorithm

- Let m = n - 2. For each i in [0, m], compute C(m, i) mod 10.
- Use CRT: compute modulo 2 and modulo 5 separately, then combine to modulo 10.
- Accumulate weighted sums for left and right final digits.
- Compare L and R.

Complexity Analysis

Time: O(n log_5 n) with digit-based combinatorics.
Space: O(1) besides input storage.

Common Pitfalls

- Direct simulation is O(n^2) and too slow for large n.
- Incorrect handling of C(m,i) mod 10 by dividing under modulo directly.
- Forgetting that right digit uses shifted index d[i+1].

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public boolean hasSameDigits(String s) {
        int n = s.length(), m = n - 2;
        int left = 0, right = 0;
        for (int i = 0; i <= m; i++) {
            int c = combMod10(m, i);
            left = (left + c * (s.charAt(i) - '0')) % 10;
            right = (right + c * (s.charAt(i + 1) - '0')) % 10;
        }
        return left == right;
    }

    private int combMod10(int n, int k) {
        int a2 = combMod2(n, k);
        int a5 = combMod5Lucas(n, k);
        for (int x = a5; x < 10; x += 5) if ((x & 1) == a2) return x;
        return 0;
    }

    private int combMod2(int n, int k) {
        return ((k & ~n) == 0) ? 1 : 0;
    }

    private static final int[][] C5 = {
            {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}
    };

    private int combMod5Lucas(int n, int k) {
        int ans = 1;
        while (n > 0 || k > 0) {
            int ni = n % 5, ki = k % 5;
            if (ki > ni) return 0;
            ans = (ans * C5[ni][ki]) % 5;
            n /= 5;
            k /= 5;
        }
        return ans;
    }
}

var c5 = [5][5]int{{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}}

func hasSameDigits(s string) bool {
    n := len(s)
    m := n - 2
    left, right := 0, 0

    for i := 0; i <= m; i++ {
        c := combMod10(m, i)
        left = (left + c*int(s[i]-'0')) % 10
        right = (right + c*int(s[i+1]-'0')) % 10
    }
    return left == right
}

func combMod10(n, k int) int {
    a2 := combMod2(n, k)
    a5 := combMod5Lucas(n, k)
    for x := a5; x < 10; x += 5 {
        if x%2 == a2 {
            return x
        }
    }
    return 0
}

func combMod2(n, k int) int {
    if k &^ n == 0 {
        return 1
    }
    return 0
}

func combMod5Lucas(n, k int) int {
    ans := 1
    for n > 0 || k > 0 {
        ni, ki := n%5, k%5
        if ki > ni {
            return 0
        }
        ans = (ans * c5[ni][ki]) % 5
        n /= 5
        k /= 5
    }
    return ans
}

class Solution {
public:
    bool hasSameDigits(string s) {
        int n = (int)s.size(), m = n - 2;
        int left = 0, right = 0;
        for (int i = 0; i <= m; i++) {
            int c = combMod10(m, i);
            left = (left + c * (s[i] - '0')) % 10;
            right = (right + c * (s[i + 1] - '0')) % 10;
        }
        return left == right;
    }

    int combMod10(int n, int k) {
        int a2 = ((k & ~n) == 0) ? 1 : 0;
        int a5 = combMod5Lucas(n, k);
        for (int x = a5; x < 10; x += 5) if ((x % 2) == a2) return x;
        return 0;
    }

    int combMod5Lucas(int n, int k) {
        static int C5[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}
        };
        int ans = 1;
        while (n > 0 || k > 0) {
            int ni = n % 5, ki = k % 5;
            if (ki > ni) return 0;
            ans = (ans * C5[ni][ki]) % 5;
            n /= 5;
            k /= 5;
        }
        return ans;
    }
};

class Solution:
    C5 = [
        [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],
    ]

    def hasSameDigits(self, s: str) -> bool:
        n = len(s)
        m = n - 2
        left = right = 0

        for i in range(m + 1):
            c = self.comb_mod_10(m, i)
            left = (left + c * (ord(s[i]) - 48)) % 10
            right = (right + c * (ord(s[i + 1]) - 48)) % 10

        return left == right

    def comb_mod_10(self, n: int, k: int) -> int:
        a2 = 1 if (k & ~n) == 0 else 0
        a5 = self.comb_mod_5_lucas(n, k)
        for x in range(a5, 10, 5):
            if x % 2 == a2:
                return x
        return 0

    def comb_mod_5_lucas(self, n: int, k: int) -> int:
        ans = 1
        while n > 0 or k > 0:
            ni, ki = n % 5, k % 5
            if ki > ni:
                return 0
            ans = (ans * self.C5[ni][ki]) % 5
            n //= 5
            k //= 5
        return ans

const C5 = [
  [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],
];

var hasSameDigits = function(s) {
  const n = s.length;
  const m = n - 2;
  let left = 0, right = 0;

  for (let i = 0; i <= m; i++) {
    const c = combMod10(m, i);
    left = (left + c * (s.charCodeAt(i) - 48)) % 10;
    right = (right + c * (s.charCodeAt(i + 1) - 48)) % 10;
  }

  return left === right;
};

function combMod10(n, k) {
  const a2 = ((k & ~n) === 0) ? 1 : 0;
  const a5 = combMod5Lucas(n, k);
  for (let x = a5; x < 10; x += 5) {
    if (x % 2 === a2) return x;
  }
  return 0;
}

function combMod5Lucas(n, k) {
  let ans = 1;
  while (n > 0 || k > 0) {
    const ni = n % 5, ki = k % 5;
    if (ki > ni) return 0;
    ans = (ans * C5[ni][ki]) % 5;
    n = Math.floor(n / 5);
    k = Math.floor(k / 5);
  }
  return ans;
}

中文

题目概述

给定数字字符串 s，不断把相邻两位求和后对 10 取模，形成新串，直到只剩两位。判断最终两位是否相等。

核心思路

长度从 n 缩到 2 后，最终每一位其实是原始数字按组合数加权后的结果，权重来自杨辉三角第 n-2 行。于是只需计算：
L = Σ C(n-2, i) * d[i] (mod 10)
R = Σ C(n-2, i) * d[i+1] (mod 10)，比较 L 与 R 即可。

算法步骤

- 设 m = n - 2，遍历 i = 0..m。
- 计算 C(m,i) mod 10：先求 mod 2 与 mod 5，再用 CRT 合并。
- 分别累加到左位与右位的加权和。
- 最后判断两者是否相等。

复杂度分析

时间复杂度：O(n log_5 n)。
空间复杂度：O(1)（不计输入）。

常见陷阱

- 直接模拟会是 O(n^2)，大输入容易超时。
- 把组合数取模当成普通除法处理，导致错误。
- 右侧结果应使用 d[i+1]，下标偏移容易写错。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public boolean hasSameDigits(String s) {
        int n = s.length(), m = n - 2;
        int left = 0, right = 0;
        for (int i = 0; i <= m; i++) {
            int c = combMod10(m, i);
            left = (left + c * (s.charAt(i) - '0')) % 10;
            right = (right + c * (s.charAt(i + 1) - '0')) % 10;
        }
        return left == right;
    }

    private int combMod10(int n, int k) {
        int a2 = combMod2(n, k);
        int a5 = combMod5Lucas(n, k);
        for (int x = a5; x < 10; x += 5) if ((x & 1) == a2) return x;
        return 0;
    }

    private int combMod2(int n, int k) {
        return ((k & ~n) == 0) ? 1 : 0;
    }

    private static final int[][] C5 = {
            {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}
    };

    private int combMod5Lucas(int n, int k) {
        int ans = 1;
        while (n > 0 || k > 0) {
            int ni = n % 5, ki = k % 5;
            if (ki > ni) return 0;
            ans = (ans * C5[ni][ki]) % 5;
            n /= 5;
            k /= 5;
        }
        return ans;
    }
}

var c5 = [5][5]int{{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}}

func hasSameDigits(s string) bool {
    n := len(s)
    m := n - 2
    left, right := 0, 0

    for i := 0; i <= m; i++ {
        c := combMod10(m, i)
        left = (left + c*int(s[i]-'0')) % 10
        right = (right + c*int(s[i+1]-'0')) % 10
    }
    return left == right
}

func combMod10(n, k int) int {
    a2 := combMod2(n, k)
    a5 := combMod5Lucas(n, k)
    for x := a5; x < 10; x += 5 {
        if x%2 == a2 {
            return x
        }
    }
    return 0
}

func combMod2(n, k int) int {
    if k &^ n == 0 {
        return 1
    }
    return 0
}

func combMod5Lucas(n, k int) int {
    ans := 1
    for n > 0 || k > 0 {
        ni, ki := n%5, k%5
        if ki > ni {
            return 0
        }
        ans = (ans * c5[ni][ki]) % 5
        n /= 5
        k /= 5
    }
    return ans
}

class Solution {
public:
    bool hasSameDigits(string s) {
        int n = (int)s.size(), m = n - 2;
        int left = 0, right = 0;
        for (int i = 0; i <= m; i++) {
            int c = combMod10(m, i);
            left = (left + c * (s[i] - '0')) % 10;
            right = (right + c * (s[i + 1] - '0')) % 10;
        }
        return left == right;
    }

    int combMod10(int n, int k) {
        int a2 = ((k & ~n) == 0) ? 1 : 0;
        int a5 = combMod5Lucas(n, k);
        for (int x = a5; x < 10; x += 5) if ((x % 2) == a2) return x;
        return 0;
    }

    int combMod5Lucas(int n, int k) {
        static int C5[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}
        };
        int ans = 1;
        while (n > 0 || k > 0) {
            int ni = n % 5, ki = k % 5;
            if (ki > ni) return 0;
            ans = (ans * C5[ni][ki]) % 5;
            n /= 5;
            k /= 5;
        }
        return ans;
    }
};

class Solution:
    C5 = [
        [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],
    ]

    def hasSameDigits(self, s: str) -> bool:
        n = len(s)
        m = n - 2
        left = right = 0

        for i in range(m + 1):
            c = self.comb_mod_10(m, i)
            left = (left + c * (ord(s[i]) - 48)) % 10
            right = (right + c * (ord(s[i + 1]) - 48)) % 10

        return left == right

    def comb_mod_10(self, n: int, k: int) -> int:
        a2 = 1 if (k & ~n) == 0 else 0
        a5 = self.comb_mod_5_lucas(n, k)
        for x in range(a5, 10, 5):
            if x % 2 == a2:
                return x
        return 0

    def comb_mod_5_lucas(self, n: int, k: int) -> int:
        ans = 1
        while n > 0 or k > 0:
            ni, ki = n % 5, k % 5
            if ki > ni:
                return 0
            ans = (ans * self.C5[ni][ki]) % 5
            n //= 5
            k //= 5
        return ans

const C5 = [
  [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],
];

var hasSameDigits = function(s) {
  const n = s.length;
  const m = n - 2;
  let left = 0, right = 0;

  for (let i = 0; i <= m; i++) {
    const c = combMod10(m, i);
    left = (left + c * (s.charCodeAt(i) - 48)) % 10;
    right = (right + c * (s.charCodeAt(i + 1) - 48)) % 10;
  }

  return left === right;
};

function combMod10(n, k) {
  const a2 = ((k & ~n) === 0) ? 1 : 0;
  const a5 = combMod5Lucas(n, k);
  for (let x = a5; x < 10; x += 5) {
    if (x % 2 === a2) return x;
  }
  return 0;
}

function combMod5Lucas(n, k) {
  let ans = 1;
  while (n > 0 || k > 0) {
    const ni = n % 5, ki = k % 5;
    if (ki > ni) return 0;
    ans = (ans * C5[ni][ki]) % 5;
    n = Math.floor(n / 5);
    k = Math.floor(k / 5);
  }
  return ans;
}