Minimum Division Operations to Make Array Non Decreasing

Minimum Division Operations to Make Array Non Decreasing - Problem

You are given an integer array nums. Any positive divisor of a natural number x that is strictly less than x is called a proper divisor of x.

For example, 2 is a proper divisor of 4, while 6 is not a proper divisor of 6.

You are allowed to perform an operation any number of times on nums, where in each operation you select any one element from nums and divide it by its greatest proper divisor.

Return the minimum number of operations required to make the array non-decreasing. If it is not possible to make the array non-decreasing using any number of operations, return -1.

Input & Output

Example 1 — Basic Violation

$ Input: nums = [25, 7]

› Output: 1

💡 Note: 25 > 7 violates non-decreasing. 25's greatest proper divisor is 5, so 25 ÷ 5 = 5. Now [5, 7] is non-decreasing with 1 operation.

Example 2 — Multiple Operations

$ Input: nums = [7, 21, 3]

› Output: 2

💡 Note: 21 > 3 violates constraint. 21 ÷ 7 = 3 (1 op), then 7 > 3 so 7 ÷ 7 = 1 (1 op). Total: 2 operations for [1, 3, 3].

Example 3 — Already Non-decreasing

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

› Output: 0

💡 Note: Array is already non-decreasing, no operations needed.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array [25, 7] with violation 25 > 7

Apply Operation

Divide 25 by its greatest proper divisor 5

Result

Array becomes [5, 7] which is non-decreasing

Key Takeaway

🎯 Key Insight: Each number can only be reduced to its smallest prime factor, so we greedily process violations from right to left

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is that each number can only be reduced to its smallest prime factor through repeated divisions by greatest proper divisors. Best approach is the greedy right-to-left strategy that processes violations as we encounter them. Time: O(n * log(max_value)), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with Backtracking	O(k^n)	O(n)	Try all possible combinations of operations on each element
Optimized with Precomputation	O(n * log(max_value))	O(1)	Precompute minimum values for each number, then apply greedy strategy
Greedy Right-to-Left	O(n * log(max_value))	O(1)	Process array from right to left, reducing elements only when necessary

Brute Force with Backtracking — Algorithm Steps

For each position, if current > next, try reducing current
Recursively try all possible operation counts
Return minimum operations needed

Visualization

Tap to expand

Step-by-Step Walkthrough

Original Array

Start with input array [25, 7]

Try Operations

For each element, try 0, 1, 2... operations

Check All Paths

Recursively check if resulting array is non-decreasing

Code -

solution.c — C

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

int getGreatestProperDivisor(int n) {
    if (n <= 1) return 0;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return n / i;
        }
    }
    return 1;
}

int backtrack(int* arr, int size, int pos, int ops) {
    if (pos == size) {
        for (int i = 1; i < size; i++) {
            if (arr[i-1] > arr[i]) {
                return INT_MAX;
            }
        }
        return ops;
    }
    
    int minOps = INT_MAX;
    int current = arr[pos];
    int operations = 0;
    
    while (1) {
        int* newArr = (int*)malloc(size * sizeof(int));
        memcpy(newArr, arr, size * sizeof(int));
        newArr[pos] = current;
        int result = backtrack(newArr, size, pos + 1, ops + operations);
        if (result < minOps) {
            minOps = result;
        }
        free(newArr);
        
        int gpd = getGreatestProperDivisor(current);
        if (gpd <= 1) break;
        current /= gpd;
        operations++;
    }
    
    return minOps;
}

int solution(int* nums, int size) {
    int result = backtrack(nums, size, 0, 0);
    return result == INT_MAX ? -1 : result;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(k^n)

For each element, we try up to k operations where k is logarithmic, but with n elements this becomes exponential

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth proportional to array length

⚡ Linearithmic Space

8.5K Views

Medium Frequency

~25 min Avg. Time

234 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 with Backtracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler