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

1


1


1


1

Comments