3886. Sum of Sortable Integers

2026, Oct 19 2 mins read

1. Description

For an integer array nums of length n, consider each positive divisor k of n.
Split nums into consecutive blocks of k elements. Each block may be cyclically shifted left or right independently, with any number of shifts, including zero.
Call k sortable if these shifts can make the entire array non-decreasing. Return the sum of all sortable values of k.

2. Example

Example 1

Input: nums = [3,1,2]
Output: 3
Explanation: Blocks of length 1 cannot change the array. With k = 3, shifting the whole array left once gives [1,2,3], so only 3 contributes to the sum.

Example 2

Input: nums = [7,6,5]
Output: 0
Explanation: Neither k = 1 nor k = 3 allows the array to become non-decreasing, so there are no sortable divisors.

Example 3

Input: nums = [5,8]
Output: 3
Explanation: The array is already sorted. Both divisors, 1 and 2, work without any shifts, giving 1 + 2 = 3.

3. Constraints

1 <= n == nums.length <= 10$^5$
1 <= nums[i] <= 10$^5$

4. Solutions

Enumeration

n = nums.size(), d = number of positive divisors of n
Time complexity: O(n log n + n d)
Space complexity: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    int sortableIntegers(vector<int> &nums) {
        const int n = nums.size();

        vector<int> sorted_nums(nums);
        sort(sorted_nums.begin(), sorted_nums.end());

        int sum = 0;
        for (int k = 1; k <= n; ++k) {
            if (n % k == 0) {
                bool valid = true;
                for (int i = 0; i < n && valid; i += k) {
                    int start = -1;
                    for (int j = i + 1; j < i + k; ++j) {
                        if (nums[j] < nums[j - 1]) {
                            if (start == -1) {
                                start = j;
                            } else {
                                goto stop;
                            }
                        }
                    }

                    if (start == -1) {
                        start = i;
                    }

                    for (int j = start, l = i; l < i + k; ++l) {
                        if (nums[j] != sorted_nums[l]) {
                            goto stop;
                        }

                        j = i + (j + 1) % k;
                    }
                }

                sum += k;

            stop:;
            }
        }

        return sum;
    }
};

Search

Tags