3461. Check If Digits Are Equal in String After Operations I LeetCode Solution
In this guide, you will get 3461. Check If Digits Are Equal in String After Operations I LeetCode Solution with the best time and space complexity. The solution to Check If Digits Are Equal in String After Operations I problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Check If Digits Are Equal in String After Operations I
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.
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 <= 100
s consists of only digits.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
3461. Check If Digits Are Equal in String After Operations I LeetCode Solution in C++
class Solution {
public:
bool hasSameDigits(const string& s) {
const int n = s.length();
int num1 = 0;
int num2 = 0;
for (int i = 0; i + 1 < n; ++i) {
const int coefficient = nCkMod10(n - 2, i);
num1 += (coefficient * (s[i] - '0')) % 10;
num1 %= 10;
num2 += (coefficient * (s[i + 1] - '0')) % 10;
num2 %= 10;
}
return num1 == num2;
}
private:
// Returns (n, k) % 10.
int nCkMod10(int n, int k) {
const int mod2 = lucasTheorem(n, k, 2);
const int mod5 = lucasTheorem(n, k, 5);
static constexpr int lookup[2][5] = {
{0, 6, 2, 8, 4}, // mod2 == 0
{5, 1, 7, 3, 9} // mod2 == 1
};
return lookup[mod2][mod5];
}
// Returns (n, k) % prime.
int lucasTheorem(int n, int k, int prime) {
int res = 1;
while (n > 0 || k > 0) {
const int nMod = n % prime;
const int kMod = k % prime;
res *= nCk(nMod, kMod);
res %= prime;
n /= prime;
k /= prime;
}
return res;
}
// Returns (n, k).
int nCk(int n, int k) {
int res = 1;
for (int i = 0; i < k; ++i) {
res *= (n - i);
res /= (i + 1);
}
return res;
}
}; /* code provided by PROGIEZ */
3461. Check If Digits Are Equal in String After Operations I LeetCode Solution in Java
class Solution {
public boolean hasSameDigits(String s) {
final int n = s.length();
int num1 = 0;
int num2 = 0;
for (int i = 0; i + 1 < n; ++i) {
final int coefficient = nCkMod10(n - 2, i);
num1 += (coefficient * (s.charAt(i) - '0')) % 10;
num1 %= 10;
num2 += (coefficient * (s.charAt(i + 1) - '0')) % 10;
num2 %= 10;
}
return num1 == num2;
}
// Returns (n, k) % 10.
private int nCkMod10(int n, int k) {
final int mod2 = lucasTheorem(n, k, 2);
final int mod5 = lucasTheorem(n, k, 5);
int[][] lookup = {
{0, 6, 2, 8, 4}, // mod2 == 0
{5, 1, 7, 3, 9} // mod2 == 1
};
return lookup[mod2][mod5];
}
// Returns (n, k) % prime.
private int lucasTheorem(int n, int k, int prime) {
int res = 1;
while (n > 0 || k > 0) {
final int nMod = n % prime;
final int kMod = k % prime;
res *= nCk(nMod, kMod);
res %= prime;
n /= prime;
k /= prime;
}
return res;
}
// Returns (n, k).
private int nCk(int n, int k) {
int res = 1;
for (int i = 0; i < k; ++i) {
res *= (n - i);
res /= (i + 1);
}
return res;
}
} // code provided by PROGIEZ
3461. Check If Digits Are Equal in String After Operations I LeetCode Solution in Python
class Solution:
def hasSameDigits(self, s: str) -> bool:
n = len(s)
num1 = 0
num2 = 0
for i in range(n - 1):
coefficient = self._nCkMod10(n - 2, i)
num1 += (coefficient * (int(s[i]) - 0)) % 10
num1 %= 10
num2 += (coefficient * (int(s[i + 1]) - 0)) % 10
num2 %= 10
return num1 == num2
def _nCkMod10(self, n: int, k: int) -> int:
"""Returns (n, k) % 10."""
mod2 = self._lucasTheorem(n, k, 2)
mod5 = self._lucasTheorem(n, k, 5)
lookup = [
[0, 6, 2, 8, 4], # mod2 == 0
[5, 1, 7, 3, 9] # mod2 == 1
]
return lookup[mod2][mod5]
def _lucasTheorem(self, n: int, k: int, prime: int) -> int:
"""Returns (n, k) % prime."""
res = 1
while n > 0 or k > 0:
nMod = n % prime
kMod = k % prime
res *= math.comb(nMod, kMod)
res %= prime
n //= prime
k //= prime
return res # code by PROGIEZ
