TheRealSamuel/LeetCodeProblem
0564
1{2 "id": 2339,3 "name": "k_divisible_elements_subarrays",4 "difficulty": "Medium",5 "link": "https://leetcode.com/problems/k-divisible-elements-subarrays/",6 "date": "1650758400000",7 "task_description": "Given an integer array `nums` and two integers `k` and `p`, return _the number of **distinct subarrays,** which have **at most**_ `k` _elements _that are _divisible by_ `p`. Two arrays `nums1` and `nums2` are said to be **distinct** if: They are of **different** lengths, or There exists **at least** one index `i` where `nums1[i] != nums2[i]`. A **subarray** is defined as a **non-empty** contiguous sequence of elements in an array. **Example 1:** ``` **Input:** nums = [**2**,3,3,**2**,**2**], k = 2, p = 2 **Output:** 11 **Explanation:** The elements at indices 0, 3, and 4 are divisible by p = 2. The 11 distinct subarrays which have at most k = 2 elements divisible by 2 are: [2], [2,3], [2,3,3], [2,3,3,2], [3], [3,3], [3,3,2], [3,3,2,2], [3,2], [3,2,2], and [2,2]. Note that the subarrays [2] and [3] occur more than once in nums, but they should each be counted only once. The subarray [2,3,3,2,2] should not be counted because it has 3 elements that are divisible by 2. ``` **Example 2:** ``` **Input:** nums = [1,2,3,4], k = 4, p = 1 **Output:** 10 **Explanation:** All element of nums are divisible by p = 1. Also, every subarray of nums will have at most 4 elements that are divisible by 1. Since all subarrays are distinct, the total number of subarrays satisfying all the constraints is 10. ``` **Constraints:** `1 <= nums.length <= 200` `1 <= nums[i], p <= 200` `1 <= k <= nums.length` **Follow up:** Can you solve this problem in O(n2) time complexity?",8 "public_test_cases": [9 {10 "label": "Example 1",11 "input": "nums = [ 2 ,3,3, 2 , 2 ], k = 2, p = 2",12 "output": "11 "13 },14 {15 "label": "Example 2",16 "input": "nums = [1,2,3,4], k = 4, p = 1",17 "output": "10 "18 }19 ],20 "private_test_cases": [21 {22 "input": [23 [24 167,25 70,26 128,27 58,28 184,29 186,30 14,31 71,32 26,33 45,34 24,35 25,36 41,37 2,38 198,39 54,40 92,41 95,42 151,43 55,44 166,45 194,46 140,47 24,48 91,49 158,50 57,51 8,52 49,53 28,54 55,55 131,56 31,57 164,58 110,59 142,60 146,61 91,62 149,63 162,64 185,65 172,66 36,67 178,68 133,69 17670 ],71 14,72 15273 ],74 "output": 107875 },76 {77 "input": [78 [79 64,80 116,81 128,82 67,83 47,84 163,85 153,86 64,87 148,88 10,89 73,90 146,91 33,92 191,93 61,94 145,95 154,96 78,97 14,98 85,99 1,100 165,101 171,102 91,103 36,104 101,105 5,106 118,107 40,108 61,109 180,110 18,111 198,112 187,113 164,114 67,115 43,116 41,117 180,118 43,119 150,120 181,121 8,122 21,123 191,124 104,125 20,126 83,127 78,128 33,129 15,130 115,131 159,132 142,133 92,134 10,135 135,136 47,137 68,138 116,139 46,140 30,141 80,142 125,143 65,144 119,145 85,146 193,147 194,148 114,149 137,150 106,151 74,152 93,153 24,154 20,155 145,156 50,157 142,158 13,159 107,160 99,161 168,162 15,163 152,164 140,165 155,166 16,167 92,168 114,169 155,170 54,171 141,172 161,173 118,174 193,175 105,176 189,177 172,178 168,179 188,180 84,181 57,182 27,183 68,184 106,185 177,186 9,187 134,188 122,189 32,190 114,191 25,192 173,193 1,194 48,195 13,196 9,197 88,198 191,199 171,200 56,201 87,202 195,203 165,204 55,205 104,206 179,207 148,208 37,209 9,210 150,211 173,212 184,213 178,214 88,215 173,216 59,217 81,218 108,219 195,220 95,221 175,222 105,223 63,224 199,225 179,226 55,227 101,228 184,229 172,230 75,231 148,232 13,233 23,234 50,235 19,236 146,237 11,238 153,239 176240 ],241 124,242 134243 ],244 "output": 12991245 },246 {247 "input": [248 [249 55,250 73,251 9,252 35,253 36,254 152,255 184,256 130,257 128,258 50,259 159,260 75,261 125,262 20,263 45,264 198265 ],266 16,267 18268 ],269 "output": 136270 },271 {272 "input": [273 [274 119,275 127,276 77,277 3,278 100,279 55,280 99,281 96,282 18,283 179,284 121285 ],286 7,287 167288 ],289 "output": 66290 },291 {292 "input": [293 [294 163,295 168,296 140,297 68,298 140,299 176,300 160,301 114,302 141,303 122,304 168,305 165,306 162,307 31,308 2,309 194,310 149,311 157,312 143,313 2,314 176,315 48,316 12,317 182,318 144,319 109,320 34,321 137,322 48,323 96,324 61,325 127,326 189,327 188,328 178,329 124,330 155,331 74,332 94,333 8,334 73,335 46,336 158,337 41,338 150,339 75,340 81,341 131,342 189,343 145,344 58,345 42,346 142,347 100,348 126,349 118,350 191,351 81,352 132,353 200,354 58,355 117,356 170,357 183,358 41,359 18,360 33,361 30,362 76,363 106,364 82,365 102,366 9,367 92,368 44,369 172,370 81,371 197,372 92,373 80,374 165,375 138,376 46,377 134,378 147,379 157,380 28,381 171382 ],383 18,384 177385 ],386 "output": 3902387 },388 {389 "input": [390 [391 153,392 24,393 189,394 40,395 28,396 139,397 195,398 168,399 61,400 98,401 140,402 52,403 166,404 132,405 60,406 180,407 15408 ],409 3,410 82411 ],412 "output": 153413 },414 {415 "input": [416 [417 60,418 11,419 190,420 147,421 105,422 99,423 73,424 106,425 16,426 178,427 134,428 70,429 106,430 24,431 47,432 56,433 107,434 85,435 48,436 119,437 59,438 95,439 137,440 157,441 152,442 47,443 155,444 84,445 92,446 113,447 62,448 93,449 113,450 10,451 22,452 105,453 81,454 185,455 76,456 33,457 65,458 54,459 140,460 75,461 199,462 94,463 44,464 85,465 55,466 163,467 104,468 142,469 80,470 167,471 182,472 53,473 33,474 91,475 50,476 197,477 19,478 190,479 25480 ],481 39,482 194483 ],484 "output": 2009485 },486 {487 "input": [488 [489 78,490 118,491 40,492 60,493 85,494 200,495 137,496 147,497 10,498 157,499 133,500 67,501 58,502 132,503 71,504 192,505 167,506 174,507 42,508 168,509 129,510 95,511 28,512 62,513 29,514 78,515 55,516 129,517 184,518 183,519 67,520 38,521 55,522 62,523 173,524 30,525 70,526 114,527 34,528 101,529 64,530 185,531 81,532 81,533 10,534 82,535 170,536 140,537 184,538 95,539 58,540 11,541 35,542 81,543 191,544 146,545 168,546 116,547 16,548 51,549 179,550 118,551 43,552 104,553 154,554 67,555 75,556 138,557 185,558 148,559 200,560 167,561 62,562 176,563 94,564 156,565 126,566 69,567 39,568 112,569 173,570 58,571 21,572 160,573 2,574 80,575 195,576 116,577 38,578 192,579 146,580 95,581 135,582 34,583 82,584 36,585 62,586 23,587 23,588 183,589 128,590 174,591 151,592 32,593 133,594 43,595 79,596 4,597 194,598 46,599 179,600 200,601 27,602 118,603 135,604 185,605 191,606 194,607 149,608 40,609 82,610 25,611 106,612 109,613 73,614 5,615 180,616 77,617 49,618 177,619 122,620 8,621 106,622 20,623 3,624 59,625 183,626 167,627 134,628 138,629 179,630 114,631 129,632 78,633 147,634 131,635 180,636 41637 ],638 108,639 56640 ],641 "output": 10974642 },643 {644 "input": [645 [646 51,647 126,648 55,649 133,650 129,651 180,652 24,653 155,654 92,655 52,656 124,657 104,658 10,659 46,660 134,661 134,662 165,663 16,664 21,665 157,666 90,667 146,668 17,669 99,670 183,671 70,672 181,673 120,674 151,675 118,676 55,677 21,678 98,679 36,680 103,681 80,682 82,683 43,684 168,685 82,686 57,687 51,688 131,689 69,690 160,691 66,692 157,693 199,694 116,695 166,696 86,697 8,698 110,699 154,700 51,701 81,702 58,703 181,704 93,705 142,706 166,707 126,708 74,709 29,710 32,711 110,712 69,713 17,714 190,715 123,716 1,717 14,718 84,719 80,720 151,721 192,722 104,723 65,724 196,725 18,726 29,727 122,728 159,729 42,730 47,731 137,732 130,733 12,734 5,735 54,736 35,737 4,738 128,739 34,740 182,741 54,742 183,743 13,744 188,745 44,746 141,747 76,748 13,749 97,750 185,751 166,752 3,753 104,754 167,755 83,756 66,757 151,758 133,759 93,760 47,761 32,762 125,763 24,764 121,765 199,766 87,767 2,768 23,769 104770 ],771 107,772 150773 ],774 "output": 7719775 },776 {777 "input": [778 [779 31,780 141,781 119,782 126,783 21,784 162,785 18,786 126,787 184,788 82,789 117,790 183,791 64,792 143,793 143,794 32,795 29,796 171,797 173,798 169,799 11,800 55,801 167,802 6,803 119,804 192,805 54,806 124,807 6,808 198,809 197,810 195,811 56,812 192,813 195,814 161,815 165,816 59,817 82,818 164,819 137,820 66,821 123,822 87,823 132,824 179,825 145,826 132,827 73,828 145,829 168,830 127,831 8,832 189,833 139,834 12,835 172,836 152,837 180,838 158,839 13,840 44,841 76,842 91,843 178,844 32,845 176,846 32,847 171,848 2,849 53,850 126,851 101,852 4,853 50,854 118,855 81,856 165,857 129,858 192,859 56,860 191,861 195,862 127,863 110,864 117,865 48,866 173,867 92,868 108,869 195,870 108,871 172,872 138,873 113,874 160,875 11,876 122,877 19,878 173,879 90,880 40,881 34,882 167,883 1,884 192,885 90,886 122,887 134,888 148,889 28,890 93,891 66,892 192,893 137,894 186,895 56,896 145,897 91898 ],899 81,900 96901 ],902 "output": 7105903 }904 ],905 "haskell_template": "countDistinct :: [Int] -> Int -> Int -> Int\ncountDistinct nums k p ",906 "ocaml_template": "let countDistinct (nums: int list) (k: int) (p: int) : int = ",907 "scala_template": "def countDistinct(nums: List[Int],k: Int,p: Int): Int = { \n \n}",908 "java_template": "public static int countDistinct(List<Integer> nums, int k, int p) {\n\n}",909 "python_template": "class Solution(object):\n def countDistinct(self, nums, k, p):\n \"\"\"\n :type nums: List[int]\n :type k: int\n :type p: int\n :rtype: int\n \"\"\"\n "910}