We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Minimum Operations to Make All Elements Divisible by Three

Number: 3476

Difficulty: Easy

Paid? No

Companies: tcs

Problem Description

Given an integer array nums, you can add or subtract 1 from any element in one operation. Determine the minimum number of operations required so that every element in the array is divisible by 3.

Key Insights

  • Each element can be adjusted independently since the operations do not affect other elements.
  • For any number:
    • If it is already divisible by 3 (num % 3 == 0), no operations are needed.
    • If num % 3 == 1, subtracting 1 makes it divisible by 3.
    • If num % 3 == 2, adding 1 makes it divisible by 3.
  • Therefore, for every element that is not divisible by 3, only one operation is required.

Space and Time Complexity

Time Complexity: O(n) where n is the number of elements in nums. Space Complexity: O(1) extra space is used.

Solution

We iterate through the array and check the remainder when each element is divided by 3. For every element that is not divisible by 3 (i.e., remainder equals 1 or 2), we increment our operation count by 1. The overall number of operations is simply the number of elements with a non-zero remainder.

The main data structure used here is the array itself and a simple counter variable. The algorithmic approach is a single pass through the list (linear scan). No complex data structures or advanced algorithms are needed, as the problem reduces to checking a simple condition for each element.

Code Solutions

# Function to calculate the minimum operations required
def minOperations(nums):
    operations = 0  # Counter for required operations
    # Iterate through each number in the list
    for num in nums:
        # If the number is not divisible by 3, increment the operations counter
        if num % 3 != 0:
            operations += 1
    return operations

# Example usage:
nums = [1, 2, 3, 4]
print(minOperations(nums))  # Expected output: 3
← Back to All Questions