3326. Minimum Division Operations to Make Array Non Decreasing

SourceWeekly Contest 420 Q3DifficultyMediumRating1864

Description

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.

Example 1:

Input: nums = [25,7]

Output: 1

Explanation:

Using a single operation, 25 gets divided by 5 and nums becomes [5, 7].

Example 2:

Input: nums = [7,7,6]

Output: -1

Example 3:

Input: nums = [1,1,1,1]

Output: 0

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁶

Solutions

Solution 1: Preprocessing + Greedy

Thinking

An operation divides \(x\) by a proper divisor. A prime cannot shrink; a composite becomes its least prime factor after one such division. With \(n \le 10^5\) and \(M \le 10^6\) we precompute least prime factors.

Editing from the left would fight constraints that are still unknown. From the right, the next value is already final, so a larger left neighbor must become \(\textit{lpf}[x]\) immediately.

If even the least prime factor exceeds the right neighbor, the array cannot become non-decreasing. Each index is operated on at most once, so one right-to-left pass counts the answer.

According to the problem description,

If an integer \(x\) is a prime number, then its largest proper divisor is \(1\), so \(x / 1 = x\), meaning \(x\) cannot be divided further.

If an integer \(x\) is not a prime number, we assume the largest proper divisor of \(x\) is \(y\), then \(x / y\) must be a prime number. Therefore, we find the smallest prime factor \(\textit{lpf}[x]\) such that \(x \bmod \textit{lpf}[x] = 0\), making \(x\) become \(\textit{lpf}[x]\), at which point it cannot be divided further.

Thus, we can preprocess the smallest prime factor for each integer from \(1\) to \(10^6\). Then, we traverse the array from right to left. If the current element is greater than the next element, we change the current element to its smallest prime factor. If after changing the current element to its smallest prime factor it is still greater than the next element, it means the array cannot be made non-decreasing, and we return \(-1\). Otherwise, we increment the operation count by one. Continue traversing until the entire array is processed.

The time complexity for preprocessing is \(O(M \times \log \log M)\), where \(M = 10^6\). The time complexity for traversing the array is \(O(n)\), where \(n\) is the length of the array. The space complexity is \(O(M)\).

Python3JavaC++GoTypeScript

mx = 10**6 + 1
lpf = [0] * (mx + 1)
for i in range(2, mx + 1):
    if lpf[i] == 0:
        for j in range(i, mx + 1, i):
            if lpf[j] == 0:
                lpf[j] = i


class Solution:
    def minOperations(self, nums: List[int]) -> int:
        ans = 0
        for i in range(len(nums) - 2, -1, -1):
            if nums[i] > nums[i + 1]:
                nums[i] = lpf[nums[i]]
                if nums[i] > nums[i + 1]:
                    return -1
                ans += 1
        return ans

class Solution {
    private static final int MX = (int) 1e6 + 1;
    private static final int[] LPF = new int[MX + 1];
    static {
        for (int i = 2; i <= MX; ++i) {
            for (int j = i; j <= MX; j += i) {
                if (LPF[j] == 0) {
                    LPF[j] = i;
                }
            }
        }
    }
    public int minOperations(int[] nums) {
        int ans = 0;
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] > nums[i + 1]) {
                nums[i] = LPF[nums[i]];
                if (nums[i] > nums[i + 1]) {
                    return -1;
                }
                ans++;
            }
        }
        return ans;
    }
}

const int MX = 1e6;
int LPF[MX + 1];

auto init = [] {
    for (int i = 2; i <= MX; i++) {
        if (LPF[i] == 0) {
            for (int j = i; j <= MX; j += i) {
                if (LPF[j] == 0) {
                    LPF[j] = i;
                }
            }
        }
    }
    return 0;
}();

class Solution {
public:
    int minOperations(vector<int>& nums) {
        int ans = 0;
        for (int i = nums.size() - 2; i >= 0; i--) {
            if (nums[i] > nums[i + 1]) {
                nums[i] = LPF[nums[i]];
                if (nums[i] > nums[i + 1]) {
                    return -1;
                }
                ans++;
            }
        }
        return ans;
    }
};

const mx int = 1e6

var lpf = [mx + 1]int{}

func init() {
    for i := 2; i <= mx; i++ {
        if lpf[i] == 0 {
            for j := i; j <= mx; j += i {
                if lpf[j] == 0 {
                    lpf[j] = i
                }
            }
        }
    }
}

func minOperations(nums []int) (ans int) {
    for i := len(nums) - 2; i >= 0; i-- {
        if nums[i] > nums[i+1] {
            nums[i] = lpf[nums[i]]
            if nums[i] > nums[i+1] {
                return -1
            }
            ans++
        }
    }
    return
}

const mx = 10 ** 6;
const lpf = Array(mx + 1).fill(0);
for (let i = 2; i <= mx; ++i) {
    for (let j = i; j <= mx; j += i) {
        if (lpf[j] === 0) {
            lpf[j] = i;
        }
    }
}

function minOperations(nums: number[]): number {
    let ans = 0;
    for (let i = nums.length - 2; ~i; --i) {
        if (nums[i] > nums[i + 1]) {
            nums[i] = lpf[nums[i]];
            if (nums[i] > nums[i + 1]) {
                return -1;
            }
            ++ans;
        }
    }
    return ans;
}

3326. Minimum Division Operations to Make Array Non Decreasing

Description

Solutions

Solution 1: Preprocessing + Greedy

Comments