3886. Sum of Sortable Integers

Description

You are given an integer array nums of length n.

An integer k is called sortable if k divides n and you can sort nums in non-decreasing order by sequentially performing the following operations:

Partition nums into consecutive subarrays of length k.
Cyclically rotate each subarray independently any number of times to the left or to the right.

Return an integer denoting the sum of all possible sortable integers k.

Example 1:

Input: nums = [3,1,2]

Output: 3

Explanation:

For n = 3, possible divisors are 1 and 3.
For k = 1: each subarray has one element. No rotation can sort the array.
For k = 3: the single subarray [3, 1, 2] can be rotated once to produce [1, 2, 3], which is sorted.
Only k = 3 is sortable. Hence, the answer is 3.

Example 2:

Input: nums = [7,6,5]

Output: 0

Explanation:

For n = 3, possible divisors are 1 and 3.
For k = 1: each subarray has one element. No rotation can sort the array.
For k = 3: the single subarray [7, 6, 5] cannot be rotated into non-decreasing order.
No k is sortable. Hence, the answer is 0.

Example 3:

Input: nums = [5,8]

Output: 3

Explanation:

For n = 2, possible divisors are 1 and 2.
Since [5, 8] is already sorted, every divisor is sortable. Hence, the answer is 1 + 2 = 3.

Constraints:

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

Solutions

Solution 1

class Solution {
    public int sortableIntegers(int[] nums) {
        int n = nums.length;
        int[] prefMax = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            prefMax[i + 1] = Math.max(prefMax[i], nums[i]);
        }
        int[] suffMin = new int[n + 1];
        suffMin[n] = 1000000000;
        for (int i = n - 1; i >= 0; --i) {
            suffMin[i] = Math.min(nums[i], suffMin[i + 1]);
        }
        int[] prefDrop = new int[n];
        for (int i = 1; i < n; ++i) {
            prefDrop[i] = prefDrop[i - 1] + (nums[i - 1] > nums[i] ? 1 : 0);
        }
        int ans = 0;
        for (int i = 1; i <= n / i; ++i) {
            if (n % i == 0) {
                if (check(nums, prefMax, suffMin, prefDrop, i)) {
                    ans += i;
                }
                if (i != n / i && check(nums, prefMax, suffMin, prefDrop, n / i)) {
                    ans += n / i;
                }
            }
        }
        return ans;
    }

    private boolean check(int[] nums, int[] prefMax, int[] suffMin, int[] prefDrop, int k) {
        int n = nums.length;
        for (int start = 0; start < n; start += k) {
            int end = start + k - 1;
            int drops = prefDrop[end] - prefDrop[start];
            if (nums[end] > nums[start]) {
                ++drops;
            }
            if (drops > 1 || prefMax[start] > suffMin[start]) {
                return false;
            }
        }
        return true;
    }
}

class Solution {
public:
    int sortableIntegers(vector<int>& nums) {
        int n = nums.size();
        vector<int> prefMax(n + 1);
        for (int i = 0; i < n; ++i) {
            prefMax[i + 1] = max(prefMax[i], nums[i]);
        }
        vector<int> suffMin(n + 1, 1000000000);
        for (int i = n - 1; i >= 0; --i) {
            suffMin[i] = min(nums[i], suffMin[i + 1]);
        }
        vector<int> prefDrop(n);
        for (int i = 1; i < n; ++i) {
            prefDrop[i] = prefDrop[i - 1] + (nums[i - 1] > nums[i]);
        }
        auto check = [&](int k) {
            for (int start = 0; start < n; start += k) {
                int end = start + k - 1;
                int drops = prefDrop[end] - prefDrop[start];
                if (nums[end] > nums[start]) {
                    ++drops;
                }
                if (drops > 1 || prefMax[start] > suffMin[start]) {
                    return false;
                }
            }
            return true;
        };
        int ans = 0;
        for (int i = 1; i <= n / i; ++i) {
            if (n % i == 0) {
                if (check(i)) {
                    ans += i;
                }
                if (i != n / i && check(n / i)) {
                    ans += n / i;
                }
            }
        }
        return ans;
    }
};

class Solution:
    def sortableIntegers(self, nums: list[int]) -> int:
        n = len(nums)
        pref_max = [0] * (n + 1)
        for i, x in enumerate(nums):
            pref_max[i + 1] = max(pref_max[i], x)
        suff_min = [10**9] * (n + 1)
        for i in range(n - 1, -1, -1):
            suff_min[i] = min(nums[i], suff_min[i + 1])
        pref_drop = [0] * n
        for i in range(1, n):
            pref_drop[i] = pref_drop[i - 1] + (nums[i - 1] > nums[i])

        def check(k: int) -> bool:
            for start in range(0, n, k):
                end = start + k - 1
                drops = pref_drop[end] - pref_drop[start]
                if nums[end] > nums[start]:
                    drops += 1
                if drops > 1 or pref_max[start] > suff_min[start]:
                    return False
            return True

        ans = 0
        i = 1
        while i <= n // i:
            if n % i == 0:
                if check(i):
                    ans += i
                other = n // i
                if i != other and check(other):
                    ans += other
            i += 1
        return ans

func sortableIntegers(nums []int) int {
	n := len(nums)
	prefMax := make([]int, n+1)
	for i, x := range nums {
		prefMax[i+1] = max(prefMax[i], x)
	}
	suffMin := make([]int, n+1)
	suffMin[n] = 1000000000
	for i := n - 1; i >= 0; i-- {
		suffMin[i] = min(nums[i], suffMin[i+1])
	}
	prefDrop := make([]int, n)
	for i := 1; i < n; i++ {
		prefDrop[i] = prefDrop[i-1]
		if nums[i-1] > nums[i] {
			prefDrop[i]++
		}
	}
	check := func(k int) bool {
		for start := 0; start < n; start += k {
			end := start + k - 1
			drops := prefDrop[end] - prefDrop[start]
			if nums[end] > nums[start] {
				drops++
			}
			if drops > 1 || prefMax[start] > suffMin[start] {
				return false
			}
		}
		return true
	}
	ans := 0
	for i := 1; i <= n/i; i++ {
		if n%i == 0 {
			if check(i) {
				ans += i
			}
			if i != n/i && check(n/i) {
				ans += n / i
			}
		}
	}
	return ans
}

function sortableIntegers(nums: number[]): number {
    const n = nums.length;
    const prefMax = new Array<number>(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        prefMax[i + 1] = Math.max(prefMax[i], nums[i]);
    }
    const suffMin = new Array<number>(n + 1).fill(1e9);
    for (let i = n - 1; i >= 0; i--) {
        suffMin[i] = Math.min(nums[i], suffMin[i + 1]);
    }
    const prefDrop = new Array<number>(n).fill(0);
    for (let i = 1; i < n; i++) {
        prefDrop[i] = prefDrop[i - 1] + (nums[i - 1] > nums[i] ? 1 : 0);
    }

    const check = (k: number): boolean => {
        for (let start = 0; start < n; start += k) {
            const end = start + k - 1;
            let drops = prefDrop[end] - prefDrop[start];
            if (nums[end] > nums[start]) {
                drops++;
            }
            if (drops > 1 || prefMax[start] > suffMin[start]) {
                return false;
            }
        }
        return true;
    };

    let ans = 0;
    for (let i = 1; i <= Math.floor(n / i); i++) {
        if (n % i === 0) {
            const other = n / i;
            if (check(i)) {
                ans += i;
            }
            if (i !== other && check(other)) {
                ans += other;
            }
        }
    }
    return ans;
}

3886 - Sum of Sortable Integers

3886. Sum of Sortable Integers

Description

Solutions

Solution 1

All Problems

All Solutions

Welcome to Subscribe On Youtube

3886. Sum of Sortable Integers

Description

Solutions

Solution 1

All Problems

All Solutions