The Question

Sum of Sortable Partition Sizes

Given an integer array `nums` of length `n`, a positive integer `k` is defined as 'sortable' if `k` is a divisor of `n` and the array can be sorted into non-decreasing order by partitioning it into consecutive subarrays of length `k` and independently rotating each subarray any number of times. Write a function to return the sum of all such sortable integers `k`. Your solution should handle large inputs efficiently and account for duplicate elements.

Python3

Hashing

Prefix Sum

Math

Sorting

Questions & Insights

Clarifying Questions

What is the range of $n$ and the values in `nums`?

Assumption: Based on common competitive programming standards,

n

is up to

10^5

and values are up to

10^9

Can the array contain duplicates?

Assumption: Yes, the solution should handle duplicate values correctly.

Does "sortable" mean the final array must be exactly the sorted version of the input array?

Assumption: Yes. If

k

is sortable, we must be able to reach sorted(nums) by rotating each block of size

k

independently.

What should be the return value if no $k$ is sortable?

Assumption: Since

k

must divide

n

k=n

is always a candidate. If no

k

works, the sum would be 0. However, usually

k=n

k=1

(if already sorted) will be the minimal cases.

Thinking Process

Multiset Constraint: For a block of size

k

starting at index

i

to be transformable into the corresponding sorted block, it must contain exactly the same elements (multiset equality). We can verify this efficiently for all blocks by checking if the prefix sum of element hashes in nums matches the prefix sum of element hashes in the sorted version at every multiple of

k

Cyclic Shift Property: A block

B

of size

k

is a cyclic shift of its sorted counterpart

S

if and only if

B

is "cyclically sorted." This means

B

has at most one "drop" (an index

j

where

B[j] > B[j+1]

). If exactly one drop exists at some index, the last element of the block must be less than or equal to the first element (

B[k-1] \le B[0]

) to satisfy the wrap-around sorted property.

Divisor Iteration: The total number of blocks across all possible values of

k

(divisors of

n

) is

\sum_{k|n} n/k = \sigma_1(n)

. For

n=10^5

\sigma_1(n)

is approximately

2.5 \times 10^5

3.6 \times 10^5

, making an

O(\sigma_1(n))

approach highly efficient even in Python.

Optimization: Pre-calculate the sorted array, prefix sums of random hashes for multiset checks, and prefix sums of "drop" occurrences for

O(1)

block validation.

Implementation Breakdown

Problem Set

Functional Requirements: Find all

k

such that

n \% k == 0

and every block of length

k

can be cyclically rotated to match the corresponding block in the fully sorted array.

Constraints:

Time Complexity:

O(N \log N + \sigma_1(N))

, where

\sigma_1(N)

is the sum of divisors.

Space Complexity:

O(N)

to store prefix sums and sorted arrays.

Approach

Algorithm: Divisor iteration with Prefix Sum optimization.

Data Structure: Prefix Sums / Hashing (Randomized Sum Hash).

Complexity: Time

O(n \log n + \sigma_1(n))

, Space

O(n)

Implementation

Wrap Up

Advanced Topics

Readability vs. Performance: In Python, utilizing numpy or itertools for prefix sums can be faster, but manual loops are more portable for standard coding interviews.

Deterministic Hashing: In competitive environments where anti-hash test cases are possible, seeding the random generator with a truly random source or using a composite hash (two different hash functions) ensures

O(1)

collision probability.

Parallelization: Since each

k

is independent, the divisor checks could be distributed across multiple CPU cores for massive arrays (

n > 10^7