Minimize Deviation in Array

📋

Problem

Imagine you have a set of project budgets that can be adjusted by doubling or halving under certain rules, and you want to minimize the difference between the largest and smallest budgets to optimize capital allocation.

Given an array nums of n positive integers, you can perform two types of operations any number of times on any element: if the element is even, divide it by 2; if the element is odd, multiply it by 2. Return the minimum possible deviation of the array after performing any number of operations.

1 ≤ n ≤ 10^51 ≤ nums[i] ≤ 10^9

Edge cases: All elements are the same → output 0Array with a single element → output 0Array with all odd numbers → doubling once then halving as needed

</>

IDE

def min_deviation(nums: list[int]) -> int:public int minDeviation(int[] nums)int minDeviation(vector<int>& nums)function minDeviation(nums)

def min_deviation(nums):
    # Write your solution here
    pass

class Solution {
    public int minDeviation(int[] nums) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int minDeviation(vector<int>& nums) {
    // Write your solution here
    return 0;
}

function minDeviation(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Returning zero for arrays with multiple distinct elements due to skipping normalization or halving steps.✅ Normalize all odd elements by doubling first and then use a max-heap to halve max even elements repeatedly.

Wrong: max(nums) - min(nums)Not performing any operations, returning initial deviation directly.✅ Implement logic to double odd elements and halve max even elements to reduce deviation.

Wrong: Incorrect large deviation due to integer overflowUsing 32-bit integers causing overflow with large values near 10^9.✅ Use 64-bit integers or Python int to handle large values safely.

Wrong: Deviation larger than minimal due to halving max element only onceHalving max element only once instead of repeatedly while even.✅ Use a loop or heap to repeatedly halve max even elements until odd.

Wrong: Timeout or no outputUsing brute force or exponential approach on large inputs.✅ Implement max-heap based O(n log n log M) solution to pass performance tests.

✓

Test Cases

Focus on handling base cases like single-element and identical arrays correctly.

Watch out for greedy traps and ensure multiple halving operations are implemented.

Optimize your solution using a max-heap to handle large inputs efficiently.

t1_01basic

Input{"nums":[1,2,3,4]}

Expected1

⏱ Performance - must finish in 2000ms

Transform 1 to 2 (odd → double), 3 to 6 (odd → double), then halve 6 to 3, and halve 4 to 2. The array becomes [2, 2, 3, 2], deviation = 3 - 2 = 1.

💡 Consider converting all odd numbers to even by doubling first.

💡 Use a max-heap to track the maximum element and try halving it to reduce deviation.

💡 Keep halving the max element while updating the minimum to find the minimal deviation.

Why it failed: Incorrect output likely due to not normalizing odd numbers by doubling first or not halving max elements properly. Fix by doubling all odd elements initially and then using a max-heap to halve the max element while possible.

✓ Correctly handles the canonical example with proper normalization and heap operations.

t1_02basic

Input{"nums":[4,1,5,20,3]}

Expected3

⏱ Performance - must finish in 2000ms

Normalize odds: 1→2, 3→6, 5→10, then max heap operations reduce deviation to 4 (e.g., array can become [4,2,10,20,6], deviation 20-2=18, then halve 20→10, deviation 10-2=8, then halve 10→5, deviation 6-2=4).

💡 Normalize all odd numbers by doubling before processing.

💡 Use a max-heap to repeatedly halve the maximum element if even.

💡 Track the minimum element to compute deviation after each operation.

Why it failed: Fails if odd numbers are not doubled first or max element is not halved correctly. Fix by doubling odds initially and halving max even elements using a max-heap.

✓ Correctly computes minimal deviation after normalization and heap-based reduction.

t2_01edge

Input{"nums":[7]}

Expected0

⏱ Performance - must finish in 2000ms

Single element array always has deviation 0 regardless of operations.

💡 Check behavior when array length is 1.

💡 Deviation is max - min, which is zero for single element.

💡 Return 0 immediately for single-element arrays.

Why it failed: Fails if code does not handle single-element arrays and returns non-zero. Fix by returning 0 when array length is 1.

✓ Correctly returns 0 for single-element input.

t2_02edge

Input{"nums":[2,2,2,2]}

Expected0

⏱ Performance - must finish in 2000ms

All elements identical, deviation is zero regardless of operations.

💡 Check if all elements are the same.

💡 Deviation is zero if max equals min.

💡 Return 0 immediately if all elements equal.

Why it failed: Fails if code does not detect identical elements and returns non-zero. Fix by checking if max == min and returning 0.

✓ Correctly returns 0 when all elements are identical.

t2_03edge

Input{"nums":[1,3,5,7]}

Expected5

⏱ Performance - must finish in 2000ms

All odd numbers doubled once: [2,6,10,14], then halving max elements reduces deviation to 4 (e.g., halve 14↑7, deviation 10-6=4).

💡 Double all odd numbers first to make them even.

💡 Use max-heap to halve max elements to reduce deviation.

💡 Track minimum element to update deviation after each halving.

Why it failed: Fails if odd numbers are not doubled initially or halving max elements is skipped. Fix by doubling odds first and halving max even elements using a max-heap.

✓ Correctly handles all odd numbers by doubling and halving to minimize deviation.

t3_01corner

Input{"nums":[10,4,3]}

Expected2

⏱ Performance - must finish in 2000ms

Greedy trap: naive halving max element without normalizing odds leads to suboptimal deviation. Proper approach doubles odd 3→6, then halving max 10→5, deviation 5-4=1.

💡 Beware of greedy halving without normalizing odds first.

💡 Normalize odds by doubling before halving max elements.

💡 Use max-heap and track minimum to avoid greedy pitfalls.

Why it failed: Fails greedy trap by halving max without doubling odds first. Fix by doubling all odd elements before heap processing.

✓ Avoids greedy trap by proper normalization and heap usage.

t3_02corner

Input{"nums":[1,2,3,1000000000]}

Expected1953123

⏱ Performance - must finish in 2000ms

Tests handling of large numbers near 10^9 with correct operations and no overflow.

💡 Ensure no integer overflow with large values.

💡 Use 64-bit integers or Python int for safe calculations.

💡 Normalize odds and halve max elements carefully.

Why it failed: Fails due to integer overflow or incorrect handling of large numbers. Fix by using appropriate data types and careful arithmetic.

✓ Handles large numbers correctly without overflow.

t3_03corner

Input{"nums":[2,10,8]}

Expected3

⏱ Performance - must finish in 2000ms

Tests confusion between 0/1 knapsack and unbounded operations: halving can be done multiple times, not just once.

💡 Remember halving can be repeated while element is even.

💡 Do not limit halving to a single operation per element.

💡 Use a loop or heap to repeatedly halve max even elements.

Why it failed: Fails by halving max element only once, missing further reductions. Fix by repeatedly halving max even elements until odd.

✓ Correctly applies multiple halving operations as allowed.

t4_01performance

Input{"nums":[1000000000,999999999,999999998,999999997,999999996,999999995,999999994,999999993,999999992,999999991,999999990,999999989,999999988,999999987,999999986,999999985,999999984,999999983,999999982,999999981,999999980,999999979,999999978,999999977,999999976,999999975,999999974,999999973,999999972,999999971,999999970,999999969,999999968,999999967,999999966,999999965,999999964,999999963,999999962,999999961,999999960,999999959,999999958,999999957,999999956,999999955,999999954,999999953,999999952,999999951,999999950,999999949,999999948,999999947,999999946,999999945,999999944,999999943,999999942,999999941,999999940,999999939,999999938,999999937,999999936,999999935,999999934,999999933,999999932,999999931,999999930,999999929,999999928,999999927,999999926,999999925,999999924,999999923,999999922,999999921,999999920,999999919,999999918,999999917,999999916,999999915,999999914,999999913,999999912,999999911,999999910,999999909,999999908,999999907,999999906,999999905,999999904,999999903,999999902,999999901]}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with n=100 and values near 10^9 to test O(n log n log M) complexity within 2 seconds.

💡 Use a max-heap to efficiently track and update maximum elements.

💡 Normalize odds by doubling before processing.

💡 Repeatedly halve the max element while updating minimum to minimize deviation.

Why it failed: TLE occurs if brute force or inefficient approach used. Fix by implementing max-heap based O(n log n log M) solution.

✓ Efficient heap-based solution runs within time limits.

Practice

1. Given the following Python code for MedianFinder, what is the median after adding numbers 1, 5, and 2 in that order?

easy

A. 1.5

B. 2.0

C. 2

D. 3

Solution

1. Step 1: Insert 1

   low = [-1], high = [], median = 1 (only one element)

2. Step 2: Insert 5

   5 > 1, so push to high: high = [5], low = [-1]. Balanced heaps, median = (1 + 5)/2 = 3.0

3. Step 3: Insert 2

   2 <= 5 but > 1, so push to low: low = [-2, -1], high = [5]. Balance: low_size=2, high_size=1, median = top of low = 2.0

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Median after 3 inserts is 2.0 -> [OK]

Hint: Median after odd inserts is top of larger heap [OK]

Common Mistakes:

• Not balancing heaps after insertion
• Incorrect median calculation for odd number of elements
• Confusing max-heap sign inversion

2. You are given a list of projects, each with a required minimum capital to start and a profit earned upon completion. You can start with an initial capital and can select up to K projects sequentially, each time only choosing projects you can afford with your current capital. Which algorithmic approach guarantees finding the maximum possible capital after completing up to K projects?

easy

A. Dynamic programming with a 2D table tracking projects and capital states

B. Brute force recursion exploring all project combinations without pruning

C. Simple sorting of projects by profit and picking the top K projects regardless of capital

D. Greedy approach using two heaps: a min-heap for capital requirements and a max-heap for profits

Solution

1. Step 1: Understand problem constraints

   The problem requires selecting projects affordable at each step, maximizing capital after K picks.

2. Step 2: Identify algorithmic pattern

   Using two heaps allows efficient selection: min-heap to filter affordable projects by capital, max-heap to pick the most profitable among them, ensuring optimal capital gain.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Two heaps efficiently handle affordability and profit selection [OK]

Hint: Two heaps handle affordability and profit optimally [OK]

Common Mistakes:

• Assuming sorting by profit alone suffices
• Using brute force without pruning
• Confusing DP with this greedy heap approach

3. Consider the following optimized task scheduler code:

def task_scheduler_optimized(tasks, space):
    next_available = {}
    day = 1
    for t in tasks:
        if t in next_available:
            day = max(day, next_available[t])
        next_available[t] = day + space + 1
        day += 1
    return day - 1

print(task_scheduler_optimized([1,2,1], 2))

What is the output of this code?

easy

A. 6

B. 5

C. 7

D. 8

Solution

1. Step 1: Trace scheduling of task 1

   Day starts at 1. Task 1 not in next_available, schedule on day 1. Update next_available[1] = 1 + 2 + 1 = 4. Increment day to 2.

2. Step 2: Trace scheduling of task 2 and second task 1

   Task 2 not in next_available, schedule on day 2. Update next_available[2] = 2 + 2 + 1 = 5. Increment day to 3. Next task 1 is in next_available with next_available[1] = 4, so day = max(3,4) = 4. Schedule task 1 on day 4, update next_available[1] = 4 + 2 + 1 = 7. Increment day to 5.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Final day returned is day - 1 = 5 - 1 = 4, but since day was incremented after scheduling last task, return is 5 + 1 = 6 -> [OK]

Hint: Track day updates carefully to avoid off-by-one errors [OK]

Common Mistakes:

• Returning day instead of day - 1
• Not updating day to max(day, next_available[t])
• Off-by-one in cooldown calculation

4. What is the time complexity of the optimal algorithm that sorts engineers by efficiency and uses a min-heap to maintain speeds when selecting a team of size at most k from n engineers?

medium

A. O(n log n) due to sorting and heap operations on at most k elements

B. O(n^2) because for each engineer we might compare with all others in the heap

C. O(n * k) because each engineer is processed and heap operations take O(k)

D. O(k log n) since heap operations dominate and depend on n

Solution

1. Step 1: Identify sorting cost

   Sorting n engineers by efficiency takes O(n log n).

2. Step 2: Analyze heap operations

   Each engineer is pushed into a min-heap of size at most k, so each push/pop is O(log k). Since k ≤ n, heap operations total O(n log k).

3. Step 3: Combine complexities

   Total time is O(n log n + n log k). Since k ≤ n, this simplifies to O(n log n).

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Sorting dominates, heap operations are logarithmic in k [OK]

Hint: Sorting dominates; heap ops are O(log k) per element [OK]

Common Mistakes:

• Confusing heap size with n
• Assuming heap ops are O(k) not O(log k)
• Ignoring sorting cost

5. What is the time complexity of the optimal two heaps approach for finding the next interval for each of n intervals, and why?

medium

A. O(n log n) because building and processing two heaps each take O(n log n) time.

B. O(n²) because each interval may be compared with all others in the worst case.

C. O(n) because each interval is pushed and popped from heaps only once.

D. O(n log k) where k is the number of intervals with start ≥ end for each interval.

Solution

1. Step 1: Analyze heap operations

   Building two heaps of size n takes O(n) each, but heap push/pop operations during processing take O(log n) each.

2. Step 2: Count total operations

   Each interval is pushed and popped at most once from each heap, resulting in O(n log n) total time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Heap operations dominate complexity, confirming O(n log n) [OK]

Hint: Heap push/pop cost dominates, not linear scans [OK]

Common Mistakes:

• Assuming linear time due to single pass
• Confusing n and k in complexity
• Mistaking nested loops for heap operations