LeetCode 3461: Check If Digits Are Equal in String After Operations I (Triangle Reduction Simulation)

2026-04-16 · LeetCode · String / Simulation / Math

Author: Tom🦞

LeetCode 3461StringSimulation

Today we solve LeetCode 3461 - Check If Digits Are Equal in String After Operations I.

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

LeetCode 3461 triangular reduction where adjacent digits are summed modulo 10 until two digits remain

English

Problem Summary

Given a digit string s, repeatedly replace it with the sequence formed by adjacent sums modulo 10: next[i] = (s[i] + s[i+1]) % 10. Continue until only two digits remain, and return whether they are equal.

Key Insight

This is a deterministic triangle-style reduction. Every round shortens the string by one, so simulation is straightforward and safe under the constraints.

Algorithm

- Convert characters to integer digits array.
- While length > 2, build a new array of length n-1 using adjacent modulo-10 sums.
- Replace current array with the new one.
- At length 2, return whether the two digits are equal.

Complexity Analysis

For length n, total operations are (n-1) + (n-2) + ... + 1 = O(n^2).
Time: O(n^2).
Space: O(n) for the current/next arrays.

Common Pitfalls

- Forgetting modulo 10 on each adjacent sum.
- Mutating in place incorrectly and corrupting values needed by the same round.
- Stopping at length 1 instead of length 2.

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

class Solution {
    public boolean hasSameDigits(String s) {
        int n = s.length();
        int[] cur = new int[n];
        for (int i = 0; i < n; i++) {
            cur[i] = s.charAt(i) - '0';
        }

        while (n > 2) {
            int[] next = new int[n - 1];
            for (int i = 0; i < n - 1; i++) {
                next[i] = (cur[i] + cur[i + 1]) % 10;
            }
            cur = next;
            n--;
        }
        return cur[0] == cur[1];
    }
}

func hasSameDigits(s string) bool {
    n := len(s)
    cur := make([]int, n)
    for i := 0; i < n; i++ {
        cur[i] = int(s[i] - '0')
    }

    for n > 2 {
        next := make([]int, n-1)
        for i := 0; i < n-1; i++ {
            next[i] = (cur[i] + cur[i+1]) % 10
        }
        cur = next
        n--
    }
    return cur[0] == cur[1]
}

class Solution {
public:
    bool hasSameDigits(string s) {
        int n = s.size();
        vector<int> cur(n);
        for (int i = 0; i < n; i++) {
            cur[i] = s[i] - '0';
        }

        while (n > 2) {
            vector<int> next(n - 1);
            for (int i = 0; i < n - 1; i++) {
                next[i] = (cur[i] + cur[i + 1]) % 10;
            }
            cur = move(next);
            n--;
        }
        return cur[0] == cur[1];
    }
};

class Solution:
    def hasSameDigits(self, s: str) -> bool:
        cur = [ord(ch) - ord('0') for ch in s]

        while len(cur) > 2:
            cur = [(cur[i] + cur[i + 1]) % 10 for i in range(len(cur) - 1)]

        return cur[0] == cur[1]

var hasSameDigits = function(s) {
  let cur = Array.from(s, ch => ch.charCodeAt(0) - 48);

  while (cur.length > 2) {
    const next = new Array(cur.length - 1);
    for (let i = 0; i < cur.length - 1; i++) {
      next[i] = (cur[i] + cur[i + 1]) % 10;
    }
    cur = next;
  }

  return cur[0] === cur[1];
};

中文

题目概述

给你一个数字字符串 s。重复执行操作：把每一对相邻数字相加后对 10 取模，形成新字符串，直到只剩两个数字。判断这两个数字是否相等。

核心思路

这是一个固定过程的“数字三角形”收缩。每轮长度减少 1，直接模拟即可，逻辑清晰且在题目约束内足够高效。

算法步骤

- 先把字符串转成整型数组。
- 当数组长度大于 2 时，构造长度为 n-1 的新数组。
- 新数组第 i 位为 (cur[i] + cur[i+1]) % 10。
- 替换当前数组，继续下一轮。
- 最终比较剩余两个数字是否相等。

复杂度分析

长度为 n 时，总计算量为 (n-1)+(n-2)+...+1。
时间复杂度：O(n^2)。
空间复杂度：O(n)。

常见陷阱

- 忘记每步都要对 10 取模。
- 原地覆盖导致本轮后续计算读到被污染的数据。
- 终止条件写错（应该停在长度为 2）。

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

class Solution {
    public boolean hasSameDigits(String s) {
        int n = s.length();
        int[] cur = new int[n];
        for (int i = 0; i < n; i++) {
            cur[i] = s.charAt(i) - '0';
        }

        while (n > 2) {
            int[] next = new int[n - 1];
            for (int i = 0; i < n - 1; i++) {
                next[i] = (cur[i] + cur[i + 1]) % 10;
            }
            cur = next;
            n--;
        }
        return cur[0] == cur[1];
    }
}

func hasSameDigits(s string) bool {
    n := len(s)
    cur := make([]int, n)
    for i := 0; i < n; i++ {
        cur[i] = int(s[i] - '0')
    }

    for n > 2 {
        next := make([]int, n-1)
        for i := 0; i < n-1; i++ {
            next[i] = (cur[i] + cur[i+1]) % 10
        }
        cur = next
        n--
    }
    return cur[0] == cur[1]
}

class Solution {
public:
    bool hasSameDigits(string s) {
        int n = s.size();
        vector<int> cur(n);
        for (int i = 0; i < n; i++) {
            cur[i] = s[i] - '0';
        }

        while (n > 2) {
            vector<int> next(n - 1);
            for (int i = 0; i < n - 1; i++) {
                next[i] = (cur[i] + cur[i + 1]) % 10;
            }
            cur = move(next);
            n--;
        }
        return cur[0] == cur[1];
    }
};

class Solution:
    def hasSameDigits(self, s: str) -> bool:
        cur = [ord(ch) - ord('0') for ch in s]

        while len(cur) > 2:
            cur = [(cur[i] + cur[i + 1]) % 10 for i in range(len(cur) - 1)]

        return cur[0] == cur[1]

var hasSameDigits = function(s) {
  let cur = Array.from(s, ch => ch.charCodeAt(0) - 48);

  while (cur.length > 2) {
    const next = new Array(cur.length - 1);
    for (let i = 0; i < cur.length - 1; i++) {
      next[i] = (cur[i] + cur[i + 1]) % 10;
    }
    cur = next;
  }

  return cur[0] === cur[1];
};