Sum of sortable integers

30.2% acceptance

Mar 31, 2026

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn sortable_integers(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    let mut sorted = nums.clone();
    sorted.sort_unstable();

    // O(k) rotation check: target is a rotation of chunk iff target
    // appears as a substring in chunk+chunk (KMP search).
    fn is_rotation(chunk: &[i32], target: &[i32]) -> bool {
      let k = chunk.len();
      // Build KMP failure function for target
      let mut fail = vec![0usize; k];
      let mut j = 0usize;
      for i in 1..k {
        while j > 0 && target[i] != target[j] {
          j = fail[j - 1];
        }
        if target[i] == target[j] {
          j += 1;
        }
        fail[i] = j;
      }
      // Search target in doubled chunk
      j = 0;
      for i in 0..2 * k {
        let c = chunk[i % k];
        while j > 0 && c != target[j] {
          j = fail[j - 1];
        }
        if c == target[j] {
          j += 1;
        }
        if j == k {
          return true;
        }
      }
      false
    }

    let mut sum = 0i32;
    for k in 1..=n {
      if n % k != 0 {
        continue;
      }
      let ok = (0..n / k).all(|c| {
        let start = c * k;
        is_rotation(&nums[start..start + k], &sorted[start..start + k])
      });
      if ok {
        sum += k as i32;
      }
    }
    sum
  }
}