Find if array can be sorted

Array Bit Manipulation Sorting

66.4% acceptance

Feb 25, 2026

712

You are given a 0-indexed array of positive integers nums. In one operation, you can swap any two adjacent elements if they have the same number of set bits. You are allowed to do this operation any number of times (including zero). Return true if you can sort the array in ascending order, else return false.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn can_sort_array(nums: Vec<i32>) -> bool {
    let n = nums.len();
    let mut prev_max = 0i32;
    let mut i = 0;
    while i < n {
      let bits = nums[i].count_ones();
      let mut j = i;
      while j < n && nums[j].count_ones() == bits { j += 1; }
      let group_min = nums[i..j].iter().min().copied().unwrap();
      let group_max = nums[i..j].iter().max().copied().unwrap();
      if group_min < prev_max { return false; }
      prev_max = group_max;
      i = j;
    }
    true
  }
}