Difference Between Element Sum and Digit Sum of an Array
EasyPrompt
You are given a positive integer array nums.
- The element sum is the sum of all the elements in
nums. - The digit sum is the sum of all the digits (not necessarily distinct) that appear in
nums.
Return the absolute difference between the element sum and digit sum of nums.
Note that the absolute difference between two integers x and y is defined as |x - y|.
Example 1:
Input: nums = [1,15,6,3]
Output: 9
Explanation:
The element sum of nums is 1 + 15 + 6 + 3 = 25.
The digit sum of nums is 1 + 1 + 5 + 6 + 3 = 16.
The absolute difference between the element sum and digit sum is |25 - 16| = 9.Example 2:
Input: nums = [1,2,3,4]
Output: 0
Explanation:
The element sum of nums is 1 + 2 + 3 + 4 = 10.
The digit sum of nums is 1 + 2 + 3 + 4 = 10.
The absolute difference between the element sum and digit sum is |10 - 10| = 0.
Constraints:
1 <= nums.length <= 20001 <= nums[i] <= 2000
Approaches
3 approaches with complexity analysis and trade-offs.
This is a straightforward but least efficient approach. It calculates the element sum by iterating through the array. For the digit sum, it converts each number to a string and then iterates through the characters of the string, summing up their numeric values. This method is generally slower due to the overhead associated with string manipulation.
Algorithm
- Initialize
elementSumanddigitSumto 0. - Iterate through each number
numin the input arraynums. - Add the
numtoelementSum. - Convert
numto its string representation. - Iterate through each character of the string.
- Convert the character back to an integer (e.g.,
c - '0') and add it todigitSum. - After the loop, return the absolute difference between
elementSumanddigitSum.
Walkthrough
This approach calculates the digit sum by first converting each number into its string representation. Then, it iterates through the characters of the string, converts each character back to a digit, and adds it to the digit sum. The element sum can be calculated in the same loop or a separate one. While intuitive, this method is generally slower due to the overhead associated with string manipulation.
Here is an implementation combining both calculations in a single loop:
class Solution { public int differenceOfSum(int[] nums) { int elementSum = 0; int digitSum = 0; for (int num : nums) { elementSum += num; String s = String.valueOf(num); for (char c : s.toCharArray()) { digitSum += c - '0'; } } return Math.abs(elementSum - digitSum); }}Complexity
Time
O(N * D), where N is the length of the array and D is the maximum number of digits in a number. While asymptotically similar to other approaches, the constant factors are higher due to string operations, making it slower in practice.
Space
O(D), for storing the string representation of a number. Since D, the maximum number of digits, is small and constant (max 4 for numbers up to 2000), this is effectively O(1) space.
Trade-offs
Pros
The logic for extracting digits might be intuitive for those familiar with string manipulation.
Cons
Significantly less performant than arithmetic-based approaches due to the overhead of string creation and character parsing.
This approach uses two separate loops over the input array. The first loop computes the elementSum by summing up all the numbers. The second loop computes the digitSum by iterating through the numbers again and, for each number, using arithmetic operations (modulo and division) to extract and sum its digits.
Algorithm
- Initialize
elementSumto 0. - First Pass: Iterate through
numsand add each element toelementSum. - Initialize
digitSumto 0. - Second Pass: Iterate through
numsagain. For each number:- Use a
whileloop that continues as long as the number is positive. - In the loop, get the last digit using the modulo operator (
num % 10) and add it todigitSum. - Remove the last digit by performing integer division (
num / 10).
- Use a
- Finally, return
Math.abs(elementSum - digitSum).
Walkthrough
This method separates the two summation concerns into two distinct passes. The first pass calculates the sum of all elements. The second pass calculates the sum of all digits using efficient arithmetic operations. This separation can make the code easy to read but is slightly less optimal than a single pass.
Here is the Java implementation:
class Solution { public int differenceOfSum(int[] nums) { int elementSum = 0; // First pass: calculate element sum for (int num : nums) { elementSum += num; } int digitSum = 0; // Second pass: calculate digit sum for (int num : nums) { int currentNum = num; while (currentNum > 0) { digitSum += currentNum % 10; currentNum /= 10; } } return Math.abs(elementSum - digitSum); }}Complexity
Time
O(N * D). The algorithm makes two passes over the array of size N. The second pass involves a loop for digits (D). The total time is `O(N) + O(N*D)`, which simplifies to `O(N*D)`. Since D is a small constant, this is effectively O(N).
Space
O(1). Only a few variables are used, requiring constant extra space.
Trade-offs
Pros
Clear separation of concerns, making the code easy to understand and debug.
More efficient than string-based methods.
Cons
Requires two passes over the data, which is less efficient than a single-pass solution.
This is the most efficient approach. It calculates both the element sum and the digit sum within a single loop over the array. By processing each number completely in one go, it minimizes redundant iterations and offers the best performance.
Algorithm
- Initialize
elementSumanddigitSumto 0. - Start a single loop to iterate through each
numin thenumsarray. - Inside the loop, add
numtoelementSum. - Also inside the loop, use a nested
whileloop to process the digits of the currentnum:- Extract the last digit using
num % 10and add it todigitSum. - Remove the last digit using
num / 10.
- Extract the last digit using
- After the main loop completes, both sums are ready.
- Return the difference
elementSum - digitSum.
Walkthrough
In a single iteration over the array, we can perform both required calculations. For each number, we add it to the elementSum and then use a nested loop to extract its digits and add them to the digitSum.
Here is the optimized Java code:
class Solution { public int differenceOfSum(int[] nums) { int elementSum = 0; int digitSum = 0; for (int num : nums) { elementSum += num; int currentNum = num; while (currentNum > 0) { digitSum += currentNum % 10; currentNum /= 10; } } // For positive integers, elementSum is always >= digitSum. // So, Math.abs() is not strictly necessary but ensures correctness. return elementSum - digitSum; }}Complexity
Time
O(N * D), where N is the array length and D is the max number of digits. This is linear O(N) because D is a small constant. This approach is the fastest in practice as it minimizes loop overhead.
Space
O(1). It uses a constant amount of extra space.
Trade-offs
Pros
Most efficient solution as it traverses the array only once.
Minimal memory usage.
Cons
The logic inside the loop is slightly more combined compared to the two-pass approach, which might be perceived as marginally less readable by some.
Solutions
Solution
class Solution {public int differenceOfSum(int[] nums) { int a = 0, b = 0; for (int x : nums) { a += x; for (; x > 0; x /= 10) { b += x % 10; } } return Math.abs(a - b); }}class Solution {public: int differenceOfSum(vector<int> &nums) { int a = 0, b = 0; for (int x : nums) { a += x; for (; x; x /= 10) { b += x % 10; } } return abs(a - b); }};class Solution: def differenceOfSum(self, nums: List[int]) -> int: a, b = sum(nums), 0 for x in nums: while x: b += x % 10 x //= 10 return abs(a - b)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.