1085. Sum of Digits in the Minimum Number

EasyArrayMath
Leetcode Link

Problem Description

In this problem, you're given an array of integers called nums. Your task is to determine the sum of the digits of the smallest integer in this array. Once you've calculated this sum, you need to decide the return value based on whether this sum is odd or even. If the sum of the digits of the smallest integer is odd, return 0. If it's even, return 1.

For example, if the array is [34, 23, 1, 24, 75, 33, 54, 8], the smallest integer is 1, and the sum of its digits is 1. Since 1 is odd, the function should return 0.

Intuition

To find the solution to this problem, you should follow these steps:

  1. Identify the smallest integer in the nums array. You can do this by directly using Python's min() function.
  2. Calculate the sum of digits of this smallest integer. This can be done by repeatedly taking the remainder of the number when divided by 10 (to get the last digit) and adding it to a sum variable. After getting the last digit, you divide the number by 10 (using floor division) to remove the last digit. You keep doing this in a loop until the number becomes 0.
  3. To determine if the sum is even or odd, you can use the bitwise AND operator & with 1. If s & 1 is 1, the sum is odd; otherwise, it's even. To return 0 for odd sums and 1 for even sums, you can use the XOR operator ^ with 1 to invert the bit returned by s & 1.

The given solution follows this thinking process and applies these operations to arrive at the correct answer.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Depth first search is equivalent to which of the tree traversal order?

Solution Approach

The implementation of the solution uses a straightforward algorithm that involves the following steps:

  1. Find the minimum value in the array: We use Python's built-in min() function to find the smallest integer in the nums array. This is an efficient way to scan through the array once and identify the minimum value. This step uses O(n) time, where n is the number of elements in nums.

  2. Sum the digits of the minimum value: After finding the smallest integer x, we initialize a variable s to 0 to hold the sum of the digits. We then enter a while loop that continues as long as x is not 0. Inside the loop, we:

    • Use the modulo operator % to get the last digit of x by calculating x % 10.
    • Add this last digit to the sum s.
    • Remove the last digit from x by performing floor division x //= 10, effectively reducing x by one digit from the right.

    This loop runs as many times as there are digits in the minimum value, which is at most O(log(max(nums))) since the number of digits in a number is proportional to the logarithm of the number.

  3. Determine the parity of the sum and provide the correct output: After obtaining the sum of the digits s, we need to return 0 if s is odd, and 1 if s is even. Since we want to return the opposite of the sum's parity:

    • We check if the sum is odd using s & 1 which is a common bit manipulation technique to get the least significant bit of a number.
    • We then invert the result by using the XOR operator with 1, s & 1 ^ 1. The operation s & 1 returns 1 if the sum is odd (because the least significant bit will be 1) and 0 otherwise. The XOR operation ^ 1 essentially flips the bit, turning 1 into 0 and vice versa.

By following this simple yet effective algorithm and using basic bit manipulation, we efficiently solve the problem without the need for complex data structures or patterns.

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

Which two pointer techniques do you use to check if a string is a palindrome?

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Consider the array [56, 32, 14, 12, 22].

  1. Find the Minimum Value in the Array: We apply the min() function to find the smallest integer in the nums array. In this case, min([56, 32, 14, 12, 22]) gives us 12, which is the smallest integer in the array.

  2. Sum the Digits of the Minimum Value: With the smallest integer, 12, we need to sum its digits:

    • We initialize sum s to 0.
    • We enter a while loop where x is our smallest integer, 12, and iterate until x becomes 0:
      • First iteration: x % 10 gives us 2, and x // 10 reduces x to 1.
      • Add 2 to the sum s (initially 0), so s becomes 2.
      • Second iteration: x % 10 gives us 1, and x // 10 reduces x to 0.
      • Add 1 to the sum s (currently 2), so s becomes 3.
    • The loop ends as x is now 0.

  3. Determine the Parity of the Sum and Provide the Correct Output: Now we have the sum of the digits s which is 3. We use bit manipulation to find out if it's odd or even and then return the corresponding value:

    • We check if the sum is odd using s & 1. In this case, it is 3 & 1, which evaluates to 1 (since 3 is odd).
    • We then invert the result using the XOR operator with 1, i.e., s & 1 ^ 1. So the final operation is 1 ^ 1, which evaluates to 0.

Thus, since the sum of the digits 3 is odd, we return 0. This small example demonstrates how the algorithm effectively computes the correct return value by identifying the smallest number, summing its digits, and determining the sum's parity with simple arithmetic and bit manipulation operations.

Solution Implementation

1from typing import List
2
3class Solution:
4    def sumOfDigits(self, nums: List[int]) -> int:
5        # Find the minimum number in the list
6        min_num = min(nums)
7      
8        # Initialize sum of digits to zero
9        digit_sum = 0
10      
11        # Calculate the sum of digits of the minimum number
12        while min_num:
13            digit_sum += min_num % 10  # Get the last digit and add to sum
14            min_num //= 10  # Remove the last digit
15      
16        # Check if the sum of digits is odd or even
17        # If the sum is odd, return 0 (since odd & 1 is 1, then 1 ^ 1 is 0)
18        # If the sum is even, return 1 (since even & 1 is 0, then 0 ^ 1 is 1)
19        return digit_sum % 2 ^ 1
20
1class Solution {
2    // This method calculates the sum of digits of the smallest number in the array.
3    // If the sum is odd, it returns 0, and if even, it returns 1.
4    public int sumOfDigits(int[] nums) {
5        // Initialize the minimum to a high value.
6        int min = 100;
7      
8        // Iterate through the array to find the smallest value.
9        for (int value : nums) {
10            min = Math.min(min, value);
11        }
12      
13        // Calculate the sum of the digits of the smallest number.
14        int sum = 0;
15        while (min > 0) {
16            sum += min % 10; // Add the rightmost digit to sum.
17            min /= 10;        // Remove the rightmost digit.
18        }
19      
20        // If the sum of the digits is odd, return 0, otherwise return 1.
21        // The bitwise AND with 1 will be 0 if sum is even, or 1 if odd.
22        // The bitwise XOR with 1 inverts the result, so even sums return 1 and odd sums return 0.
23        return sum & 1 ^ 1; 
24    }
25}
26
1class Solution {
2public:
3    int sumOfDigits(vector<int>& nums) {
4        // Find the minimum element in the vector 'nums'
5        int minElement = *min_element(nums.begin(), nums.end());
6      
7        // Initialize sum of digits of the minimum element to zero
8        int sum = 0;
9
10        // Calculate the sum of digits of the minimum element
11        for (; minElement > 0; minElement /= 10) {
12            sum += minElement % 10; // Add the least significant digit to 'sum'
13        }
14      
15        // Return 1 if the sum is even, and 0 if the sum is odd
16        // The bitwise '&' checks if the sum is odd (sum & 1 is 1 if sum is odd),
17        // then the '^ 1' inverts the bit, so odd sums return 0, even sums return 1.
18        return sum & 1 ^ 1;
19    }
20};
21
1// Function to find the sum of digits of the smallest number in the array.
2// Returns 1 if sum of digits is even, and 0 if sum is odd
3function sumOfDigits(nums: number[]): number {
4    // Find the minimum element in the array 'nums'
5    const minElement: number = Math.min(...nums);
6
7    // Initialize sum of digits of the minimum element to zero
8    let sumDigits: number = 0;
9
10    // Temporary variable to hold the value for manipulation
11    let tempMinElement: number = minElement;
12
13    // Calculate the sum of digits of the minimum element
14    while (tempMinElement > 0) {
15        sumDigits += tempMinElement % 10; // Add the least significant digit to 'sumDigits'
16        tempMinElement = Math.floor(tempMinElement / 10); // Remove the least significant digit
17    }
18
19    // Return 1 if the sumDigits is even, and 0 if the sumDigits is odd
20    // The bitwise '&' checks if sumDigits is odd (sumDigits & 1 is 1 if sumDigits is odd),
21    // The '^ 1' inverts the bit, so odd sums return 0, even sums return 1.
22    return sumDigits & 1 ^ 1;
23}
24
25// Example of using the function with an array of numbers
26const result: number = sumOfDigits([34, 23, 1, 24, 75, 33, 54, 8]);
27console.log(result); // Output will be the result according to the sum of digits of minimum element.
28
Not Sure What to Study? Take the 2-min Quiz：

Which two pointer techniques do you use to check if a string is a palindrome?

Time and Space Complexity

The given Python code computes the sum of digits of the smallest number in the list nums and then returns 0 if that sum is odd, or 1 if the sum is even.

Time Complexity

The time complexity of the function sumOfDigits is determined by two separate operations:

  1. Finding the minimum value in nums, which takes O(n) time where n is the number of elements in nums.
  2. Calculating the sum of the digits of the minimum value. In the worst case scenario, the minimum value could have O(log x) digits where x is the value of the minimum element. Therefore, the loop runs at most O(log x) times.

Overall, the time complexity is O(n + log x). However, since n is the dominant factor, we can simplify the overall time complexity to O(n).

Space Complexity

The space complexity of the code is O(1) because the function uses a fixed amount of space: variables x and s are the only additional memory used, and their size does not scale with the input size n.

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

Fast Track Your Learning with Our Quick Skills Quiz:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Recommended Readings

Math Basics

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 - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫