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.
1#include <stdio.h>
2#include <stdbool.h>
3#include <stdlib.h>
4
5int compare(const void *a, const void *b) {
6 return (*(int*)a - *(int*)b);
7}
8
9int countSetBits(int n) {
10 int count = 0;
11 while (n) {
12 n &= (n - 1);
13 count++;
14 }
15 return count;
16}
17
18bool canBeSorted(int* nums, int numsSize) {
19 int maxBitsCount = 8; // Since input constraints are nums[i] <= 2^8
20 int *bitCountBuckets[maxBitsCount];
21 int bucketSizes[maxBitsCount] = {0};
22
23 for (int i = 0; i < maxBitsCount; i++) {
24 bitCountBuckets[i] = (int *)malloc(numsSize * sizeof(int));
25 }
26
27 for (int i = 0; i < numsSize; i++) {
28 int bits = countSetBits(nums[i]);
29 bitCountBuckets[bits][bucketSizes[bits]++] = nums[i];
30 }
31
32 for (int i = 0; i < maxBitsCount; i++) {
33 qsort(bitCountBuckets[i], bucketSizes[i], sizeof(int), compare);
34 }
35
36 int index = 0;
37 for (int i = 0; i < maxBitsCount; i++) {
38 for (int j = 0; j < bucketSizes[i]; j++) {
39 nums[index++] = bitCountBuckets[i][j];
40 }
41 }
42
43 for (int i = 0; i < numsSize - 1; i++) {
44 if (nums[i] > nums[i + 1]) {
45 for (int j = 0; j < maxBitsCount; j++) {
46 free(bitCountBuckets[j]);
47 }
48 return false;
49 }
50 }
51
52 for (int i = 0; i < maxBitsCount; i++) {
53 free(bitCountBuckets[i]);
54 }
55
56 return true;
57}
58
59int main() {
60 int nums[] = {8, 4, 2, 30, 15};
61 int numsSize = 5;
62 printf("%s\n", canBeSorted(nums, numsSize) ? "true" : "false");
63 return 0;
64}The implementation first calculates the number of set bits for each element in the array. We then utilize arrays akin to buckets to store elements based on their set bits count. Each bucket is then independently sorted. Finally, the sorted buckets are concatenated and checked for any overall sorting errors.
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).
1using System;
using System.Collections.Generic;
using System.Linq;
class SortableArrayChecker {
public static int CountSetBits(int n) {
int count = 0;
while (n != 0) {
n &= (n - 1);
count++;
}
return count;
}
public static bool CanBeSorted(int[] nums) {
int[] sortedNums = (int[])nums.Clone();
Array.Sort(sortedNums);
List<int>[] bitCountBuckets = new List<int>[9];
for (int i = 0; i <= 8; i++) {
bitCountBuckets[i] = new List<int>();
}
foreach (int num in nums) {
bitCountBuckets[CountSetBits(num)].Add(num);
}
foreach (var bucket in bitCountBuckets) {
bucket.Sort();
}
int index = 0;
foreach (var bucket in bitCountBuckets) {
foreach (var num in bucket) {
if (sortedNums[index++] != num) return false;
}
}
return true;
}
static void Main() {
int[] nums = {8, 4, 2, 30, 15};
Console.WriteLine(CanBeSorted(nums));
}
}An evolution of set-bit group checking establishes base correctness srcursed on the sorted numerical set comparisons.