Check If Digits Are Equal in String After Operations II

Check If Digits Are Equal in String After Operations II - Problem

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.

Input & Output

Example 1 — Basic Reduction

$ Input: s = "1234"

› Output: false

💡 Note: Step 1: "1234" → "357" (1+2=3, 2+3=5, 3+4=7). Step 2: "357" → "82" (3+5=8, 5+7=12→2). Final: 8 ≠ 2, so return false.

Example 2 — Equal Final Digits

$ Input: s = "808"

› Output: true

💡 Note: Step 1: "808" → "88" (8+0=8, 0+8=8). Final: 8 = 8, so return true.

Example 3 — Already Two Digits

$ Input: s = "11"

› Output: true

💡 Note: String already has 2 digits: 1 = 1, so return true.

Constraints

2 ≤ s.length ≤ 1000
s consists of digits only

Visualization

Tap to expand

Understanding the Visualization

Input

String of digits to be reduced

Reduction

Iteratively combine adjacent digits

Comparison

Check if final two digits are equal

Key Takeaway

🎯 Key Insight: The reduction follows Pascal's triangle pattern - each original digit contributes to the final result with a predictable coefficient weight.

Asked in

G Google 25 M Microsoft 18

The key insight is that this reduction process follows Pascal's triangle coefficients. We can either simulate the reduction step-by-step or use mathematical properties. The simulation approach is simpler with Time: O(n²), Space: O(n), while the mathematical approach can achieve O(n) time with O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Simulation Approach	O(n²)	O(n)	Directly simulate the reduction process until two digits remain
Pascal's Triangle Optimization	O(n)	O(1)	Use mathematical coefficients to directly calculate final digits

Simulation Approach — Algorithm Steps

Start with original string
While length > 2: create new string by summing adjacent pairs mod 10
Check if final two digits are equal

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial String

Start with input digits

Combine Adjacent

Sum each pair of adjacent digits mod 10

Repeat Until 2 Digits

Continue reduction until only 2 digits remain

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool solution(char* s) {
    int len = strlen(s);
    char temp[1000];
    
    while (len > 2) {
        for (int i = 0; i < len - 1; i++) {
            int digitSum = ((s[i] - '0') + (s[i + 1] - '0')) % 10;
            temp[i] = '0' + digitSum;
        }
        temp[len - 1] = '\0';
        strcpy(s, temp);
        len--;
    }
    
    return s[0] == s[1];
}

int main() {
    char s[1000];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    bool result = solution(s);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Each iteration reduces length by 1, and we do O(n) work per iteration

⚠ Quadratic Growth

Space Complexity

O(n)

Need to store intermediate strings of decreasing lengths

⚡ Linearithmic Space

9.0K Views

Medium Frequency

~25 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Simulation Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler