3886. Sum of Sortable Integers
Problem Overview
A divisor k is sortable when each consecutive block of length k can be cyclically rotated into non-decreasing order and those sorted blocks then form one global non-decreasing array.
Intuition
A divisor k is sortable when each consecutive block of length k can be cyclically rotated into non-decreasing order and those sorted blocks then form one global non-decreasing array. A block is a cyclic shift of a sorted sequence exactly when it has at most one strict circular descent. Once every block is rotated that way, the concatenation is sorted precisely when, at each block start, the maximum of the prefix before it is at most the minimum of the suffix from there. Prefix maxima, suffix minima, and a descent prefix sum make every block check constant time.
Algorithm
- 1Build prefMax[i] as the max of nums[0..i-1], suffMin[i] as the min of nums[i..n-1], and prefDrop[i] as the number of adjacent descents among the first i pairs.
- 2Enumerate every positive divisor k of n.
- 3For each block start, let drops be the linear descents inside the block plus one when the wrap pair descends.
- 4Reject the divisor if any block has drops above 1 or prefMax[start] greater than suffMin[start].
- 5Add every divisor that passes all of its blocks.
Example Walkthrough
Input: nums = [3,1,2]
- 1.For k = 1 the single-element blocks cannot reorder [3,1,2] into sorted order.
- 2.For k = 3 the one block has a single circular descent and rotates to [1,2,3].
- 3.Only 3 is sortable, so the sum is 3.
Output: 3
Common Pitfalls
- •Having the same multiset as the matching sorted segment is not enough. The block must be a cyclic rotation, not an arbitrary permutation.
- •Count the wrap pair nums[end] against nums[start] when measuring circular descents.
- •prefMax[0] must be a sentinel below every array value so the first block always clears the prefix check.
- •Trying every rotation explicitly is too slow for n = 1e5. The descent and prefix checks are enough.
// Approach: k is sortable when every block of length k is a cyclic shift of a
// non-decreasing sequence and the blocks' value ranges nest in order. A block
// is such a shift iff it has at most one strict circular descent. After each
// block is rotated into sorted order, the concatenation is globally sorted iff
// at every block start the max of the prefix before it is <= the min of the
// suffix from there. Prefetch prefix maxima, suffix minima, and linear descent
// counts so each block is checked in O(1) while enumerating the divisors of n.
// Time: O(n + d(n) * (n/k avg)) = O(n) Space: O(n)
public 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] = int.MaxValue;
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 d = 1; d <= n / d; d++)
{
if (n % d != 0)
continue;
if (Check(nums, prefMax, suffMin, prefDrop, d))
ans += d;
int other = n / d;
if (other != d && Check(nums, prefMax, suffMin, prefDrop, other))
ans += other;
}
return ans;
}
private static bool 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;
}
}