LeetCode in Kotlin

3886. Sum of Sortable Integers

Hard

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 non-empty 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 <= 105
• 1 <= nums[i] <= 105

Solution

import kotlin.math.max
import kotlin.math.min

class Solution {
    // Changed method name from sumOfSortableIntegers to sortableIntegers
    fun sortableIntegers(nums: IntArray): Int {
        val n = nums.size
        if (n == 0) {
            return 0
        }
        val prefMax = IntArray(n)
        prefMax[0] = nums[0]
        for (i in 1..<n) {
            prefMax[i] = max(prefMax[i - 1], nums[i])
        }
        val suffMin = IntArray(n)
        suffMin[n - 1] = nums[n - 1]
        for (i in n - 2 downTo 0) {
            suffMin[i] = min(suffMin[i + 1], nums[i])
        }
        val prefDrops = IntArray(n)
        for (i in 1..<n) {
            prefDrops[i] = prefDrops[i - 1] + (if (nums[i - 1] > nums[i]) 1 else 0)
        }
        var sumOfK = 0
        for (k in 1..n) {
            if (n % k == 0 && (isSortable(k, n, nums, prefMax, suffMin, prefDrops))) {
                sumOfK += k
            }
        }
        return sumOfK
    }

    private fun isSortable(
        k: Int,
        n: Int,
        nums: IntArray,
        prefMax: IntArray,
        suffMin: IntArray,
        prefDrops: IntArray,
    ): Boolean {
        var idx = k
        while (idx < n) {
            if (prefMax[idx - 1] > suffMin[idx]) {
                return false
            }
            idx += k
        }
        var start = 0
        while (start < n) {
            val end = start + k - 1
            val internalDrops = prefDrops[end] - prefDrops[start]
            val cyclicDrop = if (nums[end] > nums[start]) 1 else 0
            if (internalDrops + cyclicDrop > 1) {
                return false
            }
            start += k
        }
        return true
    }
}

This site is open source. Improve this page.