2535. Difference Between Element Sum and Digit Sum of an Array
Problem Description
In this problem, we are provided with an array of positive integers named nums
. We need to perform two types of summations:
- Element Sum: This is the sum of all the elements of the array itself. For example, if our array is
[1, 2, 3]
, the element sum would be1 + 2 + 3 = 6
. - Digit Sum: This is the sum of all digits present in the elements of the array. Continuing the above example, the digit sum would be
1 + 2 + 3 = 6
as well (since each element is comprised of only one digit).
Our goal is to calculate the absolute difference between these two sums. The absolute difference between two numbers x
and y
is the non-negative value of x - y
(denoted as |x - y|
).
Intuition
To solve this problem, we need to calculate both the element sum and the digit sum. The element sum is straightforwardāwe simply sum all the numbers in the given array. The digit sum requires a bit more work; for each number in the array, we need to extract each digit and sum them together.
Element Sum Calculation:
- Initialize a variable (let's call it
elementSum
) to 0. - Iterate through each number in the array and add it to
elementSum
. - After the loop,
elementSum
holds the total sum of the array elements.
Digit Sum Calculation:
- Initialize a variable (let's call it
digitSum
) to 0. - Loop through each number in the array.
- For each number, use a nested loop or division and modulo operations to extract each digit.
- Add each extracted digit to
digitSum
.
- After all numbers are processed,
digitSum
holds the total sum of all digits present in the array elements.
Finally, we calculate the absolute difference between elementSum
and digitSum
using the abs
function, which returns the absolute value of the passed argument.
The solution code achieves this with the use of simple, efficient loops without any need for complex data structures or algorithms. By iterating through the array only once and handling each element's digits within that iteration, we keep the time complexity linear relative to the number of digits across all elements in the array.
Learn more about Math patterns.
Solution Approach
The implementation of the solution is pretty straightforward without involving complex algorithms or data structures. Here's what happens in the provided reference solution:
- The
Solution
class defines the methoddifferenceOfSum
which accepts an integer arraynums
. - Two variables,
a
andb
, are initialized at the start of this method.- The variable
a
stores the result of calling the Pythonsum
function on thenums
list. This computes the Element Sum efficiently, as thesum
function is a Python built-in that iterates through the list and calculates the total sum of its elements. - The variable
b
is initialized to0
. It will be used to store the Digit Sum as we process each integer innums
.
- The variable
- A
for
loop iterates over each integerx
innums
. For each integer:- A
while
loop runs as long asx
is non-zero (that is, until all digits ofx
have been processed).- Inside the while loop,
b
(the Digit Sum) is incremented byx % 10
, which gives the last digit ofx
. x
is then floor-divided by10
usingx //= 10
, which effectively removes the last digit ofx
already added tob
.
- Inside the while loop,
- A
- Once all digits of all numbers in
nums
are processed and added tob
, we calculate the absolute difference between the Element Sum (a
) and the Digit Sum (b
) using theabs
function:abs(a - b)
. - The
abs(a - b)
expression calculates the non-negative difference betweena
andb
and the resulting integer is returned as the final answer.
No additional data structures are used in this approach; we only use variables to store the sums and iterate over the list of integers. The algorithm is efficient because it only involves one pass over the input array and a straightforward digit extraction process for each integer element, resulting in an overall time complexity of O(N * K), where N is the number of elements in the nums
array, and K is the average number of digits per element.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take a small example to illustrate the solution approach using the array nums = [23, 59, 2]
.
Step 1: Calculate Element Sum
We initialize elementSum
to 0
and iterate over nums
to compute the element sum.
elementSum = 0 + 23 + 59 + 2 = 84
.
Thus, the element sum is 84
.
Step 2: Calculate Digit Sum
We initialize digitSum
to 0
and start processing each integer to extract digits and compute the digit sum.
- For the first integer
23
:23 % 10
gives3
, so we add3
todigitSum
.- We then do integer division
23 // 10
which gives2
. 2 % 10
gives2
, add2
todigitSum
.- Now
2 // 10
is0
, we stop processing this number.
- For the second integer
59
:59 % 10
gives9
, add9
todigitSum
.59 // 10
gives5
.5 % 10
gives5
, add5
todigitSum
.5 // 10
is0
, we stop processing this number.
- For the third integer
2
(single-digit):2 % 10
gives2
, and we add2
todigitSum
.2 // 10
is0
, so we stop.
Adding all digits together: digitSum = 0 + 3 + 2 + 9 + 5 + 2 = 21
.
Thus, the digit sum is 21
.
Step 3: Compute Absolute Difference
Now we calculate the absolute difference between elementSum
and digitSum
.
|elementSum - digitSum| = |84 - 21| = 63
.
So, the absolute difference for the array nums = [23, 59, 2]
is 63
.
Solution Implementation
1from typing import List
2
3class Solution:
4 def difference_of_sum(self, nums: List[int]) -> int:
5 """
6 Calculate the difference between the sum of the numbers in the array
7 and the sum of the individual digits of each number in the array.
8
9 Args:
10 nums (List[int]): List of integers.
11
12 Returns:
13 int: The absolute difference between the two calculated sums.
14 """
15
16 # Calculate the sum of all numbers in the given list.
17 total_sum = sum(nums)
18
19 # Initialize the sum of individual digits to 0.
20 digits_sum = 0
21
22 # Iterate over each number in the list to calculate the sum of digits.
23 for num in nums:
24 while num:
25 # Add the last digit of the current number to the digit sum.
26 digits_sum += num % 10
27 # Remove the last digit from the current number.
28 num //= 10
29
30 # Return the absolute difference between total sum and digits sum.
31 return abs(total_sum - digits_sum)
32
1class Solution {
2 public int differenceOfSum(int[] nums) {
3 // Initialize variables to hold the sum of array elements and the sum of digits.
4 int sumOfElements = 0;
5 int sumOfDigits = 0;
6
7 // Iterate through each element in the input array.
8 for (int num : nums) {
9 // Add the current element to the sum of elements.
10 sumOfElements += num;
11
12 // Make a copy of the current element to manipulate and get the sum of its digits.
13 int temp = num;
14
15 // Extract digits of the current element and accumulate the sum.
16 while (temp > 0) {
17 // Extract the rightmost digit and add to the sum of digits.
18 int digit = temp % 10;
19 sumOfDigits += digit;
20
21 // Remove the rightmost digit to proceed to the next digit.
22 temp /= 10;
23 }
24 }
25
26 // Return the absolute difference between the sum of elements and the sum of their digits.
27 return Math.abs(sumOfElements - sumOfDigits);
28 }
29}
30
1#include <vector>
2#include <cstdlib> // Include required header for std::abs
3
4class Solution {
5public:
6 // Function that computes the absolute difference between the sum of elements
7 // in the vector and the sum of the digits of each element in the vector.
8 int differenceOfSum(vector<int>& nums) {
9 int sumOfElements = 0; // Variable to store the sum of the elements
10 int sumOfDigits = 0; // Variable to store the sum of the digits of each element
11
12 // Loop through each number in the vector
13 for (int num : nums) {
14 sumOfElements += num; // Add current number to the sum of elements
15
16 // Inner loop to calculate the sum of digits of the current number
17 for (int n = num; n > 0; n /= 10) {
18 sumOfDigits += n % 10; // Add the rightmost digit of n to the sum of digits
19 }
20 }
21
22 // Return the absolute value of the difference between the two sums
23 return std::abs(sumOfElements - sumOfDigits);
24 }
25};
26
1function differenceOfSum(nums: number[]): number {
2 // Initialize the result accumulator.
3 let resultAccumulator = 0;
4
5 // Iterate over each value in the input array 'nums'.
6 nums.forEach((value) => {
7 // Add the current value to the result accumulator.
8 resultAccumulator += value;
9
10 // As long as 'value' is not zero, subtract the digits from 'value'.
11 while (value !== 0) {
12 // Subtract the last digit of 'value' from the result accumulator.
13 resultAccumulator -= value % 10;
14
15 // Remove the last digit of 'value'.
16 value = Math.floor(value / 10);
17 }
18 });
19
20 // Return the final result, which is the difference between
21 // the sum of the numbers and the sum of their digits.
22 return resultAccumulator;
23}
24
Time and Space Complexity
Time Complexity
The time complexity of the given function differenceOfSum
involves two parts:
- The sum of all elements in the list: This is a linear operation with respect to the number of elements,
n
, hence it has a time complexity ofO(n)
. - The loop to sum the individual digits of each number: Here, each number in the list is processed to sum its digits. This operation is executed for each number in the list. The while loop for calculating the sum of digits runs as many times as there are digits in the numberāwhich, in the worst case, can be assumed to be proportional to the logarithm of the number to base 10,
O(log10(x))
. Assuming that the numbers are bounded by some valuek
, this inner loop operation isO(log10(k))
, which can be considered constant for the purposes of this analysis, sincek
does not depend onn
. Thus, this part is alsoO(n)
for the entire list.
Combining both parts, the total time complexity remains O(n)
since both operations are linear with respect to the length of the list.
Space Complexity
The space complexity of the function is O(1)
. This is because the function uses a fixed amount of additional space regardless of the input size n
. Variables a
, b
, and x
are the only extra variables, and their space requirement does not scale with n
.
Learn more about how to find time and space complexity quickly using problem constraints.
What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!