Jobs

Interviews

Discussions

Sum of Unique Elements

Easy

Asked by:

More companies

75 views

Topics:

Arrays

You are given an integer array nums. The unique elements of an array are the elements that appear exactly once in the array.

Return the sum of all the unique elements of nums.

Example 1:

Input: nums = [1,2,3,2]
Output: 4
Explanation: The unique elements are [1,3], and the sum is 4.

Example 2:

Input: nums = [1,1,1,1,1]
Output: 0
Explanation: There are no unique elements, and the sum is 0.

Example 3:

Input: nums = [1,2,3,4,5]
Output: 15
Explanation: The unique elements are [1,2,3,4,5], and the sum is 15.

Constraints:

1 <= nums.length <= 100
1 <= nums[i] <= 100

Try coding it in LeetCode

Sum of Unique Elements

Easy

Asked by:

75 views

Topics:

Arrays

You are given an integer array nums. The unique elements of an array are the elements that appear exactly once in the array.

Return the sum of all the unique elements of nums.

Example 1:

Input: nums = [1,2,3,2]
Output: 4
Explanation: The unique elements are [1,3], and the sum is 4.

Example 2:

Input: nums = [1,1,1,1,1]
Output: 0
Explanation: There are no unique elements, and the sum is 0.

Example 3:

Input: nums = [1,2,3,4,5]
Output: 15
Explanation: The unique elements are [1,2,3,4,5], and the sum is 15.

Constraints:

1 <= nums.length <= 100
1 <= nums[i] <= 100

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values within the input array? Can the numbers be negative, zero, or only positive?
What should I return if the input array is empty or contains only duplicate elements?
What data type should the input array be? Is it guaranteed to be an array of integers?
Are there any memory constraints that I should consider, given the size of the input array?
If the input array contains a large number of duplicates, what is the expected behavior in terms of time complexity?

Brute Force Solution

Approach

Imagine you have a list of numbers and want to find the sum of only the numbers that appear exactly once. The brute force way is to look at each number and then carefully check how many times it appears in the whole list. We then add it to our sum if it appears only once.

Here's how the algorithm would work step-by-step:

Start with a total sum of zero.
Pick the first number from the list.
Go through the entire list and count how many times this number shows up.
If the number appears only one time, then add this number to our total sum.
Now, pick the second number from the list and repeat the counting process.
Again, if the number appears only one time, then add this number to our total sum.
Continue this process for every number in the list, making sure to add it to the total sum only if it's unique.
Once you have gone through every number in the list, the total sum is your final answer.

Code Implementation

def sum_of_unique_elements_brute_force(numbers):
    total_sum = 0

    for number_index in range(len(numbers)):
        current_number = numbers[number_index]
        frequency = 0

        # Iterate through the list to count occurrences
        for inner_number_index in range(len(numbers)):
            if numbers[inner_number_index] == current_number:
                frequency += 1

        # Add to sum only if the number appears once
        if frequency == 1:
            total_sum += current_number

    return total_sum

Big(O) Analysis

Time Complexity

O(n²) – The given approach iterates through the input array of size 'n'. For each element, it iterates through the entire array again to count the occurrences of that element. Therefore, for each of the 'n' elements, there is an inner loop that iterates up to 'n' times. This results in approximately n*n operations. Hence, the time complexity is O(n²).

Space Complexity

O(1) – The provided algorithm calculates the sum of unique elements by iterating through the input list multiple times. It uses a single variable to store the total sum and another to count the occurrences of each element. No auxiliary data structures, like temporary lists or hash maps, are created. Therefore, the space used remains constant regardless of the input size N, where N is the number of elements in the list, resulting in O(1) space complexity.

Optimal Solution

Approach

To find the sum of only the unique numbers, we'll keep track of how many times each number appears. We'll then add only the numbers that appear exactly once to our total sum.

Here's how the algorithm would work step-by-step:

First, examine each number in the input.
As you look at each number, record how many times you've seen it.
After looking at all the numbers, check your records to see which numbers you only saw once.
Add together all the numbers you saw only once. This is the sum of the unique elements.

Code Implementation

def sum_of_unique(numbers):
    number_counts = {}

    for number in numbers:
        number_counts[number] = number_counts.get(number, 0) + 1

    sum_of_unique_numbers = 0

    # Iterate through counts to identify unique numbers
    for number, count in number_counts.items():
        
        # Only add numbers that appeared exactly once
        if count == 1:
            sum_of_unique_numbers += number

    return sum_of_unique_numbers

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array of size n to count the frequency of each number. This takes O(n) time. Then, it iterates through the frequency map (which has at most n unique elements) to calculate the sum of elements that appeared only once, which also takes O(n) time in the worst case. Therefore, the overall time complexity is O(n) + O(n), which simplifies to O(n).

Space Complexity

O(N) – The algorithm uses a data structure (implied to be a hash map or an array) to record the frequency of each number. In the worst-case scenario, all N numbers in the input are unique, requiring the algorithm to store the count for each of these N numbers. Therefore, the auxiliary space used grows linearly with the input size N. This frequency counter contributes O(N) to the space complexity.

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 if the input array is null or empty as there are no elements to sum.
Array with a single element	Return the single element itself since it is unique by default.
Array with all identical elements	Return 0 since no element is unique.
Array with negative numbers	The solution should correctly handle negative numbers by adding them to the sum if they appear only once.
Array with zero(s)	Zeroes should be treated as any other number and included in the sum if unique.
Array with large numbers causing potential overflow	Use a data type with a larger range (e.g., long) to store the sum to prevent integer overflow.
Array with duplicate values scattered throughout	The solution should correctly identify and sum only the unique elements regardless of their position in the array.
Array with maximum integer value	The solution must properly process the maximum integer value as a valid element, contributing to the total sum if unique.

Null or empty input array

How to Handle:

Return 0 if the input array is null or empty as there are no elements to sum.

Array with a single element

How to Handle:

Return the single element itself since it is unique by default.

Array with all identical elements

How to Handle:

Return 0 since no element is unique.

Array with negative numbers

How to Handle:

The solution should correctly handle negative numbers by adding them to the sum if they appear only once.

Array with zero(s)

How to Handle:

Zeroes should be treated as any other number and included in the sum if unique.

Array with large numbers causing potential overflow

How to Handle:

Use a data type with a larger range (e.g., long) to store the sum to prevent integer overflow.

Array with duplicate values scattered throughout

How to Handle:

The solution should correctly identify and sum only the unique elements regardless of their position in the array.

Array with maximum integer value

How to Handle:

The solution must properly process the maximum integer value as a valid element, contributing to the total sum if unique.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values within the input array? Can the numbers be negative, zero, or only positive?
What should I return if the input array is empty or contains only duplicate elements?
What data type should the input array be? Is it guaranteed to be an array of integers?
Are there any memory constraints that I should consider, given the size of the input array?
If the input array contains a large number of duplicates, what is the expected behavior in terms of time complexity?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with a total sum of zero.
Pick the first number from the list.
Go through the entire list and count how many times this number shows up.
If the number appears only one time, then add this number to our total sum.
Now, pick the second number from the list and repeat the counting process.
Again, if the number appears only one time, then add this number to our total sum.
Continue this process for every number in the list, making sure to add it to the total sum only if it's unique.
Once you have gone through every number in the list, the total sum is your final answer.

Code Implementation

def sum_of_unique_elements_brute_force(numbers):
    total_sum = 0

    for number_index in range(len(numbers)):
        current_number = numbers[number_index]
        frequency = 0

        # Iterate through the list to count occurrences
        for inner_number_index in range(len(numbers)):
            if numbers[inner_number_index] == current_number:
                frequency += 1

        # Add to sum only if the number appears once
        if frequency == 1:
            total_sum += current_number

    return total_sum

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

To find the sum of only the unique numbers, we'll keep track of how many times each number appears. We'll then add only the numbers that appear exactly once to our total sum.

Here's how the algorithm would work step-by-step:

First, examine each number in the input.
As you look at each number, record how many times you've seen it.
After looking at all the numbers, check your records to see which numbers you only saw once.
Add together all the numbers you saw only once. This is the sum of the unique elements.

Code Implementation

def sum_of_unique(numbers):
    number_counts = {}

    for number in numbers:
        number_counts[number] = number_counts.get(number, 0) + 1

    sum_of_unique_numbers = 0

    # Iterate through counts to identify unique numbers
    for number, count in number_counts.items():
        
        # Only add numbers that appeared exactly once
        if count == 1:
            sum_of_unique_numbers += number

    return sum_of_unique_numbers

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 if the input array is null or empty as there are no elements to sum.
Array with a single element	Return the single element itself since it is unique by default.
Array with all identical elements	Return 0 since no element is unique.
Array with negative numbers	The solution should correctly handle negative numbers by adding them to the sum if they appear only once.
Array with zero(s)	Zeroes should be treated as any other number and included in the sum if unique.
Array with large numbers causing potential overflow	Use a data type with a larger range (e.g., long) to store the sum to prevent integer overflow.
Array with duplicate values scattered throughout	The solution should correctly identify and sum only the unique elements regardless of their position in the array.
Array with maximum integer value	The solution must properly process the maximum integer value as a valid element, contributing to the total sum if unique.

Null or empty input array

How to Handle:

Return 0 if the input array is null or empty as there are no elements to sum.

Array with a single element

How to Handle:

Return the single element itself since it is unique by default.

Array with all identical elements

How to Handle:

Return 0 since no element is unique.

Array with negative numbers

How to Handle:

The solution should correctly handle negative numbers by adding them to the sum if they appear only once.

Array with zero(s)

How to Handle:

Zeroes should be treated as any other number and included in the sum if unique.

Array with large numbers causing potential overflow

How to Handle:

Use a data type with a larger range (e.g., long) to store the sum to prevent integer overflow.

Array with duplicate values scattered throughout

How to Handle:

The solution should correctly identify and sum only the unique elements regardless of their position in the array.

Array with maximum integer value

How to Handle:

The solution must properly process the maximum integer value as a valid element, contributing to the total sum if unique.