Check If Digits Are Equal in String After Operations I

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

Math String Simulation Combinatorics Number Theory Easy

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 Case

$ Input: s = "1234"

› Output: false

💡 Note: Round 1: "1234" → "357" (1+2=3, 2+3=5, 3+4=7). Round 2: "357" → "82" (3+5=8, 5+7=12→2). Final digits 8 and 2 are different, so return false.

Example 2 — Equal Result

$ Input: s = "999"

› Output: true

💡 Note: Round 1: "999" → "88" (9+9=18→8, 9+9=18→8). Final digits are both 8, so return true.

Example 3 — Two Digits

$ Input: s = "12"

› Output: false

💡 Note: String already has two digits. 1 ≠ 2, so return false.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input String

Start with digit string of length n

Combine Process

Sum adjacent pairs mod 10, repeat until 2 digits

Final Check

Return true if final digits are equal

Key Takeaway

🎯 Key Insight: Each round reduces string length by exactly 1, requiring n-2 total rounds

Asked in

G Google 15 M Microsoft 8

The key insight is to simulate the digit combination process round by round until only two digits remain. Each round reduces the string length by 1, so we need exactly n-2 rounds. Best approach uses direct simulation with efficient string building. Time: O(n²), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized String Building	O(n²)	O(n)	Use StringBuilder/similar for efficient string concatenation
Direct Simulation	O(n²)	O(n)	Simulate the process step by step until two digits remain

Optimized String Building — Algorithm Steps

Use StringBuilder or equivalent
Simulate round by round
Efficiently build new strings
Check final result

Visualization

Tap to expand

Step-by-Step Walkthrough

Convert to Array

Work with integer arrays

Process Rounds

Build new arrays efficiently

Final Check

Compare last two elements

Code -

solution.c — C

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

int solution(char* s) {
    int len = strlen(s);
    int* current = malloc(len * sizeof(int));
    int currentLen = len;
    
    for (int i = 0; i < len; i++) {
        current[i] = s[i] - '0';
    }
    
    while (currentLen > 2) {
        int* nextRound = malloc((currentLen - 1) * sizeof(int));
        int nextLen = 0;
        
        for (int i = 0; i < currentLen - 1; i++) {
            int digitSum = (current[i] + current[i + 1]) % 10;
            nextRound[nextLen++] = digitSum;
        }
        
        free(current);
        current = nextRound;
        currentLen = nextLen;
    }
    
    int result = (current[0] == current[1]);
    free(current);
    return result;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Still need n-2 rounds with O(n) work per round

⚠ Quadratic Growth

Space Complexity

O(n)

StringBuilder reduces allocations but still O(n) space for strings

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~15 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

Optimized String Building — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler