Sponsored
Sponsored
This approach involves creating a mapping of numbers based on their set bits count. We group all numbers having the same set bits count and sort each group individually. If by concatenating these sorted groups in the order of their set bits count, we can get a sorted version of the original array, then we return true; otherwise, return false.
Time Complexity: O(n log n), primarily due to the sorting step for each bucket.
Space Complexity: O(n), for the additional storage required for the bitCountBuckets.
1import java.util.ArrayList;
2import java.util.Collections;
3import java.util.List;
4
5public class SortableArrayChecker {
6
7 public static int countSetBits(int n) {
8 int count = 0;
9 while (n != 0) {
10 n &= (n - 1);
11 count++;
12 }
13 return count;
14 }
15
16 public static boolean canBeSorted(int[] nums) {
17 List<Integer>[] bitCountBuckets = new ArrayList[9];
18 for (int i = 0; i <= 8; i++) {
19 bitCountBuckets[i] = new ArrayList<>();
20 }
21
22 for (int num : nums) {
23 int bitsCount = countSetBits(num);
24 bitCountBuckets[bitsCount].add(num);
25 }
26
27 for (List<Integer> bucket : bitCountBuckets) {
28 Collections.sort(bucket);
29 }
30
31 int[] sortedArray = new int[nums.length];
32 int index = 0;
33 for (List<Integer> bucket : bitCountBuckets) {
34 for (int num : bucket) {
35 sortedArray[index++] = num;
36 }
37 }
38
39 for (int i = 0; i < sortedArray.length - 1; i++) {
40 if (sortedArray[i] > sortedArray[i + 1]) {
41 return false;
42 }
43 }
44
45 return true;
46 }
47
48 public static void main(String[] args) {
49 int[] nums = {8, 4, 2, 30, 15};
50 System.out.println(canBeSorted(nums));
51 }
52}The Java solution mirrors the C++ one, utilizing an array of lists to create groups of numbers sharing the same set-bit counts. Each group is sorted before being concatenated back together. We then check overall sorting of the resulting list.
In this approach, we simulate the individual moves as described in the problem. We group numbers by their set bit counts and within each group, attempt sorting by simulating adjacent swaps. Finally, we attempt confirmation by juxtaposing against a globally sorted array.
Time Complexity: O(n log n), due to multiple sorting.
Space Complexity: O(n).
1
By grouping in buckets and simulating as many allowed swaps as necessary within the grouping paradigm, we achieve a checkpoint against the globally sorted version.