Jobs

Interviews

Discussions

Find Minimum Operations to Make All Elements Divisible by Three

Easy

Asked by:

24 views

Topics:

ArraysGreedy Algorithms

You are given an integer array nums. In one operation, you can add or subtract 1 from any element of nums.

Return the minimum number of operations to make all elements of nums divisible by 3.

Example 1:

Input: nums = [1,2,3,4]

Output: 3

Explanation:

All array elements can be made divisible by 3 using 3 operations:

Subtract 1 from 1.
Add 1 to 2.
Subtract 1 from 4.

Example 2:

Input: nums = [3,6,9]

Output: 0

Constraints:

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

Try coding it in LeetCode

Find Minimum Operations to Make All Elements Divisible by Three

Easy

Asked by:

24 views

Topics:

ArraysGreedy Algorithms

You are given an integer array nums. In one operation, you can add or subtract 1 from any element of nums.

Return the minimum number of operations to make all elements of nums divisible by 3.

Example 1:

Input: nums = [1,2,3,4]

Output: 3

Explanation:

All array elements can be made divisible by 3 using 3 operations:

Subtract 1 from 1.
Add 1 to 2.
Subtract 1 from 4.

Example 2:

Input: nums = [3,6,9]

Output: 0

Constraints:

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

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 for elements in the input array? Can they be negative or zero?
What should I return if it's impossible to make all elements divisible by three?
Is the input array guaranteed to be non-empty?
Are there any constraints on the number of operations I can perform?
Can you provide an example of a valid input and the expected output?

Brute Force Solution

Approach

The brute force approach to making all numbers divisible by three involves trying every possible combination of adding one or two to each number. We systematically check if a combination makes all numbers divisible by three, and if so, count the operations.

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

Consider each number in the set, one at a time.
For each number, we can either leave it as is, add one to it, or add two to it. These are our options.
Start by assuming we don't add anything to any number. Check if all the numbers are now divisible by three. If they are, we're done, and the number of operations is zero.
Now, try adding one to the first number only. Check if all numbers are divisible by three. Record the number of operations (which is 1 in this case).
Then try adding two to the first number only. Check again and record if needed.
Next, try adding one to the second number only, and then two to the second number only. Do this for every number individually.
Now, start combining operations. Try adding one to the first number AND one to the second number. Then one to the first AND two to the second, and so on. Check divisibility and record.
Keep trying every single possible combination of adding zero, one, or two to each number in the set.
For each combination, count how many 'add one' or 'add two' operations we used.
Of all the combinations that make every number divisible by three, find the one that used the fewest operations. That's our answer.

Code Implementation

def find_minimum_operations_brute_force(numbers):
    minimum_operations = float('inf')

    # Iterate through all possible combinations of adding 0, 1, or 2 to each number
    for i in range(3 ** len(numbers)):
        operations_count = 0
        temp_numbers = []
        combination_value = i

        for number in numbers:
            addition_value = combination_value % 3
            combination_value //= 3
            temp_numbers.append(number + addition_value)
            operations_count += addition_value

        # Check if all numbers are divisible by three
        all_divisible = True
        for temp_number in temp_numbers:
            if temp_number % 3 != 0:
                all_divisible = False
                break

        #If all numbers are divisible, update the minimum operation
        if all_divisible:

            # We found a working combination! Compare number of operations.
            minimum_operations = min(minimum_operations, operations_count)

    if minimum_operations == float('inf'):
        return -1
    else:

        # If no operations are required, return 0; otherwise, minimum operations
        return minimum_operations

Big(O) Analysis

Time Complexity

O(3^n) – The brute force approach explores all possible combinations of adding 0, 1, or 2 to each of the n numbers. For each number, we have 3 choices, leading to 3 * 3 * ... * 3 (n times) total combinations. Each combination requires checking if all numbers are divisible by three, which takes O(n) time. However, the number of combinations, 3^n, dominates the time complexity. Therefore, the overall time complexity is O(3^n * n), which can be simplified to O(3^n) because the exponential term grows much faster than the linear term.

Space Complexity

O(1) – The brute-force approach, as described, primarily iterates and checks divisibility using a fixed number of variables. While exploring combinations, it doesn't explicitly store all combinations in a separate data structure. It checks each combination in place. Therefore, the space required remains constant irrespective of the input size N (number of elements in the input), leading to a space complexity of O(1).

Optimal Solution

Approach

The core idea is to figure out if we can make all numbers in the set divisible by three with the fewest moves possible. We focus on the remainders when each number is divided by three, and use that information to intelligently decide which numbers to change and how.

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

First, find the remainder when each number is divided by three. The remainders can only be 0, 1, or 2.
Count how many numbers have a remainder of 1 and how many have a remainder of 2.
If all numbers are already divisible by three (all remainders are zero), then no operations are needed.
If there are remainders, consider the case where we only have numbers with a remainder of 1. We can either change one of these numbers into a number divisible by three (one operation), or combine three of these numbers (three operations) to make their sum divisible by three. Pick the single operation if possible.
Similarly, if we only have numbers with a remainder of 2, we can either change one to zero (one operation), or combine three to make their sum divisible by three. Pick the single operation if possible.
If we have both remainders of 1 and 2, we need to make groups of them that can turn into multiples of 3. One number with a remainder of 1 and one number with a remainder of 2 will add up to a number divisible by 3 (1 + 2 = 3). Pair them off to eliminate them with two moves per pair.
After pairing them off, you might have leftover remainders of either all 1's or all 2's. Now you can repeat the strategy from steps 4 and 5. Change a leftover number or combine groups of three to make their sum a multiple of 3
The minimum number of operations is the total number of individual changes and group combinations you needed to make.

Code Implementation

def find_minimum_operations(numbers):
    remainder_one_count = 0
    remainder_two_count = 0

    for number in numbers:
        remainder = number % 3
        if remainder == 1:
            remainder_one_count += 1
        elif remainder == 2:
            remainder_two_count += 1

    if remainder_one_count == 0 and remainder_two_count == 0:
        return 0

    operations = 0
    # Pair off remainders of 1 and 2
    operations += min(remainder_one_count, remainder_two_count)
    remainder_one_count -= min(remainder_one_count, remainder_two_count)
    remainder_two_count -= min(remainder_one_count, remainder_two_count)

    # Handle remaining 1s. We prioritize using a single move if possible
    if remainder_one_count > 0:
        operations += remainder_one_count // 3
        remainder_one_count %= 3

        if remainder_one_count > 0:

            operations += remainder_one_count

    # Handle remaining 2s. We prioritize using a single move if possible
    if remainder_two_count > 0:
        operations += remainder_two_count // 3
        remainder_two_count %= 3

        if remainder_two_count > 0:

            operations += remainder_two_count

    return operations

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array once to count the number of elements with remainders 0, 1, and 2 when divided by 3. This step takes O(n) time. After counting, the algorithm performs a fixed number of arithmetic and comparison operations to determine the minimum operations, which takes constant O(1) time. Therefore, the overall time complexity is dominated by the initial iteration through the array, resulting in O(n) time complexity.

Space Complexity

O(1) – The algorithm primarily uses two counter variables to store the counts of remainders 1 and 2. These counters require constant space, irrespective of the number of elements in the input. There are no auxiliary data structures like lists, maps, or recursion involved that scale with the input size N (where N is the number of elements). Thus, the space complexity is constant.

Edge Cases

Case	How to Handle
Empty or null input array	Return 0 immediately as no operations are needed on an empty array.
Array with only one element	If the single element is divisible by 3, return 0, otherwise return 1 or 2 depending on remainder.
All elements are already divisible by 3	Return 0, as no operations are needed.
Array contains very large numbers (potential integer overflow when calculating operations)	Use modulo operator (%) within calculations to prevent overflow, working with remainders instead of potentially overflowing numbers.
Array contains negative numbers	Take the absolute value of the number before calculating the number of operations needed to make it divisible by 3.
A mix of numbers that require 1 operation and numbers that require 2 operations	Strategically combine numbers that require 1 and 2 operations to create a number divisible by 3 with the minimum operations.
No solution exists, i.e., it's impossible to make all numbers divisible by 3	This should not happen, as there is always a solution of at most 2 operations on each number; therefore, this is not an explicit failure case.
Array contains only numbers that require the same number of operations (all 1 or all 2)	Calculate the minimum number of operations required to make elements divisible by 3 and return it.

Empty or null input array

How to Handle:

Return 0 immediately as no operations are needed on an empty array.

Array with only one element

How to Handle:

If the single element is divisible by 3, return 0, otherwise return 1 or 2 depending on remainder.

All elements are already divisible by 3

How to Handle:

Return 0, as no operations are needed.

Array contains very large numbers (potential integer overflow when calculating operations)

How to Handle:

Use modulo operator (%) within calculations to prevent overflow, working with remainders instead of potentially overflowing numbers.

Array contains negative numbers

How to Handle:

Take the absolute value of the number before calculating the number of operations needed to make it divisible by 3.

A mix of numbers that require 1 operation and numbers that require 2 operations

How to Handle:

Strategically combine numbers that require 1 and 2 operations to create a number divisible by 3 with the minimum operations.

No solution exists, i.e., it's impossible to make all numbers divisible by 3

How to Handle:

This should not happen, as there is always a solution of at most 2 operations on each number; therefore, this is not an explicit failure case.

Array contains only numbers that require the same number of operations (all 1 or all 2)

How to Handle:

Calculate the minimum number of operations required to make elements divisible by 3 and return it.

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 for elements in the input array? Can they be negative or zero?
What should I return if it's impossible to make all elements divisible by three?
Is the input array guaranteed to be non-empty?
Are there any constraints on the number of operations I can perform?
Can you provide an example of a valid input and the expected output?

Brute Force Solution

Approach

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

Consider each number in the set, one at a time.
For each number, we can either leave it as is, add one to it, or add two to it. These are our options.
Start by assuming we don't add anything to any number. Check if all the numbers are now divisible by three. If they are, we're done, and the number of operations is zero.
Now, try adding one to the first number only. Check if all numbers are divisible by three. Record the number of operations (which is 1 in this case).
Then try adding two to the first number only. Check again and record if needed.
Next, try adding one to the second number only, and then two to the second number only. Do this for every number individually.
Now, start combining operations. Try adding one to the first number AND one to the second number. Then one to the first AND two to the second, and so on. Check divisibility and record.
Keep trying every single possible combination of adding zero, one, or two to each number in the set.
For each combination, count how many 'add one' or 'add two' operations we used.
Of all the combinations that make every number divisible by three, find the one that used the fewest operations. That's our answer.

Code Implementation

def find_minimum_operations_brute_force(numbers):
    minimum_operations = float('inf')

    # Iterate through all possible combinations of adding 0, 1, or 2 to each number
    for i in range(3 ** len(numbers)):
        operations_count = 0
        temp_numbers = []
        combination_value = i

        for number in numbers:
            addition_value = combination_value % 3
            combination_value //= 3
            temp_numbers.append(number + addition_value)
            operations_count += addition_value

        # Check if all numbers are divisible by three
        all_divisible = True
        for temp_number in temp_numbers:
            if temp_number % 3 != 0:
                all_divisible = False
                break

        #If all numbers are divisible, update the minimum operation
        if all_divisible:

            # We found a working combination! Compare number of operations.
            minimum_operations = min(minimum_operations, operations_count)

    if minimum_operations == float('inf'):
        return -1
    else:

        # If no operations are required, return 0; otherwise, minimum operations
        return minimum_operations

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, find the remainder when each number is divided by three. The remainders can only be 0, 1, or 2.
Count how many numbers have a remainder of 1 and how many have a remainder of 2.
If all numbers are already divisible by three (all remainders are zero), then no operations are needed.
If there are remainders, consider the case where we only have numbers with a remainder of 1. We can either change one of these numbers into a number divisible by three (one operation), or combine three of these numbers (three operations) to make their sum divisible by three. Pick the single operation if possible.
Similarly, if we only have numbers with a remainder of 2, we can either change one to zero (one operation), or combine three to make their sum divisible by three. Pick the single operation if possible.
If we have both remainders of 1 and 2, we need to make groups of them that can turn into multiples of 3. One number with a remainder of 1 and one number with a remainder of 2 will add up to a number divisible by 3 (1 + 2 = 3). Pair them off to eliminate them with two moves per pair.
After pairing them off, you might have leftover remainders of either all 1's or all 2's. Now you can repeat the strategy from steps 4 and 5. Change a leftover number or combine groups of three to make their sum a multiple of 3
The minimum number of operations is the total number of individual changes and group combinations you needed to make.

Code Implementation

def find_minimum_operations(numbers):
    remainder_one_count = 0
    remainder_two_count = 0

    for number in numbers:
        remainder = number % 3
        if remainder == 1:
            remainder_one_count += 1
        elif remainder == 2:
            remainder_two_count += 1

    if remainder_one_count == 0 and remainder_two_count == 0:
        return 0

    operations = 0
    # Pair off remainders of 1 and 2
    operations += min(remainder_one_count, remainder_two_count)
    remainder_one_count -= min(remainder_one_count, remainder_two_count)
    remainder_two_count -= min(remainder_one_count, remainder_two_count)

    # Handle remaining 1s. We prioritize using a single move if possible
    if remainder_one_count > 0:
        operations += remainder_one_count // 3
        remainder_one_count %= 3

        if remainder_one_count > 0:

            operations += remainder_one_count

    # Handle remaining 2s. We prioritize using a single move if possible
    if remainder_two_count > 0:
        operations += remainder_two_count // 3
        remainder_two_count %= 3

        if remainder_two_count > 0:

            operations += remainder_two_count

    return operations

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty or null input array	Return 0 immediately as no operations are needed on an empty array.
Array with only one element	If the single element is divisible by 3, return 0, otherwise return 1 or 2 depending on remainder.
All elements are already divisible by 3	Return 0, as no operations are needed.
Array contains very large numbers (potential integer overflow when calculating operations)	Use modulo operator (%) within calculations to prevent overflow, working with remainders instead of potentially overflowing numbers.
Array contains negative numbers	Take the absolute value of the number before calculating the number of operations needed to make it divisible by 3.
A mix of numbers that require 1 operation and numbers that require 2 operations	Strategically combine numbers that require 1 and 2 operations to create a number divisible by 3 with the minimum operations.
No solution exists, i.e., it's impossible to make all numbers divisible by 3	This should not happen, as there is always a solution of at most 2 operations on each number; therefore, this is not an explicit failure case.
Array contains only numbers that require the same number of operations (all 1 or all 2)	Calculate the minimum number of operations required to make elements divisible by 3 and return it.

Empty or null input array

How to Handle:

Return 0 immediately as no operations are needed on an empty array.

Array with only one element

How to Handle:

If the single element is divisible by 3, return 0, otherwise return 1 or 2 depending on remainder.

All elements are already divisible by 3

How to Handle:

Return 0, as no operations are needed.

Array contains very large numbers (potential integer overflow when calculating operations)

How to Handle:

Use modulo operator (%) within calculations to prevent overflow, working with remainders instead of potentially overflowing numbers.

Array contains negative numbers

How to Handle:

Take the absolute value of the number before calculating the number of operations needed to make it divisible by 3.

A mix of numbers that require 1 operation and numbers that require 2 operations

How to Handle:

Strategically combine numbers that require 1 and 2 operations to create a number divisible by 3 with the minimum operations.

No solution exists, i.e., it's impossible to make all numbers divisible by 3

How to Handle:

This should not happen, as there is always a solution of at most 2 operations on each number; therefore, this is not an explicit failure case.

Array contains only numbers that require the same number of operations (all 1 or all 2)

How to Handle:

Calculate the minimum number of operations required to make elements divisible by 3 and return it.