3461. Check If Digits Are Equal in String After Operations I

EasyMathStringCombinatoricsNumber TheorySimulation

Problem Description

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.

Intuition

The problem involves transforming a string of digits through repeated operations until only two digits remain. The transformation requires creating a new sequence where each new digit is the sum of each consecutive pair of original digits, taken modulo 10. This simulates a "condensing" of the string into fewer digits iteratively.

To solve this problem, simulate the operation as described: reduce the string step by step until it consists of precisely two digits. In each pass, calculate the modulo 10 sum of each adjacent pair, shortening the string. Finally, once only two digits remain, check if they are equal. This direct simulation ensures the transformation adheres to the problem constraints and correctly determines the required condition.

Learn more about Math and Combinatorics patterns.

Solution Approach

The solution employs a simulation approach to tackle the problem:

Convert the String to a List of Integers: Start by transforming the input string s into a list of integers. This allows easy manipulation and arithmetic operations on individual digits.
Iterative Reduction Process:
- Loop over the string while its length is greater than two.
- For each element in the sequence, compute the sum of each pair of consecutive digits, taking modulo 10 of each sum. This effectively reduces the sequence by one digit in each complete pass. The use of modulo 10 ensures each digit in the new sequence remains a valid single-digit number.
Comparison of Final Digits: Once reduced to two digits, the task is to compare them. If the digits are identical, return true; otherwise, return false.

The provided function hasSameDigits implements this logic effectively:

class Solution:
    def hasSameDigits(self, s: str) -> bool:
        t = list(map(int, s))
        n = len(t)
        for k in range(n - 1, 1, -1):
            for i in range(k):
                t[i] = (t[i] + t[i + 1]) % 10
        return t[0] == t[1]

In the inner loop, t[i] is updated with the result of (t[i] + t[i + 1]) % 10, and this continues until t becomes a two-element list. The outer loop adjusts dynamically with each iteration, making the process efficient for any initial length of the string s.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through this problem with an example to understand the solution approach.

Suppose we are given the string s = "123456". We'll follow the solution approach step-by-step.

Convert the String to a List of Integers:
Convert s into a list of integers: t = [1, 2, 3, 4, 5, 6].
Iterative Reduction Process:
We need to reduce t iteratively until only two digits remain.
- First Pass:
  - Compute (1 + 2) % 10 = 3
  - Compute (2 + 3) % 10 = 5
  - Compute (3 + 4) % 10 = 7
  - Compute (4 + 5) % 10 = 9
  - Compute (5 + 6) % 10 = 1
    Resulting list: t = [3, 5, 7, 9, 1]
- Second Pass:
  - Compute (3 + 5) % 10 = 8
  - Compute (5 + 7) % 10 = 2
  - Compute (7 + 9) % 10 = 6
  - Compute (9 + 1) % 10 = 0
    Resulting list: t = [8, 2, 6, 0]
- Third Pass:
  - Compute (8 + 2) % 10 = 0
  - Compute (2 + 6) % 10 = 8
  - Compute (6 + 0) % 10 = 6
    Resulting list: t = [0, 8, 6]
- Fourth Pass:
  - Compute (0 + 8) % 10 = 8
  - Compute (8 + 6) % 10 = 4
    Resulting list: t = [8, 4]
Comparison of Final Digits:
Now t has only two digits: [8, 4]. Compare these two digits. Since they are different, the result is false.

The final output for the input string s = "123456" is false.

Solution Implementation

1class Solution:
2    def hasSameDigits(self, s: str) -> bool:
3        # Convert each character in the string to an integer
4        digits = list(map(int, s))
5
6        # Get the length of the digits list
7        n = len(digits)
8
9        # Process the digits with a nested loop
10        # The outer loop starts with the last index and decreases
11        for k in range(n - 1, 1, -1):
12            # The inner loop modifies the current list of digits
13            for i in range(k):
14                # Update each element by adding it to the next element and taking mod 10
15                digits[i] = (digits[i] + digits[i + 1]) % 10
16
17        # Check if the first two elements in the transformed list are the same
18        return digits[0] == digits[1]
19

1class Solution {
2    public boolean hasSameDigits(String s) {
3        // Convert the input string to a character array for easier manipulation
4        char[] digitArray = s.toCharArray();
5        int length = digitArray.length;
6
7        // Perform calculations from right to left, reducing the size
8        // of the array by modifying elements directly
9        for (int k = length - 1; k > 1; --k) {
10            for (int i = 0; i < k; ++i) {
11                // Calculate new digit by summing current and next digit, 
12                // taking modulo 10 for single digit, and converting it back to character
13                digitArray[i] = (char) ((digitArray[i] - '0' + digitArray[i + 1] - '0') % 10 + '0');
14            }
15        }
16
17        // Return true if the first two digits are the same after transformations
18        return digitArray[0] == digitArray[1];
19    }
20}
21

1#include <string>
2
3class Solution {
4public:
5    // Method to determine if the first two digits of the transformed string t are the same
6    bool hasSameDigits(std::string s) {
7        int n = s.size();  // Get the size of the input string
8        std::string t = s;  // Make a copy of the input string to modify
9        // Iterate backwards from the second-to-last character of the string down to 2
10        for (int k = n - 1; k > 1; --k) {
11            // Transform the string by modifying each character based on adjacent characters
12            for (int i = 0; i < k; ++i) {
13                // Calculate the new character by adding two adjacent characters, taking modulo 10, and converting back to a character
14                t[i] = (t[i] - '0' + t[i + 1] - '0') % 10 + '0';  
15            }
16        }
17        // Compare the first two characters of the modified string
18        return t[0] == t[1];
19    }
20};
21

1function hasSameDigits(s: string): boolean {
2    // Convert the input string into an array of numbers
3    const digits = s.split('').map(Number);
4    const length = digits.length;
5
6    // Perform a reduction-like operation on the array
7    for (let k = length - 1; k > 1; --k) {
8        for (let i = 0; i < k; ++i) {
9            // Update each element to be the sum of itself and the next, modulo 10
10            digits[i] = (digits[i] + digits[i + 1]) % 10;
11        }
12    }
13
14    // Return whether the first two elements are the same
15    return digits[0] === digits[1];
16}
17

Time and Space Complexity

The time complexity of the code is O(n^2) because there are two nested loops. The outer loop runs n-2 times (where n is the length of the list t) and the inner loop runs up to n-1 times. This results in a quadratic time complexity.

The space complexity is O(n), as the algorithm uses a list t derived from the input string, occupying space proportional to the length of s.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which of these pictures shows the visit order of a depth-first search?

I don't know