3886. Sum of Sortable Integers

/**
 * Problem: LeetCode 3886 - Sum of Sortable Integers
 * Difficulty: Hard
 * Language: Java
 * Author: CodeByTushu
 */
class Solution {
    public int sortableIntegers(int[] nums) {
        int n = nums.length;
        int ans = 0;
        for (int k = 1; k <= n; k++) {
            if (n % k != 0) continue;
            if (isSortable(nums, n, k)) ans += k;
        }
        return ans;
    }

    private boolean isSortable(int[] nums, int n, int k) {
        int prevMax = 0;
        for (int start = 0; start < n; start += k) {
            int mn = Integer.MAX_VALUE, mx = Integer.MIN_VALUE;
            int desc = 0;
            int end = start + k;
            for (int i = start; i < end; i++) {
                mn = Math.min(mn, nums[i]);
                mx = Math.max(mx, nums[i]);
                int next = (i + 1 < end) ? i + 1 : start;
                if (nums[i] > nums[next]) desc++;
            }
            if (desc > 1) return false;
            if (mn < prevMax) return false;

            prevMax = mx;
        }
        return true;
    }
}

"""
Problem: LeetCode 3886 - Sum of Sortable Integers
Difficulty: Hard
Language: Python
Author: CodeByTushu
"""
from typing import List

class Solution:
    def sortableIntegers(self, nums: List[int]) -> int:
        n = len(nums)
        ans = 0

        def is_sortable(k: int) -> bool:
            prev_max = 0
            for start in range(0, n, k):
                end = start + k
                mn = float('inf')
                mx = float('-inf')
                desc = 0
                for i in range(start, end):
                    val = nums[i]
                    if val < mn:
                        mn = val
                    if val > mx:
                        mx = val
                    next_idx = i + 1 if i + 1 < end else start
                    if nums[i] > nums[next_idx]:
                        desc += 1
                if desc > 1:
                    return False
                if mn < prev_max:
                    return False
                prev_max = mx
            return True

        for k in range(1, n + 1):
            if n % k != 0:
                continue
            if is_sortable(k):
                ans += k

        return ans

/**
 * Problem: LeetCode 3886 - Sum of Sortable Integers
 * Difficulty: Hard
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

/**
 * Problem: LeetCode 3886 - Sum of Sortable Integers
 * Difficulty: Hard
 * Language: C++
 * Author: CodeByTushu
 */
class Solution {
public:
    int sortableIntegers(vector<int>& nums) {
        int n = nums.size();
        int ans = 0;

        for (int k = 1; k <= n; k++) {
            if (n % k != 0) continue;
            if (isSortable(nums, n, k)) {
                ans += k;
            }
        }
        return ans;
    }

private:
    bool isSortable(const vector<int>& nums, int n, int k) {
        int prevMax = 0;
        for (int start = 0; start < n; start += k) {
            int mn = INT_MAX, mx = INT_MIN;
            int desc = 0;
            int end = start + k;
            for (int i = start; i < end; i++) {
                mn = min(mn, nums[i]);
                mx = max(mx, nums[i]);
                int next = (i + 1 < end) ? i + 1 : start;
                if (nums[i] > nums[next]) {
                    desc++;
                }
            }
            if (desc > 1) return false;
            if (mn < prevMax) return false;

            prevMax = mx;
        }
        return true;
    }
};

/**
 * Problem: LeetCode 3886 - Sum of Sortable Integers
 * Difficulty: Hard
 * Language: JavaScript
 * Author: CodeByTushu
 */
var sortableIntegers = function(nums) {
    const n = nums.length;
    let ans = 0;

    function isSortable(k) {
        let prevMax = 0;
        for (let start = 0; start < n; start += k) {
            let mn = Infinity;
            let mx = -Infinity;
            let desc = 0;
            const end = start + k;

            for (let i = start; i < end; i++) {
                if (nums[i] < mn) mn = nums[i];
                if (nums[i] > mx) mx = nums[i];
                const next = (i + 1 < end) ? i + 1 : start;
                if (nums[i] > nums[next]) {
                    desc++;
                }
            }

            if (desc > 1) return false;
            if (mn < prevMax) return false;

            prevMax = mx;
        }
        return true;
    }

    for (let k = 1; k <= n; k++) {
        if (n % k !== 0) continue;
        if (isSortable(k)) {
            ans += k;
        }
    }

    return ans;
};