Minimize Deviation in Array - Practice Coding Problems

Minimize Deviation in Array - Problem

You are given an array nums of n positive integers.

You can perform two types of operations on any element of the array any number of times:

If the element is even, divide it by 2.
If the element is odd, multiply it by 2.

The deviation of the array is the maximum difference between any two elements in the array.

Return the minimum deviation the array can have after performing some number of operations.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2,3,4]

› Output: 1

💡 Note: Convert 1→2, 3→6. Array becomes [2,2,6,4]. Then reduce 6→3, 4→2. Final: [2,2,3,2]. Deviation = 3-2 = 1.

Example 2 — All Odds

$ Input: nums = [4,1,5,20,3]

› Output: 3

💡 Note: Convert odds: 1→2, 5→10, 3→6. Array: [4,2,10,20,6]. After optimal reductions: deviation is 3.

Example 3 — Single Element

$ Input: nums = [2]

› Output: 0

💡 Note: Only one element, so deviation is 0.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Array

[1,2,3,4] with operations: odd×2, even÷2

Transform Strategy

Convert odds to evens, then reduce largest elements

Optimal Result

Minimum possible deviation = 1

Key Takeaway

🎯 Key Insight: Convert all odds to evens first, then greedily reduce the maximum element until optimal

Asked in

G Google 45 a Amazon 32 f Facebook 28

The key insight is to first convert all odd numbers to even (by multiplying by 2), then use a max-heap to greedily reduce the largest elements until no more reductions are possible. The optimal approach uses a heap-based greedy strategy with Time: O(n log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(2^n)	O(2^n)	Generate all possible arrays by trying every combination of operations
Heap-Based Greedy Approach	O(n log n)	O(n)	Maximize all odds first, then use max-heap to minimize deviation by reducing largest elements

Brute Force - Try All Combinations — Algorithm Steps

Generate all possible values for each element
Try every combination of values
Calculate deviation for each combination
Return minimum deviation found

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Values

For each number, find all possible values through operations

Try Combinations

Test every possible combination of values

Find Minimum

Calculate deviation for each and find minimum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int* getAllValues(int num, int* size) {
    int* values = malloc(32 * sizeof(int));
    int count = 0;
    
    if (num % 2 == 1) {
        values[count++] = num;
        values[count++] = num * 2;
        int temp = num * 2;
        while (temp % 2 == 0) {
            temp /= 2;
            values[count++] = temp;
        }
    } else {
        values[count++] = num;
        int temp = num;
        while (temp % 2 == 0) {
            temp /= 2;
            values[count++] = temp;
        }
    }
    
    *size = count;
    return values;
}

int findMin(int* arr, int size) {
    int min = arr[0];
    for (int i = 1; i < size; i++) {
        if (arr[i] < min) min = arr[i];
    }
    return min;
}

int findMax(int* arr, int size) {
    int max = arr[0];
    for (int i = 1; i < size; i++) {
        if (arr[i] > max) max = arr[i];
    }
    return max;
}

int generateCombinations(int** possibilities, int* sizes, int numsSize, int index, int* current) {
    if (index == numsSize) {
        int max = findMax(current, numsSize);
        int min = findMin(current, numsSize);
        return max - min;
    }
    
    int minDeviation = INT_MAX;
    for (int i = 0; i < sizes[index]; i++) {
        current[index] = possibilities[index][i];
        int dev = generateCombinations(possibilities, sizes, numsSize, index + 1, current);
        if (dev < minDeviation) {
            minDeviation = dev;
        }
    }
    
    return minDeviation;
}

int solution(int* nums, int numsSize) {
    int** allPossibilities = malloc(numsSize * sizeof(int*));
    int* sizes = malloc(numsSize * sizeof(int));
    
    for (int i = 0; i < numsSize; i++) {
        allPossibilities[i] = getAllValues(nums[i], &sizes[i]);
    }
    
    int* current = malloc(numsSize * sizeof(int));
    int result = generateCombinations(allPossibilities, sizes, numsSize, 0, current);
    
    for (int i = 0; i < numsSize; i++) {
        free(allPossibilities[i]);
    }
    free(allPossibilities);
    free(sizes);
    free(current);
    
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nums[100];
    int numsSize = 0;
    
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(nums, numsSize);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

Each element can have multiple possible values, leading to exponential combinations

⚠ Quadratic Growth

Space Complexity

O(2^n)

Need to store all possible combinations

⚠ Quadratic Space

38.2K Views

Medium Frequency

~25 min Avg. Time

1.6K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler