Sum the Block Lengths That Permit Sorting by Rotation

# Sum the Block Lengths That Permit Sorting by Rotation You are given an integer array `nums` of length `n`. A positive integer `k` is valid if `k` divides `n` and the following process can make the whole array nondecreasing: 1. Split the array into the fixed consecutive blocks `[0, k)`, `[k, 2k)`, and so on. 2. Independently rotate each block cyclically to the left or right any number of times, including zero times. A rotation moves entries only within their own block. You may not exchange blocks or move an entry across a block boundary. Return the sum of all valid block lengths `k`. Return `0` if none is valid. ### Function `int sortableIntegers(vector<int>& nums)` ### Example 1 **Input:** `nums = [2, 1, 4, 3, 6, 5]` **Output:** `2` **Explanation:** For `k = 2`, rotate each pair once to obtain `[1, 2, 3, 4, 5, 6]`. The other divisors of `6`, namely `1`, `3` and `6`, do not allow the whole array to be sorted. The sum is therefore `2`. ### Example 2 **Input:** `nums = [2, 2, 1, 1]` **Output:** `4` **Explanation:** For `k = 4`, rotate the whole array two positions left to obtain `[1, 1, 2, 2]`. With `k = 2`, the constant blocks `[2, 2]` and `[1, 1]` cannot change their order or values. With `k = 1`, no entry can move. Only `4` is valid. ### Constraints - `1 <= n == nums.length <= 100000` - `1 <= nums[i] <= 100000` - Values may repeat. ### Clarifications - The required final order is nondecreasing, so equal neighboring values are allowed. - Each block may use a different rotation, and a block may be left unchanged. - The answer is a sum of valid lengths, not the number of valid lengths. ### What a Strong Answer Covers - Preserving the fixed partition for each chosen divisor. - Accounting for duplicate values and independent rotations. - Handling cases where only some divisors work or no divisor works.