3153. Sum of Digit Differences of All Pairs LeetCode Solution
In this guide, you will get 3153. Sum of Digit Differences of All Pairs LeetCode Solution with the best time and space complexity. The solution to Sum of Digit Differences of All Pairs 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 Sum of Digit Differences of All Pairs
You are given an array nums consisting of positive integers where all integers have the same number of digits.
The digit difference between two integers is the count of different digits that are in the same position in the two integers.
Return the sum of the digit differences between all pairs of integers in nums.
Example 1:
Input: nums = [13,23,12]
Output: 4
Explanation:
We have the following:
– The digit difference between 13 and 23 is 1.
– The digit difference between 13 and 12 is 1.
– The digit difference between 23 and 12 is 2.
So the total sum of digit differences between all pairs of integers is 1 + 1 + 2 = 4.
Example 2:
Input: nums = [10,10,10,10]
Output: 0
Explanation:
All the integers in the array are the same. So the total sum of digit differences between all pairs of integers will be 0.
2 <= nums.length <= 105
1 <= nums[i] < 109
All integers in nums have the same number of digits.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(10) = O(1)
3153. Sum of Digit Differences of All Pairs LeetCode Solution in C++
class Solution {
public:
long long sumDigitDifferences(vector<int>& nums) {
const int n = nums.size();
const int digitSize = std::to_string(nums[0]).size();
long ans = 0;
for (int i = 0, denominator = 1; i < digitSize; ++i, denominator *= 10) {
vector<int> count(10);
for (const int num : nums)
++count[num / denominator % 10];
for (const int freq : count)
ans += freq * (n - freq);
}
return ans / 2;
}
}; /* code provided by PROGIEZ */
3153. Sum of Digit Differences of All Pairs LeetCode Solution in Java
class Solution {
public long sumDigitDifferences(int[] nums) {
final int n = nums.length;
final int digitSize = String.valueOf(nums[0]).length();
long ans = 0;
for (int i = 0, denominator = 1; i < digitSize; ++i, denominator *= 10) {
int[] count = new int[10];
for (final int num : nums)
++count[num / denominator % 10];
for (final int freq : count)
ans += freq * (n - freq);
}
return ans / 2;
}
} // code provided by PROGIEZ
3153. Sum of Digit Differences of All Pairs LeetCode Solution in Python
class Solution:
def sumDigitDifferences(self, nums: list[int]) -> int:
n = len(nums)
digitSize = len(str(nums[0]))
ans = 0
denominator = 1
for _ in range(digitSize):
count = [0] * 10
for num in nums:
count[num // denominator % 10] += 1
ans += sum(freq * (n - freq) for freq in count)
denominator *= 10
return ans // 2 # code by PROGIEZ
