FPEvalDataset/LeetCodeProblem
0302
1{2 "id": 3783,3 "name": "permutations_iv",4 "difficulty": "Hard",5 "link": "https://leetcode.com/problems/permutations-iv/",6 "date": "2025-02-15 00:00:00",7 "task_description": "Given two integers, `n` and `k`, an **alternating permutation** is a permutation of the first `n` positive integers such that no **two** adjacent elements are both odd or both even. Return the **k-th** **alternating permutation** sorted in _lexicographical order_. If there are fewer than `k` valid **alternating permutations**, return an empty list. **Example 1:** **Input:** n = 4, k = 6 **Output:** [3,4,1,2] **Explanation:** The lexicographically-sorted alternating permutations of `[1, 2, 3, 4]` are: `[1, 2, 3, 4]` `[1, 4, 3, 2]` `[2, 1, 4, 3]` `[2, 3, 4, 1]` `[3, 2, 1, 4]` `[3, 4, 1, 2]` ← 6th permutation `[4, 1, 2, 3]` `[4, 3, 2, 1]` Since `k = 6`, we return `[3, 4, 1, 2]`. **Example 2:** **Input:** n = 3, k = 2 **Output:** [3,2,1] **Explanation:** The lexicographically-sorted alternating permutations of `[1, 2, 3]` are: `[1, 2, 3]` `[3, 2, 1]` ← 2nd permutation Since `k = 2`, we return `[3, 2, 1]`. **Example 3:** **Input:** n = 2, k = 3 **Output:** [] **Explanation:** The lexicographically-sorted alternating permutations of `[1, 2]` are: `[1, 2]` `[2, 1]` There are only 2 alternating permutations, but `k = 3`, which is out of range. Thus, we return an empty list `[]`. **Constraints:** `1 <= n <= 100` `1 <= k <= 1015`",8 "public_test_cases": [9 {10 "label": "Example 1",11 "input": "n = 4, k = 6",12 "output": "[3,4,1,2] "13 },14 {15 "label": "Example 2",16 "input": "n = 3, k = 2",17 "output": "[3,2,1] "18 },19 {20 "label": "Example 3",21 "input": "n = 2, k = 3",22 "output": "[] "23 }24 ],25 "private_test_cases": [26 {27 "input": [28 40,29 63542971088917230 ],31 "output": [32 1,33 2,34 3,35 4,36 5,37 6,38 7,39 8,40 9,41 10,42 11,43 12,44 13,45 14,46 15,47 16,48 17,49 18,50 27,51 28,52 23,53 32,54 31,55 26,56 35,57 36,58 39,59 40,60 19,61 34,62 21,63 38,64 37,65 20,66 33,67 30,68 29,69 24,70 25,71 2272 ]73 },74 {75 "input": [76 90,77 51873824780559078 ],79 "output": [80 1,81 2,82 3,83 4,84 5,85 6,86 7,87 8,88 9,89 10,90 11,91 12,92 13,93 14,94 15,95 16,96 17,97 18,98 19,99 20,100 21,101 22,102 23,103 24,104 25,105 26,106 27,107 28,108 29,109 30,110 31,111 32,112 33,113 34,114 35,115 36,116 37,117 38,118 39,119 40,120 41,121 42,122 43,123 44,124 45,125 46,126 47,127 48,128 49,129 50,130 51,131 52,132 53,133 54,134 55,135 56,136 57,137 58,138 59,139 60,140 61,141 62,142 63,143 64,144 65,145 66,146 67,147 68,148 75,149 82,150 77,151 90,152 73,153 88,154 83,155 86,156 71,157 84,158 79,159 70,160 89,161 78,162 85,163 74,164 81,165 76,166 69,167 80,168 87,169 72170 ]171 },172 {173 "input": [174 1,175 40295860898402176 ],177 "output": []178 },179 {180 "input": [181 16,182 349551818813564183 ],184 "output": []185 },186 {187 "input": [188 87,189 998153691720678190 ],191 "output": [192 1,193 2,194 3,195 4,196 5,197 6,198 7,199 8,200 9,201 10,202 11,203 12,204 13,205 14,206 15,207 16,208 17,209 18,210 19,211 20,212 21,213 22,214 23,215 24,216 25,217 26,218 27,219 28,220 29,221 30,222 31,223 32,224 33,225 34,226 35,227 36,228 37,229 38,230 39,231 40,232 41,233 42,234 43,235 44,236 45,237 46,238 47,239 48,240 49,241 50,242 51,243 52,244 53,245 54,246 55,247 56,248 57,249 58,250 59,251 60,252 61,253 62,254 63,255 64,256 65,257 78,258 85,259 84,260 67,261 66,262 75,263 68,264 73,265 72,266 71,267 74,268 77,269 82,270 81,271 86,272 79,273 76,274 83,275 70,276 87,277 80,278 69279 ]280 },281 {282 "input": [283 74,284 795093009177573285 ],286 "output": [287 1,288 2,289 3,290 4,291 5,292 6,293 7,294 8,295 9,296 10,297 11,298 12,299 13,300 14,301 15,302 16,303 17,304 18,305 19,306 20,307 21,308 22,309 23,310 24,311 25,312 26,313 27,314 28,315 29,316 30,317 31,318 32,319 33,320 34,321 35,322 36,323 37,324 38,325 39,326 40,327 41,328 42,329 43,330 44,331 45,332 46,333 47,334 48,335 49,336 50,337 51,338 52,339 63,340 64,341 59,342 70,343 73,344 72,345 65,346 68,347 67,348 62,349 61,350 74,351 71,352 66,353 69,354 60,355 53,356 58,357 55,358 54,359 57,360 56361 ]362 },363 {364 "input": [365 3,366 331829499538853367 ],368 "output": []369 },370 {371 "input": [372 31,373 738363147318413374 ],375 "output": [376 1,377 2,378 3,379 4,380 5,381 6,382 7,383 8,384 9,385 20,386 13,387 10,388 27,389 14,390 23,391 12,392 11,393 18,394 21,395 28,396 25,397 26,398 31,399 22,400 29,401 24,402 17,403 16,404 15,405 30,406 19407 ]408 },409 {410 "input": [411 40,412 699856856676228413 ],414 "output": [415 1,416 2,417 3,418 4,419 5,420 6,421 7,422 8,423 9,424 10,425 11,426 12,427 13,428 14,429 15,430 16,431 17,432 18,433 27,434 38,435 21,436 28,437 35,438 36,439 19,440 30,441 23,442 20,443 37,444 26,445 31,446 32,447 39,448 34,449 25,450 40,451 33,452 24,453 29,454 22455 ]456 },457 {458 "input": [459 67,460 674021944184663461 ],462 "output": [463 1,464 2,465 3,466 4,467 5,468 6,469 7,470 8,471 9,472 10,473 11,474 12,475 13,476 14,477 15,478 16,479 17,480 18,481 19,482 20,483 21,484 22,485 23,486 24,487 25,488 26,489 27,490 28,491 29,492 30,493 31,494 32,495 33,496 34,497 35,498 36,499 37,500 38,501 39,502 40,503 41,504 42,505 43,506 44,507 45,508 54,509 61,510 48,511 65,512 60,513 47,514 58,515 51,516 56,517 63,518 62,519 57,520 50,521 53,522 64,523 67,524 46,525 59,526 66,527 49,528 52,529 55530 ]531 }532 ],533 "haskell_template": "permute :: Int -> Int -> [Int]\npermute n k ",534 "ocaml_template": "let permute (n: int) (k: int) : int list = ",535 "scala_template": "def permute(n: Int,k: Int): List[Int] = { \n \n}",536 "java_template": "class Solution {\n public int[] permute(int n, long k) {\n \n }\n}",537 "python_template": "class Solution(object):\n def permute(self, n, k):\n \"\"\"\n :type n: int\n :type k: int\n :rtype: List[int]\n \"\"\"\n "538}