3886. Sum of Sortable Integers
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.
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
|
class Solution {
bool helper(vector<int>& A, vector<int>& S, int x) {
int n = A.size();
for(int i = 0; i < n; i += x) {
if(S[i] == S[i+x-1]) {
for(int j = i; j < i + x; j++) {
if(S[j] != A[j]) return false;
}
} else {
int best = 0;
for(int j = i; j < i + x; j++) {
if(A[j] >= A[i + best]) best = j - i;
}
while(A[(best + 1) % x + i] == A[best + i]) best = (best + 1) % x + i;
for(int j = i + x - 1; j >= i; j--, best = (best - 1 + x) % x) {
if(A[i + best] != S[j]) return false;
}
}
}
return true;
}
public:
int sortableIntegers(vector<int>& nums) {
vector<int> S = nums;
sort(begin(S), end(S));
int n = nums.size(), res = 0;
for(int i = 1; i * i <= n; i++) {
if(n % i) continue;
int j = n / i;
if(helper(nums,S,i)) res += i;
if(i != j and helper(nums,S,j)) res += j;
}
return res;
}
};
|
