TheRealSamuel/LeetCodeProblem
0564
1{2 "id": 3291,3 "name": "find_if_array_can_be_sorted",4 "difficulty": "Medium",5 "link": "https://leetcode.com/problems/find-if-array-can-be-sorted/",6 "date": "2024-01-06 00:00:00",7 "task_description": "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 in ascending order, 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`",8 "public_test_cases": [9 {10 "label": "Example 1",11 "input": "nums = [8,4,2,30,15]",12 "output": "true "13 },14 {15 "label": "Example 2",16 "input": "nums = [1,2,3,4,5]",17 "output": "true "18 },19 {20 "label": "Example 3",21 "input": "nums = [3,16,8,4,2]",22 "output": "false "23 }24 ],25 "private_test_cases": [26 {27 "input": [28 23,29 6,30 22,31 18,32 13,33 11,34 26,35 3,36 25,37 14,38 24,39 19,40 1,41 5,42 5,43 21,44 9,45 16,46 28,47 28,48 10,49 18,50 7,51 21,52 26,53 10,54 7,55 11,56 13,57 858 ],59 "output": false60 },61 {62 "input": [63 20,64 14,65 19,66 23,67 17,68 10,69 7,70 27,71 24,72 14,73 11,74 21,75 18,76 12,77 13,78 10,79 7,80 1,81 23,82 22,83 22,84 23,85 11,86 3,87 21,88 1,89 14,90 4,91 5,92 15,93 28,94 16,95 12,96 5,97 27,98 12,99 9,100 21,101 20,102 22,103 14,104 27,105 16,106 11,107 28,108 5,109 26,110 20,111 24,112 12,113 22,114 3,115 28,116 4,117 24,118 5,119 20,120 10,121 15122 ],123 "output": false124 },125 {126 "input": [127 26,128 10,129 14,130 22,131 6,132 25,133 5,134 17,135 7,136 11,137 16,138 10,139 19,140 22,141 10,142 21,143 18,144 6,145 28,146 10,147 7,148 17,149 22,150 17,151 23,152 22,153 5,154 5,155 18,156 14,157 19,158 2,159 6,160 4,161 27,162 26,163 7,164 22,165 13,166 18,167 24,168 12,169 21,170 16,171 17,172 15,173 19,174 24,175 12,176 15,177 24,178 21,179 28,180 3,181 9,182 22,183 19,184 15,185 23,186 6,187 19,188 20,189 18,190 6,191 18,192 4,193 15,194 21,195 23,196 10,197 5,198 3199 ],200 "output": false201 },202 {203 "input": [204 17,205 17,206 20,207 17,208 6,209 1,210 4,211 6,212 11,213 21,214 9,215 25,216 14,217 4,218 15,219 25,220 21,221 16,222 23,223 13,224 11,225 3,226 20,227 4,228 5,229 23,230 23,231 15,232 15,233 4,234 21,235 11,236 14,237 14,238 5,239 12,240 21,241 18242 ],243 "output": false244 },245 {246 "input": [247 20,248 21,249 9,250 28,251 5,252 8,253 28,254 8,255 27,256 16,257 4,258 25,259 18,260 7,261 14,262 22,263 16,264 1,265 16,266 28,267 13,268 11,269 25,270 25,271 15,272 2,273 10,274 21,275 24,276 4,277 8,278 12,279 13,280 20,281 7,282 12,283 18,284 28,285 27,286 8,287 17,288 4,289 11,290 24,291 21,292 24,293 5,294 2,295 12,296 16,297 28,298 14,299 27,300 16,301 4,302 18,303 17,304 26,305 27306 ],307 "output": false308 },309 {310 "input": [311 1,312 2,313 3,314 4,315 5,316 6,317 7,318 8,319 9,320 10,321 11,322 12,323 13,324 14,325 15,326 16,327 17,328 18,329 19,330 20,331 21,332 22333 ],334 "output": true335 },336 {337 "input": [338 15,339 4,340 4,341 15,342 4343 ],344 "output": false345 },346 {347 "input": [348 3,349 16,350 8,351 4,352 2353 ],354 "output": false355 },356 {357 "input": [358 4359 ],360 "output": true361 }362 ],363 "haskell_template": "canSortArray :: [Int] -> Bool\ncanSortArray nums ",364 "ocaml_template": "let canSortArray (nums: int list) : bool = ",365 "scala_template": "def canSortArray(nums: List[Int]): Boolean = { \n \n}",366 "java_template": "class Solution {\n public boolean canSortArray(int[] nums) {\n \n }\n}",367 "python_template": "class Solution(object):\n def canSortArray(self, nums):\n \"\"\"\n :type nums: List[int]\n :rtype: bool\n \"\"\"\n "368}