Description
Sum of Sortable Integers
HardYou 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
numsinto consecutive subarrays of lengthk. - 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 = 3is 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
kis 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 is1 + 2 = 3.
Constraints:
1 <= n == nums.length <= 1051 <= nums[i] <= 105
Solutions
Fixed my mistake and simplified code using named continues. Not gonna lie, pretty proud of myself for this one.
Language: javascript()DONE
CPU Performance14.33%
x
Memory Performance5.11%
x
/**
* @param {number[]} nums
* @return {number}
*/
var sortableIntegers = function(nums) {
const n = nums.length;
let res = 0;
next_k: for (let k = 1; k <= n; k++) {
if (n % k === 0) {
const partitions = [];
let cur = [];
for (let i = 0; i < n; i++) {
if (cur.length < k) {
cur.push(nums[i]);
} else {
partitions.push(cur);
cur = [nums[i]];
}
}
partitions.push(cur);
let lastMax = 0;
for (let i = 0; i < partitions.length; i++) {
const len = partitions[i].length;
let seenCut = false;
let max = 0;
for (let j = 0; j < len; j++) {
max = Math.max(max, partitions[i][j]);
if (partitions[i][j] < lastMax) continue next_k;
if (partitions[i][j] > partitions[i][(j + 1) % len]) {
if (seenCut) continue next_k;
seenCut = true;
}
}
lastMax = max;
}
res += k;
}
}
return res;
};