LeetCode 3886 - Sum of Sortable Integers

The problem asks us to find all integers k that divide the length of the input array nums and for which the array can be sorted into non-decreasing order using a very specific operation.

leetcodehardarraymathsortingenumeration

LeetCode Problem 3886

Difficulty: 🔴 Hard
Topics: Array, Math, Sorting, Enumeration

Solution

Problem Understanding

The problem asks us to find all integers k that divide the length of the input array nums and for which the array can be sorted into non-decreasing order using a very specific operation. The operation is to partition nums into consecutive subarrays of length k and then cyclically rotate each subarray independently any number of times. A cyclic rotation allows elements to be shifted left or right with wrap-around, meaning the relative order of elements within each subarray can be changed but only within the subarray itself. The task is to sum all such k that allow the array to be sorted after these operations.

The input is an integer array nums of size n with elements between 1 and 10^5. The array length n can be as large as 10^5, which suggests that a naive brute-force approach checking every permutation would be too slow. The output is a single integer representing the sum of all sortable divisors of n.

Key observations include the importance of array length divisors, subarray rotations, and the fact that k = 1 is trivial but usually unsortable unless the array is already sorted. Edge cases include arrays that are already sorted, arrays in strictly descending order, or arrays of length 1 or 2.

Approaches

The brute-force approach would try every divisor k of n and for each one, generate all possible rotations of every subarray and check if the final array is sorted. This approach is correct in principle but extremely inefficient because generating all rotations for each subarray is exponential in k and n/k. This would quickly exceed time limits for n = 10^5.

The optimal approach relies on a key observation: a subarray of length k can be rotated arbitrarily, so the position modulo k in the sorted array must contain exactly the same elements as the position modulo k in the original array. Concretely, if we sort nums to get sorted_nums, then for each index i, nums[i] must appear somewhere in the group i % k in the sorted array. If this holds for all indices in all groups, then k is sortable. This reduces the problem to counting occurrences in modulo classes, which is linear for each divisor k.

Approach Time Complexity Space Complexity Notes
Brute Force O(n! * n/k) O(n) Generates all rotations for all divisors, too slow for large n
Optimal O(n * sqrt(n)) O(n) Uses counting by modulo positions and compares with sorted array

Algorithm Walkthrough

  1. Compute the sorted version of nums called sorted_nums.
  2. Find all divisors of n and store them in a list.
  3. Initialize a variable total to accumulate the sum of sortable k.
  4. For each divisor k, create k buckets (lists) representing positions modulo k.
  5. Assign elements of nums into their corresponding bucket according to index modulo k.
  6. Assign elements of sorted_nums into another set of buckets in the same way.
  7. For each bucket, compare the multiset of original elements with the multiset of sorted elements.
  8. If all buckets match for a divisor k, add k to total.
  9. Return total.

Why it works: The modulo buckets guarantee that cyclic rotations of size k cannot move elements out of their modulo class. Therefore, if the elements in each modulo class match the sorted array's corresponding positions, there exists a series of rotations to achieve the sorted array.

Python Solution

class Solution:
    def sortableIntegers(self, nums: list[int]) -> int:
        from collections import Counter
        n = len(nums)
        sorted_nums = sorted(nums)
        
        # Find all divisors of n
        divisors = []
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                divisors.append(i)
                if i != n // i:
                    divisors.append(n // i)
        
        total = 0
        for k in divisors:
            buckets_orig = [[] for _ in range(k)]
            buckets_sorted = [[] for _ in range(k)]
            
            for idx, val in enumerate(nums):
                buckets_orig[idx % k].append(val)
            
            for idx, val in enumerate(sorted_nums):
                buckets_sorted[idx % k].append(val)
            
            if all(Counter(buckets_orig[i]) == Counter(buckets_sorted[i]) for i in range(k)):
                total += k
        
        return total

Explanation: The code first sorts nums and finds all divisors of n. For each divisor k, it partitions both nums and sorted_nums into k modulo-based buckets. Using Counter, it checks if each bucket contains exactly the same elements as the corresponding sorted bucket. If all buckets match, k is added to the total sum. The use of Counter allows handling repeated numbers correctly.

Go Solution

package main

func sortableIntegers(nums []int) int {
    n := len(nums)
    sortedNums := make([]int, n)
    copy(sortedNums, nums)
    // Sort the copy
    sort.Ints(sortedNums)

    // Find divisors
    divisors := []int{}
    for i := 1; i*i <= n; i++ {
        if n%i == 0 {
            divisors = append(divisors, i)
            if i != n/i {
                divisors = append(divisors, n/i)
            }
        }
    }

    total := 0
    for _, k := range divisors {
        bucketsOrig := make([]map[int]int, k)
        bucketsSorted := make([]map[int]int, k)
        for i := 0; i < k; i++ {
            bucketsOrig[i] = make(map[int]int)
            bucketsSorted[i] = make(map[int]int)
        }

        for idx, val := range nums {
            bucketsOrig[idx%k][val]++
        }
        for idx, val := range sortedNums {
            bucketsSorted[idx%k][val]++
        }

        sortable := true
        for i := 0; i < k; i++ {
            if len(bucketsOrig[i]) != len(bucketsSorted[i]) {
                sortable = false
                break
            }
            for key, count := range bucketsOrig[i] {
                if bucketsSorted[i][key] != count {
                    sortable = false
                    break
                }
            }
            if !sortable {
                break
            }
        }
        if sortable {
            total += k
        }
    }
    return total
}

Go-specific notes: Since Go does not have Counter, we use maps to count occurrences. Slices of maps represent the modulo buckets. Sorting is done with sort.Ints. Overflow is not a concern due to constraints.

Worked Examples

Example 1: nums = [3, 1, 2]

  • n = 3, divisors [1, 3]
  • Sorted array: [1, 2, 3]
  • k = 1: buckets [[3], [1], [2]] vs [[1], [2], [3]] → not equal
  • k = 3: buckets [[3, 1, 2]] vs [[1, 2, 3]] → equal → sortable
  • Sum = 3

Example 2: nums = [7, 6, 5]

  • n = 3, divisors [1, 3]
  • Sorted array: [5, 6, 7]
  • k = 1: not equal, k = 3: not equal → sum = 0

Example 3: nums = [5, 8]

  • n = 2, divisors [1, 2]
  • Sorted array: [5, 8]
  • k = 1: equal → 1, k = 2: equal → 2 → sum = 3

Complexity Analysis

Measure Complexity Explanation
Time O(n * sqrt(n)) Divisors of n are ≤ 2*sqrt(n). For each divisor, we build modulo buckets and compare them in O(n).
Space O(n) Storing buckets for nums and sorted_nums uses linear space.

The algorithm scales well up to n = 10^5 due to linear processing per divisor and a small number of divisors.

Test Cases

# Example test cases
assert Solution().sortableIntegers([3,1,2]) == 3  # single sortable k=3
assert Solution().sortableIntegers([7,6,5]) == 0  # no sortable k
assert Solution().sortableIntegers([5,8]) == 3    # both k=1 and k=2 sortable

# Edge and additional cases
assert Solution().sortableIntegers([1]) == 1       # single element array
assert Solution().sortableIntegers([2,1]) == 2    # k=1 not sortable, k=2 sortable
assert Solution().sortableIntegers([1,2,3,