Statistics

Problem Statement for "Distincter"

Problem Statement

We are given a int[] sequence containing a sequence of numbers. In a single operation, we can either increment or decrement the value of a single element by 1. Determine the minimum number of operations we must perform before the sequence contains at least K distinct elements.

Definition

Class:
Distincter
Method:
disperse
Parameters:
int[], int
Returns:
int
Method signature:
int disperse(int[] sequence, int K)
(be sure your method is public)

Notes

  • Note that we can create negative elements during the process.

Constraints

  • sequence will contain between 1 and 50 elements, inclusive.
  • Each element in sequence will be between 1 and 1000, inclusive.
  • K will be between 1 and the number of elements in sequence, inclusive.

Examples

  1. {5, 1, 3}

    2

    Returns: 0

    The sequence already has two distinct elements.

  2. {1, 1, 1, 1, 1, 1, 1}

    5

    Returns: 6

    Some elements can become negative.

  3. {1, 1, 1, 1, 1, 2, 3}

    6

    Returns: 6

  4. {8, 9, 7, 8, 7, 9, 7}

    7

    Returns: 7

  5. {1, 2, 3, 4, 4, 5, 7, 7, 8}

    9

    Returns: 4

    The optimal way to make 9 distinct elements is to increase one of the 4s two times and increase one of the 7s two times.

  6. {576, 571, 571, 572, 575, 572, 571, 568, 573, 572, 569, 572}

    11

    Returns: 12

  7. {676,677,678,679,679,681,682,682,683,684,685,686,687,688,689,690,691,692,693,694}

    20

    Returns: 6

  8. {489,490,491,492,492,494,495,495,496,497,499,500,501,501,502,503,504,505,506,507}

    20

    Returns: 9

  9. {543,544,545,546,546,548,549,549,550,551,553,554,555,555,556,557,558,560,561,562,563,563,564,565,566,567,568,569,570,571}

    30

    Returns: 13

  10. {340,341,342,343,343,345,346,346,347,348,350,351,352,352,353,354,355,357,358,359,360,360,361,362,363,364,366,367,368,369,370,370,371,372,373,374,375}

    30

    Returns: 0

  11. {340,341,342,343,343,345,346,346,347,348,350,351,352,352,353,354,355,357,358,359,360,360,361,362,363,364,366,367,368,369,370,370,371,372}

    27

    Returns: 0

  12. {574,604,619,585,587,579,600,621,594,611,581,618,597,584,614,616,595,594,580,582,575,592,596,586,593,607,591,586,576,613,577,605,589,608,617,609,604,603,588,606,612,620,598,615,577,602,580,616,622,601}

    50

    Returns: 24

  13. {626,601,588,606,648,587,589,635,630,638,632,595,646,605,592,604,594,616,609,634,643,647,590,649,627,607,607,611,617,645,622,641,624,613,629,617,590,621,619,629,600,593,639,631,643,614,599,602,618,637}

    50

    Returns: 6

  14. {340,341,342,343,343,343,346,346,347,348,350,351,352,352,353,354,355,357,358,359,360,360,361,362,363,364,366,367,368,369,370,370,371,372,373,374,375}

    30

    Returns: 0

  15. {340,341,342,343,343,345,346,346,347,348,351,351,352,352,353,354,355,357,358,358,360,360,361,362,362,364,366,367,362,369,370,370,370,372,373,374,375}

    30

    Returns: 3

  16. {574,604,619,585,587,579,600,621,594,611,581,618,596,584,614,617,595,594,581,582,575,591,596,584,593,609,591,584,576,613,577,605,589,608,617,609,604,603,588,606,612,620,598,615,577,602,580,616,622,601}

    50

    Returns: 24

  17. {352,345,337,349,346,351,339,346,337,343}

    10

    Returns: 2

  18. {640,640,644,643,642,640,639,646,643,632,640}

    11

    Returns: 8

  19. {564,551,551,550,549,547,563,548,551,547,557,543,555}

    12

    Returns: 2

  20. {599,590,598,589,604,605,588,605,588,598,591,600,590}

    13

    Returns: 5

  21. {518,523,516,519,520,514,522,517,518,520,511}

    10

    Returns: 1

  22. {421,422,433,432,432,428,424,431,427,420,410,423,434,433}

    13

    Returns: 2

  23. {492,500,498,522,517,497,503,504,509,496,516,522,505,525,508,512,510,514}

    18

    Returns: 1

  24. {332,332,330,334,322,316,315,321,331,319,331}

    10

    Returns: 1

  25. {391,400,406,393,401,389,398,397,397,390}

    8

    Returns: 0

  26. {445,464,463,449,467,449,457,445,433,431,430,436,439,449,427,457,450,464,445,435}

    18

    Returns: 4

  27. {510,526,517,517,518,504,511,506,504,499,522,494,521,514,520,505,518,518,527}

    16

    Returns: 1

  28. {435,460,437,461,440,460,460,452,432,453,438,452,455,460,434,438,445,454}

    17

    Returns: 5

  29. {668,652,667,650,668,649,613,647,662,622,668,634,610,598,625,620,663,623,613,631,613,650,622,672,638,665,610,647,595,660,615,598,620,631,662,627,624,644,653,598,610}

    36

    Returns: 9

  30. {522,513,516,518,514,509,510,513,511,516,511,510,513}

    12

    Returns: 6

  31. {623,601,621,612,603,644,599,612,618,618,656,659,619,616,654,620,627,607,623,656,645,632,602,603,623,649,643,625,603,648,608,616,618,641,598,637,611}

    35

    Returns: 7

  32. {428,497,446,455,418,467,476,434,460,461,457,447,421,423,434,452,434,505,481,474,457,444,499,428,480,454,492,464,419,470,449,480,414,475,498,477,451,449,462,475,488,415,424,411,416,424,484,412,407,442}

    42

    Returns: 0

  33. {415,453,460,443,418,437,413,415,451,422,462,453,420,426,463,462,412,455,440,433,417,423,422,423,426,449,453}

    22

    Returns: 2

  34. {578,528,564,565,539,537,562,521,520,525,545,554,571,573,577,556,578,580,573,520,582,519,572,542,568,573,516,545,568,568,581,522,558}

    33

    Returns: 9

  35. {629,629,663,643,631,629,643,635,649,657,648,653,645,633,634,627,631,638,633,633,656,659,664,627}

    24

    Returns: 12

  36. {445,429,436,462,406,442,403,407,416,435,416,403,462,445,412,430,394,452,465,406,437,388,457,422,411,397,402,455,447,408,450,429,407,461,407,402,390,453,437,448,405}

    38

    Returns: 7

  37. {360,362,383,382,394,376,359,394,366,367,359,383,382,391,364,367,363,384,386,359,362,360,384}

    19

    Returns: 5

  38. {666,673,685,670,669,652,685,652,636,657,649,668,658,633,684,634,647,637,682,633,654,640,651,681,638,660,656,671,631,648,648,680,650,677}

    29

    Returns: 0

  39. {702,695,710,710,688,681,702,701,692,693,691,679,699,683,698,699,688,702,676,677,703,690,675}

    19

    Returns: 1

  40. {631,604,605,565,626,602,609,570,566,630,591,634,573,571,609,596,595,615,622,634,593,566,598,577,616,611,583,622,576,619,596,555,594,572,553,625,625,595,599,564,579,578,542,554,591,550,606,545,617}

    44

    Returns: 3

  41. {488,514,503,561,486,473,527,476,526,554,544,553,537,493,495,540,534,545,518,500,542,548,533,519,542,531,549,539,537,508,511,524,511,516,505,480,476,523,471,518,532,502,552,473,506,524,552,480,489}

    49

    Returns: 9

  42. {446,451,453,439,414,453,439,416,454,439,446,444,433,431,420,429,409,413,416,449,455,441,445,413,421,446,440,448}

    24

    Returns: 3

  43. {696,676,679,695,694,691,706,692,700,686,682,687,695,689,687,669,679,674,703,708,673,677,695}

    20

    Returns: 1

  44. {312,278,330,295,285,329,287,346,279,325,307,334,278,345,311,349,308,288,286,305,301,310,330,318,351,305,326,279,293,302,290,287,307,351,295,334,306,286,301,293}

    37

    Returns: 9

  45. {514,484,518,516,463,492,495,491,504,483,485,511,494,486,493,494,466,470,459,503,516,472,509,478,487,511,510,513,518,505,493}

    28

    Returns: 2

  46. {656,657,710,702,699,705,677,669,685,672,656,689,662,658,672,644,642,654,670,666,644,666,711,649,666,698,663,647,688,667,670,651,659,659,690,692,700,691}

    32

    Returns: 1

  47. {421,397,459,468,424,480,460,422,432,476,438,412,409,447,414,440,399,460,478,437,447,451,436,461,439,444,420,394,441,405,444,474,417,452,478,482,440,438,474,475,399,458,476,457,465,409}

    44

    Returns: 9

  48. {347,378,395,400,348,416,406,403,413,408,380,404,385,355,347,370,353,404,377,386,362,396,399,389,416,359,357,361,410,361,398,405,382,344,373,422,376,372,337,421,365,370,397,404}

    41

    Returns: 3

  49. {565,562,585,537,588,532,564,579,570,590,576,560,592,535,555,543,576,537,575,543,580,548,557,578,586,568,546,560,537,554}

    26

    Returns: 1

  50. {493,482,493,477,496,494,488,492,475,478,476,498,486,468,481,494,477}

    14

    Returns: 0

  51. {337,264,277,279,288,326,297,279,325,333,323,296,315,275,292,312,263,312,254,322,269,285,265,259,309,308,274,254,327,333,297,335,330,261,319,322,279,278,337,343,327,289,256,309,336,311,254,278,271}

    44

    Returns: 7

  52. {642,627,631,642,637,629,628,626,629,633,621,639,648}

    12

    Returns: 1

  53. {483,486,507,539,511,549,489,492,501,520,492,548,541,530,491,519,501,488,489,487,539,520,508,498,527,488,530,543,547,540,509,503,537,498,523,545,516,532,542}

    38

    Returns: 7

  54. {402,393,423,415,372,380,384,406,352,387,379,401,361,378,356,407,413,394,420,353,391,386,396,357,356,376,359,389,396,374,421,381,381,375,372,426,359,361,406,419,362,374}

    39

    Returns: 5

  55. {530,530,553,491,497,550,520,518,521,504,503,541,540,499,493,553,528,547,480,480,494,544,485,509,488,500,502,502,544,515,503,503,492,526,531,501,524}

    31

    Returns: 1

  56. {408,416,448,433,419,424,429,443,449,425,411,432,450,448,416,426,418,449,415,414,428,418}

    21

    Returns: 4

  57. {919,329,131,452,752,398,166,116,852,982,453,224,884,927,982,453,256,912,246,490,224,811,920,442,153,558,446,13,208,341,464,828,685,86,40,153,555,453,811,753,226,725,329,131,153,530,802,251,398,469}

    47

    Returns: 7

  58. {423,779,779,81,958,903,809,281,99,865,542,195,258,304,281,527,41,602,241,600,42,79,955,414,470,817,978,75,852,734,861,595,467,467,506,350,178,598,900,734,527,288,75,825,569,299,14,80,965,230}

    46

    Returns: 2

  59. {213,114,441,686,505,714,643,134,347,578,585,505,996,985,206,792,52,385,348,372,681,686,996,716,108,985,441,48,716,823,206,585,811,394,52,803,186,64,312,651,78,728,910,415,262,718,89,38,485,86}

    40

    Returns: 0

  60. {565,790,379,460,982,747,565,790,482,972,569,790,830,889,982,469,678,818,718,432,984,432,888,337,220,801,6,557,565,559,569,432,6,426,40,80,250,830,939,974,518,762,675,530,638,758,308,116,604,657}

    40

    Returns: 0

  61. {83,767,231,391,884,474,705,382,31,861,720,323,897,900,634,997,29,515,539,735,323,83,419,539,210,434,724,128,978,506,231,515,665,492,284,702,673,657,680,83,612,562,757,224,422,9,881,128,224,722}

    50

    Returns: 8

  62. {372,63,130,103,202,621,40,893,913,486,124,114,488,124,103,40,545,262,738,708,37,738,808,541,545,269,525,816,738,4,656,206,415,67,782,761,25,483,25,482,738,899,760,71,862,848,420,894,193,538}

    41

    Returns: 0

  63. {682,344,718,748,796,389,281,211,942,344,719,262,262,378,673,894,461,431,985,249,781,281,129,712,474,712,449,389,328,267,76,821,639,389,123,568,776,378,596,328,139,397,340,211,894,378,378,595,713,443}

    47

    Returns: 9

  64. {587,762,762,680,845,144,698,584,845,752,738,579,600,471,895,284,587,305,466,487,587,181,488,39,993,488,619,560,659,756,895,680,733,206,471,976,976,600,799,116,883,382,1000,488,203,643,850,918,272,132}

    42

    Returns: 3

  65. {36,754,277,940,800,897,566,163,781,130,277,480,246,304,528,785,36,185,47,772,978,134,940,500,566,553,582,791,643,277,643,742,605,921,566,643,735,134,412,819,641,447,34,84,250,340,166,196,168,927}

    40

    Returns: 0

  66. {840,276,590,452,73,330,646,633,276,972,898,285,324,888,402,118,937,498,585,330,596,378,100,56,598,385,482,710,665,264,30,646,966,482,44,119,646,616,216,472,937,385,589,633,586,727,895,779,407,48}

    46

    Returns: 4

  67. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 501, 502, 503, 503, 505, 505, 506 }

    40

    Returns: 140

  68. {7, 5, 4, 5, 8, 3, 3, 3, 7, 2, 1, 9, 4, 5, 9, 10, 6, 6, 5, 2, 4, 2, 1, 3, 1, 2, 6, 5, 7, 6, 6, 9, 1, 4, 1, 4, 6, 9, 9, 7, 3, 1, 6, 7, 1, 6, 10, 9, 9, 9 }

    46

    Returns: 412

  69. {1, 2, 3, 4, 4, 5, 7, 7, 8 }

    9

    Returns: 4

  70. {1, 100 }

    2

    Returns: 0

  71. {1, 1000 }

    2

    Returns: 0

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: