3326. Minimum Division Operations to Make Array Non Decreasing - Medium

前往題目

想法

• 從後往前，遇到invalid的地方去試所有可行的divisor，找不到就是-1

思路

這題是weekly contest差一點就寫出來了，TLE，應該是找divisor那邊太花時間

1. 從後往前，因為最後一個是基準
2. 循環過程中，遇到invalid的部分，嘗試把前數除到比後數小或等於
3. 有辦法的話就繼續，沒有的話直接失敗回傳-1

Code

網友解答

class Solution {
    public int minOperations(int[] nums) {
        int res = 0;
        // From the end to the beginning
        for (int i = nums.length - 1; i >= 1; i--) {
            // Found invalid
            if (nums[i] < nums[i - 1]) {
                // Try to make the next num valid
                nums[i - 1] = makeValid(nums[i], nums[i - 1]);
                // Not possible to be valid
                if (nums[i - 1] == -1) return -1;
                ++res;
            }
        }
        return res;
    }

    private int makeValid(int curNum, int nextNum) {
        // Try to divide from 2 until the largest valid divisor
        for (int i = 2; i < curNum + 1; ++i) {
            if (nextNum % i == 0) return i;
        }
        return -1;
    }
}

▶

TLE

class Solution {
    public int minOperations(int[] nums) {
        if (nums.length == 1) return 0;

        int res = 0;

        for (int i = nums.length - 1; i >= 1; --i) {
            int nextNum = nums[i - 1];

            int divisor = 2;

            boolean isValid = true;

            // Found invalid
            while (nextNum > nums[i]) {
                isValid = false;
                // Cannot find a valid divisor, hence the nextNum will always be invalid
                if (divisor > nextNum) return -1;

                // Ensure the divisor is strictly less than nextNum
                while (divisor < nextNum) {
                    // Try to find the valid divisor
                    while (nextNum % divisor > 0) {
                        ++divisor;
                        // Cannot find the valid divisor
                        if (divisor > nextNum) return -1;
                    }

                    // Found valid divisor and it is effective
                    if (nextNum / divisor <= nums[i]) {
                        nextNum /= divisor;
                        break;
                    }
                    
                } 
            }
            // Valid and proceed
            nums[i - 1] = nextNum;
            if (!isValid) ++res;
        }
        return res;
    }
}