We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find if Array Can Be Sorted

Number: 3291

Difficulty: Medium

Paid? No

Companies: Meta, Microsoft, Edelweiss Group

Problem Description

Given a 0-indexed array of positive integers, nums, you can swap any two adjacent elements if they have the same number of set bits in their binary representation. Return true if it is possible to sort the array in ascending order using any number of these operations (including zero), otherwise return false.

Key Insights

  • Only adjacent elements with the same number of set bits can be swapped.
  • The relative order between numbers with different set bit counts cannot change.
  • For each group of numbers sharing the same set bit count, the sequence's relative order must remain identical in both the original array and the sorted version.
  • Thus, by grouping elements based on their set bit count and comparing the groups in the original array to those in the fully sorted array, one can determine if the array can be sorted using the allowed swaps.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the array. Space Complexity: O(n) for storing the sorted array and subsequences for each group.

Solution

First, create a sorted copy of the array. For each possible set bit count (which can be from 0 to at most 8 based on the problem constraints), extract the subsequences from both the original and sorted arrays. Since only adjacent swaps between numbers with the same set bit count are allowed, the relative order of elements in each group must match between the two arrays. If any group's order differs, then it is impossible to sort the array under the given constraints. Otherwise, the array can be sorted.

This solution uses basic list operations and comparisons, leveraging sorting and subsequence extraction to check the necessary condition.

Code Solutions

def count_set_bits(x):
    # Return the number of 1's in the binary representation of x.
    return bin(x).count("1")

def canBeSorted(nums):
    # Create a sorted copy of the array.
    sorted_nums = sorted(nums)
    
    # Determine the maximum relevant bit count (nums[i] <= 2^8 implies bit counts up to 8).
    max_bits = max(count_set_bits(num) for num in nums)
    
    # For each possible bit count, compare the subsequences from original and sorted arrays.
    for bit in range(max_bits + 1):
        original_group = [num for num in nums if count_set_bits(num) == bit]
        sorted_group = [num for num in sorted_nums if count_set_bits(num) == bit]
        if original_group != sorted_group:
            return False
    return True

# Example usage:
print(canBeSorted([8,4,2,30,15]))  # Expected output: True
print(canBeSorted([1,2,3,4,5]))    # Expected output: True
print(canBeSorted([3,16,8,4,2]))    # Expected output: False
← Back to All Questions