Problem Statement
Most telephones today are equipped with a speed dialing facility, which makes it possible to assign telephone numbers to single keys on your phone - although it's usually required to press some special speed dialing key first. However, there's usually a limit on how many numbers you can assign to the speed dial slots, so deciding which numbers you should assign can sometimes be tricky, if you want the optimal assignment.
Assume that you have made a list of all phone numbers you dial, and how many times you are dialing them each month. Now you want to find out which phone numbers you should assign to speed dialing slots in order to minimize the number of keys you have to press. For the purposes of this problem, you only have to return the total number of keypresses required if the optimal assignment is done.
In this problem, we assume that speed dialing a number takes exactly two keypresses, while dialing a number the default way requires exactly the same amount of keypresses as the length of the phone number. It's not possible to speed dial a number partially (for instance, speed dialing and then add two extra digits, or speed dialing twice to produce a single compound number).
Create a class SpeedDial containing the method assignNumbers which takes as parameters a
Definition
- Class:
- SpeedDial
- Method:
- assignNumbers
- Parameters:
- int[], int[], int
- Returns:
- int
- Method signature:
- int assignNumbers(int[] numbers, int[] howMany, int slots)
- (be sure your method is public)
Notes
- There may be more speed dialing slots than actual phone numbers. In that case, some slots will be left unused (see example 1).
- Since the numbers are given as int, they can't contain leading zeros.
Constraints
- numbers will contain between 1 and 50 elements, inclusive.
- howMany will contain between 1 and 50 elements, inclusive.
- numbers will contain the same number of elements as howMany.
- Each element in numbers is between 1000 and 999999999, inclusive.
- Each element in howMany is between 1 and 1000, inclusive.
- The elements in numbers are unique.
- slots is between 1 and 9, inclusive.
Examples
{9753,1245987,4833,34473,8733,1437}
{5,2,4,3,2,4}
4
Returns: 52
If we would dial all numbers without using speed dialing, the number of keypresses required would be 4*5 + 7*2 + 4*4 + 5*3 + 4*2 + 4*4 = 89. The number of keypresses saved if we would assign each of the numbers to a speed dialing slot would be 10, 10, 8, 9, 4, and 8. So we should definitely assign 9753, 1245987 and 34473 to a speed dialing slot, and either 4833 or 1437. We would then save 10 + 10 + 9 + 8 = 37 keypresses, so the total number of keypresses required would be 89 - 37 = 52.
{124839,9876,43823}
{73,95,102}
5
Returns: 540
Here we have more slots than phone numbers, so all numbers in the list should be assigned to speed dialing slots. The total number of keypresses required would be 2*73 + 2*95 + 2*102 = 540.
{8925135,6046333,68260,29405,4830502,378742,13561,6090,976234,71994}
{5,35,2,34,33,14,43,42,29,10}
5
Returns: 695
{553229,86184,14683,65568,68056,15411,21096779,2603,68881,71709}
{91,2,62,81,79,25,100,4,30,72}
4
Returns: 1673
{388659,1504343,93915046,9872,3389,83587895,32032,73280911,80058046,1738,823365,70925,41223,789119,3019,25741778,75087,801483,54627,29863313}
{100,26,18,176,163,140,183,108,160,53,135,50,49,119,101,18,4,191,113,26}
3
Returns: 8615
{707737,3442897,5600161,51681,191891,228748,6867,13408,9313651,265410,25086,57107987,44832,9896445,684920,143324,92254252,56328,73888235,668926}
{56,185,138,112,112,77,48,19,12,195,23,124,154,129,192,130,51,158,155,44}
8
Returns: 7244
{20352,900722594,68469,47399,719212,17566240,99962,83166,31160989,1395,8068591,232756084,42488967,199505469,51916,5452896,6701344,48499112,2749,2547,42493,85947,237504246,7488136,37581,53871719,515522,9618,713032,290949}
{344,321,380,486,43,467,69,424,277,392,344,253,218,310,77,413,275,358,129,329,365,455,422,351,38,216,51,496,270,418}
9
Returns: 37357
{8219,8039,9139,6241,8114,8077,2922,9242,4814,5932,5665,7176,2542,5136,9737,9388,6707,5585,4026,7373,6394,6585,1024,7452,6245,4902,9206,4634,5670,9093}
{80,172,379,172,917,216,339,976,864,529,713,365,766,582,654,500,932,367,388,355,518,722,197,184,597,680,370,320,997,968}
9
Returns: 47566
{219039260,55322033,53456,107376686,10124,6467710,5280,3280109,17469297,49955341,994114580,608424270,199885867,37589343,8454594,57386,80576620,151761,53898887,7258690,7853861,69033688,751151,599714,638921,9296672,204915355,801597819,458930438,78321312,404535,37800669,332733,9168,3542,445981384,1860,46463,88786,66177078,2304736,6383674,202200,312433,540029,1518,30761,353656,24942258,53974}
{893,382,265,42,246,353,316,591,734,292,425,858,176,629,696,793,292,822,746,960,679,597,518,171,239,338,361,719,556,75,418,787,17,967,542,817,564,489,84,280,908,212,286,704,199,496,561,258,373,643}
1
Returns: 160764
{2514952,79206,6984468,47406,8325722,2095,45722783,182871,6483739,5024497,724834,50844,8880936,214168596,1523209,2605160,53211,63402067,4623873,3337,9949,2216,48739896,95828761,1159065,667261,925447503,17406353,2934,9101244,44038758,36153,63383,1441,9188714,6873,7585499,997117,70341901,190036569,17682605,3940,9095,139377,3550,633557424,6630,3854,67797623,6946829}
{168,401,766,221,768,961,494,248,185,706,20,388,445,150,4,331,459,419,379,486,107,690,638,728,988,723,40,742,949,762,999,864,90,96,380,822,146,961,303,523,294,320,954,74,303,361,747,170,858,309}
9
Returns: 108272
{279164,3702,1620,604627021,827658,371250816,961856,1975702,1054,684016,58098,65358191,3512,32117072,6197312,935605,7610485,552849466,11804,67506726,5523609,4722,6470833,94866,6677,9524654,796711,7850,50203990,533740,747320,68955231,7119,2062,56199753,75230,82865132,316121,99479234,6820230,4630482,1934,804872,58925,23012,521847,53195527,83610,2636,3193197}
{548,607,867,671,296,539,594,444,739,711,214,258,872,213,293,612,587,126,873,810,21,901,428,12,968,238,604,985,551,113,598,728,787,499,819,391,729,390,398,977,629,606,993,802,478,331,310,779,611,280}
9
Returns: 124935
{26502784,765342978,98588357,9613,30407564,6870702,807270,950720,251810,9396,4653,4141,3629,5934,8317020,579736,808371313,760068554,13986,9596670,5832494,53475655,823746,13141871,685056,27594516,540667300,951200,4473,3591601,723947,78961815,3338131,201951,73220,4067209,24742,3633330,5102,376225,955109216,53741,3211,226693016,67315320,2314854,5732189,560748,819618912,48175}
{938,516,30,44,556,927,789,855,768,924,624,352,993,829,258,87,966,142,363,224,385,801,463,243,29,497,214,617,28,567,385,89,294,687,854,57,927,600,177,356,604,29,447,643,958,228,391,334,374,979}
9
Returns: 113856
{881210052,8912838,843165,97583,6597967,63943,41061,85062,88081,8669116,573039355,9495817,10972,5631,168391035,6760,8919,1548182,442549061,16217079,3164463,1153378,86049,211410,23541271,8854331,580336371,276564,160143,84636309,2631314,2373,223799,845537112,9274,92013,67052,41907193,9690,474748882,5217011,787426,15827,1954,4063,6499,85150236,7466063,49874,47671}
{976,56,175,694,831,558,313,628,732,327,444,546,302,27,873,770,239,502,263,388,952,779,392,214,707,419,615,148,745,677,605,959,267,434,824,129,922,220,706,422,111,449,862,871,772,602,429,614,664,578}
9
Returns: 123273
{52750}
{570}
9
Returns: 1140
{85061766,7516223,686355,8822,198570879,2039481,72068,4522554,74077,974450378,64050817,8203,82252,688454,931337185,8859412,353042,691549,7809350,551906044,8381,393484376,242978443,929536,55409,296788818,3502276,25796,8438375,7399119,851995,13474,7239320,97533,7337874,716888,25581,95360,252364624,1866,160646100,87096,88633434,47138376,1160,58226,988515533,69423423,410653,16820327}
{150,872,768,579,705,308,757,668,111,6,209,563,92,304,361,985,298,656,637,500,297,159,387,521,824,915,121,372,66,394,488,88,360,540,331,986,643,801,540,70,232,246,889,921,335,401,524,457,120,932}
9
Returns: 112415
{39894,8984,37478716,2216,393108848,5361047,269701713,43194,429417,4714,92419149,38408182,82964919,9804,8456,47923671,5104,286067,31592019,10179,435974298,6841973,1794,7628,61842230,842728761,620629615,5239,93912,53484838,82483131,908579,61301,497231,90752455,640550,42377,993010,874713630,34252,57516161,684380745,115607754,935329822,351102,1319,92304715,675675256,5858,41719387}
{653,820,963,12,444,767,613,316,992,583,613,160,32,680,742,753,629,881,424,745,852,918,397,753,461,83,489,348,679,864,976,88,777,738,751,257,385,556,238,138,351,883,19,272,504,969,766,524,939,490}
9
Returns: 135256
{123370782,5305211,3718154,1669,995366,5665,924373,64899582,550660760,4970032,4680051,6328,26398,60793128,9053648,186342442,11975,1936,4363992,150235586,98744720,460283,9588162,912677,54423564,5933,897876,9714871,876728696,91846,50011218,66599796,45578,188115893,2715,10252,3021823,91544,264266733,8685875,4363,18227559,265861496,16746,818421,941564,72836,934729519,84403,2469}
{729,865,368,889,931,468,467,552,309,779,260,851,18,183,5,998,614,251,378,564,38,78,332,594,202,903,47,775,253,980,513,663,613,305,89,628,641,981,782,181,691,695,577,937,848,440,645,438,48,808}
9
Returns: 125083
{76735,39359,60733,60202,2695,64354,159929,1873754,64910,70659,5309,2529,57478,708564,295643,6113,1077624,7394,38955,228904,3870368,718477,8901,3649214,4421867,466045,155453,583804,4642,1903268,353516,785240,61620,75936,726235,7931510,2488197,81541,6501,2792}
{13,71,57,20,30,40,29,37,33,41,9,85,31,51,10,42,29,44,48,13,75,78,66,28,32,2,79,2,70,97,68,39,78,79,58,33,95,15,40,19}
7
Returns: 7334
{5531512,79790391,1971,5107,44874,50378,60971,45730454,52322237,1956755,200848,38369,343557,32808372,93763604}
{335,443,470,565,163,550,638,775,887,575,789,196,251,126,365}
9
Returns: 19163
{6908,3576971,72519,42411,5707,842603,14491280,802792,1508,4456339,602372,6170617,4016,1838,2498,58375910,9437,9376,8307,3076,49405086,7710,803256,55357,220661,877004,832423,8374775,303723,5453356,44914823,70020118,978843,46641,547980,313574,88787632,77616524,78597541,3053,56253552,60277,3591,33149,295504,97429,915258,42368542,617167,104506}
{376,135,297,111,63,215,244,122,304,62,220,78,163,267,58,349,499,492,401,431,166,433,435,258,161,288,426,404,397,232,23,195,17,355,177,7,421,186,271,285,117,100,309,127,188,255,441,226,359,396}
8
Returns: 55832
{ 1111, 2222222, 3333, 44444, 5555, 6666 }
{ 5, 2, 4, 3, 2, 4 }
4
Returns: 52
{ 4564, 45645, 7893 }
{ 4, 5, 6 }
1
Returns: 50
{ 9753, 1245987, 4833, 34473, 8733, 1437 }
{ 5, 2, 4, 3, 2, 4 }
4
Returns: 52
{ 100000, 100002, 100003, 100005 }
{ 1, 1, 1, 1 }
8
Returns: 8
{ 3002, 3001, 3000, 9999999 }
{ 7, 6, 5, 4 }
3
Returns: 54
{ 1000, 111111 }
{ 10, 6 }
1
Returns: 52
{ 8925135, 6046333, 68260, 29405, 4830502, 378742, 13561, 6090, 976234, 71994 }
{ 5, 35, 2, 34, 33, 14, 43, 42, 29, 10 }
5
Returns: 695
{ 1111, 111111 }
{ 10, 6 }
1
Returns: 52
{ 4333, 455568, 449975, 3448997, 6889765, 356597896, 665874, 2246 }
{ 3, 4, 5, 8, 7, 2, 2, 3 }
4
Returns: 102
{ 123456789, 12345 }
{ 2, 4 }
1
Returns: 24
{ 1111, 2222222, 3333, 44444, 5555, 6666 }
{ 5, 2, 4, 3, 2, 4 }
4
Returns: 52
{ 4564, 45645, 7893 }
{ 4, 5, 6 }
1
Returns: 50
{ 9753, 1245987, 4833, 34473, 8733, 1437 }
{ 5, 2, 4, 3, 2, 4 }
4
Returns: 52
{ 100000, 100002, 100003, 100005 }
{ 1, 1, 1, 1 }
8
Returns: 8
{ 3002, 3001, 3000, 9999999 }
{ 7, 6, 5, 4 }
3
Returns: 54
{ 1000, 111111 }
{ 10, 6 }
1
Returns: 52
{ 8925135, 6046333, 68260, 29405, 4830502, 378742, 13561, 6090, 976234, 71994 }
{ 5, 35, 2, 34, 33, 14, 43, 42, 29, 10 }
5
Returns: 695
{ 1111, 111111 }
{ 10, 6 }
1
Returns: 52
{ 4333, 455568, 449975, 3448997, 6889765, 356597896, 665874, 2246 }
{ 3, 4, 5, 8, 7, 2, 2, 3 }
4
Returns: 102
{ 123456789, 12345 }
{ 2, 4 }
1
Returns: 24