Skip to content

3886. Sum of Sortable Integers

Description

You are given an integer array nums of length n.

An integer k is called sortable if k divides n 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

Thinking

\(k\) is sortable iff \(k\) divides \(n\) and each block of length \(k\) can be rotated so the concatenation is nondecreasing. \(n \le 10^5\).

There are few divisors; enumerate them. For each \(k\), a block must be a rotation, and neighboring blocks must join monotonically.

Global monotonicity means the chosen rotations concatenate in order. Check each position against the cyclic order, or compare adjacent blocks after their minimal rotations.

Sum the divisors that pass.

1


1


1


1

Comments