algoadvance

Leetcode 3190. Find Minimum Operations to Make All Elements Divisible by Three

Problem Statement

You are given an array nums of size n. You can perform the following operation on the array any number of times:

• Pick two different indices i and j, and set nums[i] to nums[i] + nums[j].

You need to determine the minimum number of operations required to make all elements of the array divisible by 3.

Clarifying Questions

1. Are there any constraints on the values within the array nums? (e.g., range of values)
2. What should we assume about the size of the array n?
3. Can the values in nums be negative or zero?
4. In the output, if it’s not possible to make all elements divisible by 3, what should be returned?

Code

#include <iostream>
#include <vector>

using namespace std;

int minOperationsToMakeDivisibleByThree(vector<int>& nums) {
    int count_mod1 = 0, count_mod2 = 0;

    for (int num : nums) {
        if (num % 3 == 1) {
            count_mod1++;
        } else if (num % 3 == 2) {
            count_mod2++;
        }
    }

    if (count_mod1 == 0 && count_mod2 == 0) {
        return 0; // All numbers are already divisible by 3
    }

    if (count_mod1 == count_mod2) {
        return count_mod1;
    }

    return max(count_mod1, count_mod2);
}

int main() {
    vector<int> nums = {2, 2, 5, 8};
    cout << minOperationsToMakeDivisibleByThree(nums) << endl;
    return 0;
}

Strategy

1. Count Remainders: First, iterate through the array and count how many numbers leave a remainder of 1 or 2 when divided by 3.
2. Identify the Problem Scope:
   • If there are no numbers with a remainder of 1 and no numbers with a remainder of 2, the array is already in the desired state.
   • If the counts of numbers with remainders 1 and 2 are equal, each pair can solve each other.
   • Otherwise, the maximum number of either count will tell you the minimum operations needed, as one will be larger than the other.

Time Complexity

• The solution involves a single pass through the array to count how many numbers have remainders of 1 and 2. Thus, the time complexity is O(n), where n is the length of the array.
• Space complexity is O(1) because we only use a constant amount of extra space.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?