3011. Find if Array Can Be Sorted#
Surdarla
Nov 06 Wed 15:06, 2024
1 min read
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, else return false.
Example 1:
Input: nums = [8,4,2,30,15]
Output: true
Explanation: Letโs look at the binary representation of every element. The numbers 2, 4, and 8 have one set bit each with binary representation โ10โ, โ100โ, and โ1000โ respectively. The numbers 15 and 30 have four set bits each with binary representation โ1111โ and โ11110โ.
We can sort the array using 4 operations:
Swap nums[0] with nums[1]. This operation is valid because 8 and 4 have one set bit each. The array becomes [4,8,2,30,15].
Swap nums[1] with nums[2]. This operation is valid because 8 and 2 have one set bit each. The array becomes [4,2,8,30,15].
Swap nums[0] with nums[1]. This operation is valid because 4 and 2 have one set bit each. The array becomes [2,4,8,30,15].
Swap nums[3] with nums[4]. This operation is valid because 30 and 15 have four set bits each. The array becomes [2,4,8,15,30]. The array has become sorted, hence we return true. Note that there may be other sequences of operations which also sort the array.
Example 2:
Input: nums = [1,2,3,4,5]
Output: true
Explanation: The array is already sorted, hence we return true.
Example 3:
Input: nums = [3,16,8,4,2]
Output: false
Explanation: It can be shown that it is not possible to sort the input array using any number of operations.
Constraints:
1 <= nums.length <= 100
1 <= nums[i] <= 28
## code
import os
import logging
import traceback
import datetime
from typing import List
def get_logger(LEVEL: str = "INFO") -> logging.Logger:
logger = logging.getLogger("custom_logger")
logger.setLevel(getattr(logging, LEVEL.upper(), logging.INFO))
stream_handler = logging.StreamHandler()
formatter = logging.Formatter(
fmt="[%(asctime)s %(levelname)s] %(message)s", datefmt="%Y/%m/%d %H:%M:%S"
)
stream_handler.setFormatter(formatter)
if logger.hasHandlers():
logger.handlers.clear()
logger.addHandler(stream_handler)
return logger
def sol(problem_num, func):
script_dir = os.getcwd() # os.path.dirname(os.path.abspath(__file__))
path = script_dir + f"\\txt\\{problem_num}" + ".txt"
try:
with open(path, "r") as getter:
line_count = 1
while True:
line = getter.readline()
if not line:
logger.info("EOF")
break
try:
inp, oup = line.strip().split()
##############
inp = list(map(int, inp.split(",")))
oup = True if oup == "true" else False if oup == "false" else None
################
if not func(inp) == oup:
raise ValueError(f"wrong output in line : {line}")
logger.info(f"{line_count} : {inp} : {oup == func(inp)}")
line_count += 1
except Exception as e:
logger.error(f"Error occurred while processing line: {line}")
logger.error(f"Exception: {e}")
logger.error(traceback.format_exc())
line_count += 1
break
logger.info("ACCEPT")
except FileNotFoundError:
logger.error(f"File not found: {path}")
except Exception as e:
logger.error(f"Error opening file: {e}")
logger.error(traceback.format_exc())
class Solution:
def canSortArray(self, nums: List[int]) -> bool:
pmax = pcnt = cmin = cmax = 0
for v in nums:
ccnt = v.bit_count()
if pcnt == ccnt:
cmin = min(cmin, v)
cmax = max(cmax, v)
elif cmin < pmax:
return False
else:
pmax = cmax
cmin = cmax = v
pcnt = ccnt
return cmin >= pmax
problem_num = 3011
global logger
logger = get_logger("info")
sol(problem_num, Solution().canSortArray)
[2024/11/06 15:56:23 INFO] 1 : [8, 4, 2, 30, 15] : True
[2024/11/06 15:56:23 INFO] 2 : [1, 2, 3, 4, 5] : True
[2024/11/06 15:56:23 INFO] 3 : [3, 16, 8, 4, 2] : True
[2024/11/06 15:56:23 INFO] EOF
[2024/11/06 15:56:23 INFO] ACCEPT