algoadvance

You are given an integer array apples of length n, where apples[i] represents the number of apples in the i-th box.

Your goal is to make all the boxes have the same number of apples by performing the following operations any number of times:

• Choose a box with a non-zero number of apples.
• Choose another box.
• Move one apple from the first box to the second box.

Return true if you can achieve this goal, and false otherwise.

Example

• Example 1:

    Input: apples = [2, 5, 3, 9]
    Output: False
    Explanation: It is not possible to make all the boxes have the same number of apples.
  

• Example 2:

    Input: apples = [3, 3, 3]
    Output: True
    Explanation: All boxes already contain the same number of apples.
  

Clarifying Questions

1. What is the range of the length of the apples array?
2. What is the range of the number of apples in each box?
3. Can the array have negative or zero values?

To simplify, let’s assume:

1. 1 ≤ n ≤ 10^5 (length of the apples array).
2. 0 ≤ apples[i] ≤ 10^9 (number of apples in each box).

Strategy

To solve this problem, consider the following steps:

1. Compute the total number of apples.
2. Check if the total number of apples is divisible by the length of the array n.
3. If divisible, it means we can redistribute the apples equally into each box.
4. If not, return false since we cannot evenly distribute apples into each box.

Prove of Conditions

• If the total number of apples is divisible by n, it means we can evenly distribute them. (Total sum modulo the number of boxes should equal 0).

Time Complexity

• Calculating the sum of the array takes O(n) time.

Code

Here’s a Python function to implement the aforementioned strategy:

def canRedistributeApples(apples):
    total_apples = sum(apples)
    n = len(apples)
    
    # Check if the total number of apples is divisible by the number of boxes
    if total_apples % n == 0:
        return True
    else:
        return False

# Test case
print(canRedistributeApples([2, 5, 3, 9])) # Output: False
print(canRedistributeApples([3, 3, 3]))    # Output: True

Explanation:

• Calculate the total number of apples using sum(apples).
• Calculate the length of the array, n, using len(apples).
• Check if total_apples is divisible by n.
• Return true if divisible, otherwise false.

This algorithm runs in O(n) time where n is the length of the input list apples, which is efficient for the given constraints.

Try our interview co-pilot at AlgoAdvance.com

• 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?