An integer k is called sortable if kdividesn 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
Solutions
Solution 1: Enumeration + Simulation
Thinking
Trying every rotation of every block for each divisor \(k\) costs \(O(k^2)\) per block, which is too slow when \(n \le 10^5\).
Those repeated rotations are the bottleneck. A block can be cycled into non-decreasing order exactly when it has at most one strict circular descent. After every block is rotated that way, the concatenation is globally non-decreasing exactly when, at every boundary, the maximum on the left does not exceed the minimum on the right.
Both quantities sit on the block boundaries.
We precompute the prefix maximum, the suffix minimum, and a prefix sum of adjacent descents, then enumerate the divisors of \(n\) and judge each block in \(O(1)\) time.
First build three auxiliary arrays. \(\textit{prefMax}[i]\) is the maximum of \(\textit{nums}[0..i-1]\), with \(\textit{prefMax}[0] = 0\). \(\textit{suffMin}[i]\) is the minimum of \(\textit{nums}[i..n-1]\). \(\textit{prefDrop}[i]\) counts how many index pairs \((0,1),\ldots,(i-1,i)\) satisfy \(\textit{nums}[j-1] > \textit{nums}[j]\).
Then enumerate every divisor \(k\) of \(n\) and split the array into blocks of length \(k\). For a block starting at \(i\), the number of adjacent descents inside the block is \(\textit{prefDrop}[i+k-1] - \textit{prefDrop}[i]\), plus one more when \(\textit{nums}[i+k-1] > \textit{nums}[i]\). If this total is at most \(1\) and \(\textit{prefMax}[i] \le \textit{suffMin}[i]\), the block can be cyclically rotated onto the already ordered prefix. When every block passes, add \(k\) to the answer.
The time complexity is \(O(n + \sigma(n))\), and the space complexity is \(O(n)\), where \(n\) is the length of the array and \(\sigma(n)\) is the sum of all positive divisors of \(n\).