The Question
Coding

Sum of Sortable Block Lengths

You are given an integer array nums of length $n$. An integer $k$ is defined as 'sortable' if $k$ is a divisor of $n$ and the array nums can be transformed into a non-decreasingly sorted array by performing the following operations: 1. Partition the array into $n/k$ consecutive subarrays, each of length $k$. 2. Independently rotate each subarray cyclically (left or right) any number of times. Your task is to find and return the sum of all such sortable integers $k$. Constraints: - $1 \le n \le 10^5$ - $-10^9 \le nums[i] \le 10^9$
Python3
Prefix Sum
Hashing
Divisor Iteration
Questions & Insights

Clarifying Questions

What is the range of $n$ and the elements in `nums`?
Assumption: n can be up to 10^5, and elements are integers within typical 32-bit ranges.
Can the array contain duplicates?
Assumption: Yes, duplicates are allowed, and "non-decreasing order" implies handling these correctly (the sorted version of a block must be exactly the same as the sorted slice of the globally sorted array).
What is the time complexity limit?
Assumption: Typically 2.0 seconds, which is sufficient for O(n \log n + \sigma_1(n)) where \sigma_1(n) is the sum of divisors of n.
What are the constraints on $k$?
Assumption: k must be a positive divisor of n.

Thinking Process

Sorted Target Alignment: If rotating subarrays of length k results in a sorted global array, then each k-length block in the original array must contain exactly the same elements as the corresponding k-length block in the globally sorted array.
Cyclic Shift Property: For a specific block to be "sortable" via cyclic rotation, the block must be a cyclic shift of the target sorted block.
Efficient Validation: To check if block A is a cyclic shift of sorted block B:
The multiset of elements in A must match the multiset of elements in B.
A must be "rotationally sorted"—meaning it has at most one "drop" (an index j where A[j] > A[j+1]), accounting for the wrap-around from the last element back to the first.
Complexity Optimization:
Use random hashing (Zobrist-like) and prefix sums to verify multiset equality for all blocks in O(1) after O(n) precomputation.
Use prefix sums of "drop" counts (where nums[i] > nums[i+1]) to verify the "rotationally sorted" property in O(1) per block.
Iterate through all divisors k of n. Since the total number of blocks across all divisors is \sum_{k|n} n/k = \sigma_1(n), the total complexity is very efficient.
Implementation Breakdown

Problem Set

Functional Requirements: Sum all k such that k|n and every consecutive block of length k can be independently cyclically rotated to match its corresponding segment in the globally sorted array.
Constraints: n \in [1, 10^5], nums[i] \in [-10^9, 10^9].

Approach

Algorithm: Prefix Sums + Random Hashing + Divisor Iteration.
Data Structure: Array, Hash Map.
Complexity:
Time: O(n \log n + \sigma_1(n)) where \sigma_1(n) is the sum of divisors.
Space: O(n).

Implementation

Wrap Up

Advanced Topics

Readability vs. Performance: In Python, loops can be slow. For very large N, using numpy or a rolling hash might be considered, but the O(\sigma_1(n)) complexity here is already highly efficient because the number of block checks is relatively small.
Probabilistic Safety: While 128-bit random hashing is standard for competitive programming to prevent collisions, in a production environment, one might use a cryptographic hash or a strictly deterministic approach (like counting frequencies if the alphabet is small).
Parallelization: Checking each divisor k is an independent task (Embarrassingly Parallel), so it could be distributed across multiple CPU cores for massive datasets.