Check If Digits Are Equal in String After Operations II
Source: leetcode
Difficulty: Hard
Tags: math, string, combinatorics, number-theory

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`.


 


**Example 1:**



**Input:** s \= "3902"


**Output:** true


**Explanation:**


- Initially, `s = "3902"`
- First operation:
	- `(s[0] + s[1]) % 10 = (3 + 9) % 10 = 2`
	- `(s[1] + s[2]) % 10 = (9 + 0) % 10 = 9`
	- `(s[2] + s[3]) % 10 = (0 + 2) % 10 = 2`
	- `s` becomes `"292"`
- Second operation:
	- `(s[0] + s[1]) % 10 = (2 + 9) % 10 = 1`
	- `(s[1] + s[2]) % 10 = (9 + 2) % 10 = 1`
	- `s` becomes `"11"`
- Since the digits in `"11"` are the same, the output is `true`.



**Example 2:**



**Input:** s \= "34789"


**Output:** false


**Explanation:**


- 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`.



 


**Constraints:**


- `3 <= s.length <= 105`
- `s` consists of only digits.




C++ solution:
class Solution {
public:
    bool hasSameDigits(string s) {
        vector<int> digits;
        for (char c : s) {
            digits.push_back(c - '0');
        }
        int m = digits.size() - 2;
        vector<int> coeff(m + 1);
        for (int k = 0; k <= m; ++k) {
            int a = lucas_mod2(m, k);
            int b = lucas_mod5(m, k);
            coeff[k] = crt(a, b);
        }
        int digit1 = 0;
        for (int i = 0; i <= m; ++i) {
            digit1 = (digit1 + digits[i] * coeff[i]) % 10;
        }
        digit1 %= 10;
        int digit2 = 0;
        for (int i = 1; i <= m + 1; ++i) {
            int k = i - 1;
            digit2 = (digit2 + digits[i] * coeff[k]) % 10;
        }
        digit2 %= 10;
        return digit1 == digit2;
    }

private:
    static int lucas_mod2(int n, int k) {
        int res = 1;
        while (n > 0 || k > 0) {
            int ni = n % 2;
            int ki = k % 2;
            if (ki > ni) return 0;
            res = (res * 1) % 2;
            n /= 2;
            k /= 2;
        }
        return res;
    }

    static int lucas_mod5(int n, int k) {
        static const int table5[5][5] = {
            {1}, 
            {1, 1}, 
            {1, 2, 1}, 
            {1, 3, 3, 1}, 
            {1, 4, 1, 4, 1} 
        };
        int res = 1;
        while (n > 0 || k > 0) {
            int ni = n % 5;
            int ki = k % 5;
            if (ki > ni) return 0;
            res = (res * table5[ni][ki]) % 5;
            n /= 5;
            k /= 5;
        }
        return res;
    }

    static int crt(int a, int b) {
        static const int crt_table[2][5] = {
            {0, 6, 2, 8, 4}, 
            {5, 1, 7, 3, 9}  
        };
        return crt_table[a][b];
    }
};

Go solution:
func lucasMod2(n, k int) int {
    for k > 0 {
        if n%2 < k%2 {
            return 0
        }
        n /= 2
        k /= 2
    }
    return 1
}

func lucasMod5(n, k int) int {
    res := 1
    for n > 0 || k > 0 {
        nd := n % 5
        kd := k % 5
        if kd > nd {
            return 0
        }
        comb := 1
        for i := 0; i < kd; i++ {
            comb *= (nd - i)
            comb /= (i + 1)
        }
        res = (res * comb) % 5
        n /= 5
        k /= 5
    }
    return res
}

func hasSameDigits(s string) bool {
    m := len(s) - 2
    if m < 0 {
        return false
    }
    sum1, sum2 := 0, 0
    for i := 0; i <= m; i++ {
        a := lucasMod2(m, i)
        b := lucasMod5(m, i)
        coeff := (5*a + 6*b) % 10
        sum1 += coeff * int(s[i]-'0')
        sum2 += coeff * int(s[i+1]-'0')
    }
    sum1 %= 10
    sum2 %= 10
    return sum1 == sum2
}

Java solution:
class Solution {
    public boolean hasSameDigits(String s) {
        int n = s.length();
        int k = n - 2;
        if (k == 0) {
            return s.charAt(0) == s.charAt(1);
        }

        List<Integer> digitsK_p2 = getDigits(k, 2);
        List<Integer> digitsK_p5 = getDigits(k, 5);

        int[] coeff = new int[k + 1];
        for (int j = 0; j <= k; j++) {
            int a = lucasModWithDigits(j, 2, digitsK_p2);
            int b = lucasModWithDigits(j, 5, digitsK_p5);
            coeff[j] = (5 * a + 6 * b) % 10;
        }

        int sum0 = 0;
        int sum1 = 0;
        for (int j = 0; j <= k; j++) {
            int digit0 = s.charAt(j) - '0';
            sum0 = (sum0 + digit0 * coeff[j]) % 10;
            int digit1 = s.charAt(j + 1) - '0';
            sum1 = (sum1 + digit1 * coeff[j]) % 10;
        }
        return sum0 == sum1;
    }

    private List<Integer> getDigits(int n, int p) {
        List<Integer> digits = new ArrayList<>();
        while (n > 0) {
            digits.add(n % p);
            n /= p;
        }
        return digits;
    }

    private int lucasModWithDigits(int j, int p, List<Integer> digitsN) {
        if (j == 0) {
            return 1;
        }
        List<Integer> digitsK = new ArrayList<>();
        int jCopy = j;
        while (jCopy > 0) {
            digitsK.add(jCopy % p);
            jCopy /= p;
        }
        while (digitsK.size() < digitsN.size()) {
            digitsK.add(0);
        }
        int res = 1;
        for (int i = 0; i < digitsK.size(); i++) {
            int ni = (i < digitsN.size()) ? digitsN.get(i) : 0;
            int ki = digitsK.get(i);
            if (ki > ni) {
                return 0;
            }
            if (p == 2) {
                if (ni == 0) {
                    if (ki != 0) return 0;
                    res = (res * 1) % p;
                } else if (ni == 1) {
                    if (ki == 0 || ki == 1) res = (res * 1) % p;
                    else return 0;
                }
            } else if (p == 5) {
                int[][] table = {
                    {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}
                };
                res = (res * table[ni][ki]) % 5;
            }
        }
        return res;
    }
}

JavaScript solution:
var hasSameDigits = function(s) {
    function lucas(n, k, p) {
        let res = 1;
        while (n > 0 || k > 0) {
            const a = n % p;
            const b = k % p;
            if (b > a) return 0;
            let comb = 1;
            for (let i = a - b + 1; i <= a; i++) {
                comb = (comb * i) % p;
            }
            let denom = 1;
            for (let i = 2; i <= b; i++) {
                denom = (denom * i) % p;
            }
            let invDenom = 1;
            let exponent = p - 2;
            let base = denom;
            while (exponent > 0) {
                if (exponent % 2 === 1) {
                    invDenom = (invDenom * base) % p;
                }
                base = (base * base) % p;
                exponent = Math.floor(exponent / 2);
            }
            comb = (comb * invDenom) % p;
            res = (res * comb) % p;
            n = Math.floor(n / p);
            k = Math.floor(k / p);
        }
        return res;
    }

    const k = s.length - 2;
    if (k < 0) return false;

    let sum1 = 0, sum2 = 0;

    for (let i = 0; i <= k; i++) {
        const mod2 = lucas(k, i, 2);
        const mod5 = lucas(k, i, 5);

        const a = mod2;
        const b = mod5;

        let delta = (a - (b % 2)) % 2;
        if (delta < 0) delta += 2;

        const c = (delta * 5 + b) % 10;

        const d1 = parseInt(s[i], 10);
        sum1 = (sum1 + c * d1) % 10;

        const d2 = parseInt(s[i + 1], 10);
        sum2 = (sum2 + c * d2) % 10;
    }

    return sum1 === sum2;
};

Python solution:
class Solution:
    def hasSameDigits(self, s: str) -> bool:
        n = len(s)
        if n == 2:
            return s[0] == s[1]
        k = n - 2

        mod5_table = [
            [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],
        ]

        crt_table = {
            (0, 0): 0,
            (0, 1): 6,
            (0, 2): 2,
            (0, 3): 8,
            (0, 4): 4,
            (1, 0): 5,
            (1, 1): 1,
            (1, 2): 7,
            (1, 3): 3,
            (1, 4): 9,
        }

        def compute_mod5(k_val, i_val):
            res = 1
            while k_val > 0 or i_val > 0:
                dk = k_val % 5
                di = i_val % 5
                if di > dk:
                    return 0
                res = (res * mod5_table[dk][di]) % 5
                k_val = k_val // 5
                i_val = i_val // 5
            return res

        sum1, sum2 = 0, 0
        for i in range(k + 1):
            a = 1 if (i & k) == i else 0
            b = compute_mod5(k, i)
            if b == 0:
                mod10 = 5 if a else 0
            else:
                mod10 = crt_table[(a, b)]
            sum1 = (sum1 + int(s[i]) * mod10) % 10
            sum2 = (sum2 + int(s[i + 1]) * mod10) % 10

        return sum1 == sum2

Ruby solution:
def has_same_digits(s)
    m = s.length
    return s[0] == s[1] if m == 2

    k = m - 2
    digits = s.chars.map(&:to_i)

    mod5_table = [
        [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],
    ]

    crt_table = {
        [0, 0] => 0,
        [0, 1] => 6,
        [0, 2] => 2,
        [0, 3] => 8,
        [0, 4] => 4,
        [1, 0] => 5,
        [1, 1] => 1,
        [1, 2] => 7,
        [1, 3] => 3,
        [1, 4] => 9,
    }

    sum0 = 0
    sum1 = 0

    (0..k).each do |s_val|
        a = (k & s_val) == s_val ? 1 : 0

        n_temp = k
        k_temp = s_val
        res = 1
        loop do
            break if n_temp == 0 && k_temp == 0

            n_digit = n_temp % 5
            k_digit = k_temp % 5

            if k_digit > n_digit
                res = 0
                break
            end

            res = (res * mod5_table[n_digit][k_digit]) % 5

            n_temp /= 5
            k_temp /= 5
        end

        b = res % 5
        mod10 = crt_table[[a, b]]

        sum0 += mod10 * digits[s_val]
        sum1 += mod10 * digits[s_val + 1]
    end

    sum0 %= 10
    sum1 %= 10

    sum0 == sum1
end