Good Things Come in Threes - codepath/compsci_guides GitHub Wiki

TIP102 Unit 1 Session 2 Standard (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Easy
• ⏰ Time to complete: 10 mins
• 🛠️ Topics: Modulo Arithmetic, Iteration

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• The function make_divisible_by_3() should take an integer array nums and return the minimum number of operations required to make all elements divisible by 3. Each operation consists of adding or subtracting 1 from any element.

HAPPY CASE
Input: [1, 2, 3, 4]
Expected Output: 3
Explanation: 
- Subtract 1 from 1 to get 0.
- Add 1 to 2 to get 3.
- Subtract 1 from 4 to get 3.

Input: [3, 6, 9]
Expected Output: 0
Explanation: All elements are already divisible by 3.

EDGE CASE
Input: []
Expected Output: 0
Explanation: An empty array requires no operations.

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Define a function that iterates through the array, calculates the remainder when each element is divided by 3, and accumulates the number of operations needed based on the remainder.

1. Define the function `make_divisible_by_3(nums)`.
2. Initialize a variable `operations` to 0.
3. Use a for loop to iterate through each number in `nums`.
4. For each number:
   a. Calculate the remainder when divided by 3.
   b. If the remainder is 1, increment `operations` by 1 (subtract 1).
   c. If the remainder is 2, increment `operations` by 1 (add 1).
5. Return the total `operations`.

⚠️ Common Mistakes

• Forgetting to handle the case where the input list is empty.
• Not correctly identifying the operations needed based on the remainder.

I-mplement

Implement the code to solve the algorithm.

def make_divisible_by_3(nums):
    operations = 0
    for num in nums:
        remainder = num % 3
        if remainder == 1:
            operations += 1  # Subtract 1
        elif remainder == 2:
            operations += 1  # Add 1
    return operations