Minimum Total Operations

Minimum Total Operations - Problem

Array Easy

Given an array of integers nums, you can perform any number of operations on this array. In each operation, you can:

Choose a prefix of the array
Choose an integer k (which can be negative) and add k to each element in the chosen prefix

A prefix of an array is a subarray that starts from the beginning of the array and extends to any point within it.

Return the minimum number of operations required to make all elements in the array equal.

Input & Output

Example 1 — Basic Case

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

› Output: 2

💡 Note: Target is 2 (last element). Element at index 1 (value 3) differs from 2, needs 1 operation. Element at index 0 (value 1) differs from 2, needs 1 operation. Total: 2 operations.

Example 2 — Already Equal

$ Input: nums = [2,2,2]

› Output: 0

💡 Note: All elements are already equal to 2, so no operations needed.

Example 3 — Single Element

$ Input: nums = [5]

› Output: 0

💡 Note: Single element array is already equal, requires 0 operations.

Constraints

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

Visualization

Tap to expand

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that we can work backwards from the last element as our target. Each element that differs from the target requires exactly one prefix operation to fix. The greedy approach processes from right to left, counting differences. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(k^n)	O(n)	Try all possible sequences of operations until all elements are equal
Greedy Approach - Right to Left	O(n)	O(1)	Process array from right to left, making each element equal to the target

Brute Force - Try All Combinations — Algorithm Steps

Step 1: Generate all possible operation sequences
Step 2: For each sequence, simulate the operations
Step 3: Check if all elements become equal
Step 4: Return minimum operations needed

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Operations

Create all possible prefix + k combinations

Simulate Each

Apply operations and check if all equal

Find Minimum

Return shortest sequence that works

Code -

solution.c — C

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

int backtrack(int* arr, int size, int operations) {
    int i, j, unique = 1;
    for (i = 1; i < size; i++) {
        if (arr[i] != arr[0]) {
            unique = 0;
            break;
        }
    }
    if (unique) return operations;
    if (operations >= 10) return INT_MAX;
    
    int minOps = INT_MAX;
    
    for (int prefixLen = 1; prefixLen <= size; prefixLen++) {
        for (int k = -100; k <= 100; k += 10) {
            if (k == 0) continue;
            int* newArr = malloc(size * sizeof(int));
            for (i = 0; i < size; i++) {
                newArr[i] = arr[i];
            }
            for (i = 0; i < prefixLen; i++) {
                newArr[i] += k;
            }
            int result = backtrack(newArr, size, operations + 1);
            if (result < minOps) minOps = result;
            free(newArr);
        }
    }
    
    return minOps;
}

int solution(int* nums, int size) {
    int unique = 1;
    for (int i = 1; i < size; i++) {
        if (nums[i] != nums[0]) {
            unique = 0;
            break;
        }
    }
    if (unique) return 0;
    
    return backtrack(nums, size, 0);
}

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

Time & Space Complexity

Time Complexity

⏱️

O(k^n)

Exponential combinations of operations and prefix choices

✓ Linear Growth

Space Complexity

O(n)

Space to store array copies during simulation

⚡ Linearithmic Space

34.7K Views

Medium Frequency

~15 min Avg. Time

890 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