Find if Array Can Be Sorted

Leetcode Problem:

• Find if Array Can Be Sorted

Summary

• Given an array of positive integers, determine if it can be sorted in ascending order by swapping adjacent elements with the same number of set bits.

Approach

• The solution uses a two-pass approach to track the maximum and minimum numbers encountered so far
• It also keeps track of the number of set bits for each number
• If a number with more set bits is found after a number with the same number of set bits, the function returns false
• If all numbers can be sorted, the function returns true.

Complexity

• O(n) where n is the number of elements in the array, as each element is visited once.

Explanation

• The solution works by iterating through the array and tracking the number of set bits for each number
• If a number with more set bits is found after a number with the same number of set bits, the function returns false
• If all numbers can be sorted, the function returns true
• The time complexity is O(n) because each element is visited once, and the space complexity is O(1) because only a constant amount of space is used.

Solution Code:

class Solution {
public:
    int getOneCnt(int num){
        int cnt = 0;
        while(num){
            cnt++;
            num &= num-1;
        }
        return cnt;
    }
    vector arr;
    bool canSortArray(vector& nums) {
        int beforeCnt = getOneCnt(nums[0]);
        int beforeMax = 0;
        int maxNum = nums[0];
        for(int i = 1 ; i < nums.size(); i++){
            int cnt = getOneCnt(nums[i]);
            if( cnt != beforeCnt){
                if(maxNum > nums[i]) return false;
                beforeMax = maxNum;
                maxNum = nums[i];
                beforeCnt = cnt;
                continue;
            }
            if(beforeMax > nums[i]) return false;
            if(maxNum < nums[i]){
                maxNum = nums[i];
            }
        }

        return true;
    }
};