Ezvor

3886. Sum of Sortable Integers

HardArray Preparing judge… LeetCode

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

Hints

Hint 1
First, observe that k must divide n, since the array is partitioned into subarrays of length k. Iterate over all divisors of n.
Hint 2
Let s be the sorted version of the array. For each divisor k, check every block [i, i+k).
Hint 3
A block can be rotated to match its sorted counterpart if the sorted segment s[i..i+k-1] appears as a cyclic rotation of nums[i..i+k-1].
Hint 4
You can test this by checking whether the sorted segment exists inside two concatenated copies of the block. If all blocks satisfy this, then k is sortable.