Statistics

Problem Statement for "IDs"

Problem Statement

You are working on the backend of a particular system in which you want to assign a unique ID to each client. However, the system is distributed, and there are a number of components, each of must be able to assign IDs to clients. Thus, you have to figure out how to assign each client a unique ID, while maintaining the distributed nature of the system. In other words, you want to have each of the components assign the IDs with as little communication between the components as possible. You have decided that it is more important that the system remain as distributed as possible than it is that all of the clients have unique IDs. Thus, you are considering having each of the components independently assign IDs randomly from a large pool of possible IDs, and synchronizing the assigned IDs at the end of each day. In other words, each component will update its list of available IDs at the end of each day, based on the IDs assigned by all of the components.

Your task is to simulate this system and figure out the probability that an ID is assigned by more than one component. You will be given an int, num, which represents the number of IDs in the pool of possible IDs that each component may assign at the beginning of some day. You will also be given a int[], counts, each of whose elements represents the number of IDs that some component assigns during the day. You are to return a double representing the probability that more than one component will assign the same ID.

Definition

Class:
IDs
Method:
collisionProbability
Parameters:
int, int[]
Returns:
double
Method signature:
double collisionProbability(int num, int[] counts)
(be sure your method is public)

Notes

  • Due to memory constraints in the components, they do not 'remember' the IDs that they have assigned. Thus, it is possible for two components to both assign a particular ID, and also for a single component to assign a particular ID more than once.
  • Note that because the return type is a double, your result need not be precisely the same as the result of the reference solution. As long as your result is either within 10-9 of the reference result, or within (10-9 * reference result) of the reference result, your solution will be judged correct. In other words, as long as the first 10 digits of your solution's result are within one of the reference result, you will be judged correct.

Constraints

  • num will be between 1,000 and 2,000,000,000, inclusive.
  • counts will contain between 2 and 50 elements, inclusive.
  • Each element of counts will be between 0 and 1,000, inclusive.

Examples

  1. 1000

    {1,2}

    Returns: 0.002998000000000056

    There are a total of three clients during this day. Lets call them c1, c2, and c3. There are 4 possible ways for a particular ID to be assigned to more than one person: 1) c1 and c2 get the same ID, while c3 gets a different ID 2) c1 and c3 get the same ID, while c2 gets a different ID 3) c2 and c3 get the same ID, while c1 gets a different ID 4) c1, c2, and c3 all get the same ID. (1), (2), and (3) all have the same probability of 999/1,000,000. (4) has a probability of 1/1,000,000. So, the total probability is (999+999+999+1)/1,000,000 = 0.002998. (Note that the extra digits are due to double imprecision)

  2. 1000

    {234,543,640}

    Returns: 1.0

    Here, there are more clients than IDs, so there must be some ID which is assigned to more than one person.

  3. 2000000000

    {100,150,482,71,349,57,751,673,761,942}

    Returns: 0.004688119695273496

    With 2 billions IDs, the chance that collision will occur is relatively small.

  4. 200000000

    {100,150,482,71,349,57,751,673,761,942}

    Returns: 0.04590472119127553

    This is the same as example 2, except the pool has been reduced by a factor of 10. It seems somewhat counterintuitive that when assigning a total of only 4336 out of 200 million IDs, there is about a 4.6% chance of a collision, but it is true.

  5. 2000000000

    {1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000}

    Returns: 0.4647346684700865

  6. 2000000

    {25,25}

    Returns: 6.123175102596967E-4

  7. 2000000000

    {1,1}

    Returns: 5.000000413701855E-10

  8. 4756

    {0,1,0,0}

    Returns: 0.0

    If only one ID gets assigned, the probability of a collision is 0.

  9. 1576728816

    {21,673,552,690,830,152,382,404,850,645,860,854,563,807,448,108,544,967,991}

    Returns: 0.039962499297501175

  10. 1064853942

    {235,51,460,541,952,31,854,95,257,500,492,678,965,446,832,135,500,330,771,542}

    Returns: 0.042926672559867374

  11. 605642287

    {3,285,462,920,761,363,917,941,813,513,11,847,727,747,281,66,919}

    Returns: 0.07290298285281105

  12. 54421987

    {10,556,894,831,528,721}

    Returns: 0.10872618344040341

  13. 1138063574

    {19,876,307,574,795,47,860,513,595,715,831,677,694,361,503,438,167,13,279,76,815,532,189,278,883,785,740,932}

    Returns: 0.08815878547673806

  14. 1259784162

    {571,991,977,745,958,432,59,137,77,593,83,361,811,815,57,904,560,12,722,414,992,819,872,867,119,184,865,426,602,774,246,121,170,978,884,381,576,969,353,687,531,945,94,879,13,671,346,33,732,193}

    Returns: 0.2448496551220558

  15. 1593317662

    {372,37,882,667,932,100,492,394,513,114,749,269,554,823}

    Returns: 0.014818824767573235

  16. 29464025

    {629,381,172,160,149,827,983,432,950,41,893,144,893,803,2,65,157,184,927,239,154}

    Returns: 0.7610834371809063

  17. 1821465006

    {331,273}

    Returns: 9.997277825113393E-5

  18. 589445721

    {271,187,740,416,148,141,595,214,211,419,110,429,666,910,153,91,955,159,581,271,448,97,661,649}

    Returns: 0.07401967217642791

  19. 1583533214

    {125,942,292,235,566}

    Returns: 0.0014713964792579803

  20. 719020935

    {486,341,980,344,775,406,677,154,113,397,309,202,55,452,719,13,728,85,847,934,303,582,316,932,285,217,328,655,827,468,664,662,553,910,795,573,897,673}

    Returns: 0.23561665677194144

  21. 195156828

    {56,807,409,15,149,867,722,518,700,295,519,226,557,17,233,947,42,169,929,808,252,384,918,593,630,232,452,70,791,21,703,74,679,31,84,447,127,250,319,246}

    Returns: 0.49322300741200265

  22. 474634556

    {409,507,177,392,801,254,929,690,234,863,499,361,49,79,404,259,236,673,94,44,644,455,644,270,878,300,811,147,397,931,48,689,382,133,864,591,385,918}

    Returns: 0.2741634947603401

  23. 1767560683

    {259,901,950,892,931,846}

    Returns: 0.006438391699574719

  24. 920606346

    {74,979,250,517,813,507,305,741,943,559,46,615,326,450,166,209,893,808,679,1,254,489,255,530,584,991,775,910,781,252,291,579,359,185,238,331,446,242,128,354,926,42,92,960,484,291,78}

    Returns: 0.22616806138041423

  25. 1291729360

    {912,804,560,232,528,862,773,820,792,697,876,833,961,388,911,7,762,428,861,639,188,179,822,768,516,595,664,806,735,735,907,13,878,721,963}

    Returns: 0.18713095260911916

  26. 97762161

    {737,753,810,743,608,825,73,307,611,772,110,337,47,209,51,558,612,782,437,285,664}

    Returns: 0.4206391331230728

  27. 1354805923

    {989,360,584,968,737,692,695,581,109,616,374,103,454,400,401,278,345,796,333,265,422,293,967,56,260,801,564,272,384,763,655,379,138,945,310,584}

    Returns: 0.11120340390258476

  28. 1753597821

    {550,257,613,498,475,230,262,123,334,498,128,981,323,402,565,368,979,862,633,380,145}

    Returns: 0.025964541556212195

  29. 1950034345

    {859,754,224,351,702,675,683,226,857,822,405,902,240,639,186,272,422,357,388,749,849,407,634,120,471,254,295,330,920,444,68,259,383,118,443,423,233,953,610,318}

    Returns: 0.09059103394285639

  30. 1847303003

    {861,10,131,413,165,600,135,557,685,367,404,712,285,83,875,294,327,384,439,166,337}

    Returns: 0.018163729544728446

  31. 589876498

    {137,834,742,120,877,889,398,150,248,137,782,427,862,508,886,135,726,666,408,562,980,234}

    Returns: 0.10968713047993073

  32. 84633286

    {591,966,274,495,76,400}

    Returns: 0.04530906868856055

  33. 351509353

    {668,200,365,585,502,870,571,734,662,447,955,932,596,917,83,681,900,227,652,174,726,906,615,614,964,792,490,310,225,193,733,670,686,901,434,614,145,197,906,355,548,380,112,545,630,383,450,857,280,954}

    Returns: 0.680853923078582

  34. 1568870788

    {956,815,262,395,520,494,997,647,567,685}

    Returns: 0.012718701494613405

  35. 136925927

    {674,30,702,200,731,24,365,761,202,29,430,551,156,348,567,928,582,396,298,504,334,219}

    Returns: 0.2575464999447581

  36. 1526101450

    {758,900,219,414,402,848,171,317,859,873,858,212,823,536,772,229,518,286,166,725,72,320,256,627}

    Returns: 0.04729469023918986

  37. 35188919

    {267,123,160,393,573,691,531,208,530,775,753,636,768,255,536,987,506,613,449,663,402,520,107,548,759,390,196,568,322,873,194,345,813,589,545,551}

    Returns: 0.9906804799347564

  38. 893277911

    {59,902,347,783,158,47,633,926,368,802,946,835,311,101,846,680,266,493,964,158,538,989,457,57,383,545,757,30,711,15,603,601,210}

    Returns: 0.1416711895245517

  39. 70185347

    {418,261,98,751,391,819,773,360,749,319,465,117,945,468,262,810,861,739,567,454,538,446,907,383,457,47,253,300,884,588,772,765}

    Returns: 0.8713800483034007

  40. 1155978589

    {117,979,1,621,20,672,399,36,427,317,660,179,655,781,508,234,702,288,749,802,907,274,835,105,625}

    Returns: 0.059340600826282786

  41. 1945328903

    {654,214,498,155,357,642,192,84,587,941,953,336,941,815,566,591,966,784,477,94,744,294,252,303,804,638,223,193,984}

    Returns: 0.058256134334522036

  42. 487872393

    {987,198,115,618,737,55,116,720,145,562,294,413,618,35,428,635,187,232,227}

    Returns: 0.05345535628930542

  43. 687706162

    {590,846,886,571,875,509,651,298,504,590,629,827,850,578,226,310,86,857,45,554,719,98,961,746,896,257,542,545,557,934,896,509,836,0,210,780,400,543,600,798,679,512,961,186,6,133,759,628}

    Returns: 0.41077706408883774

  44. 1882060295

    {325,199,267,99,713,410,379,628,695,394,116,155,187,7,903,274,968,717,671,598,218,648,145,496,199,552,799,788,524,378,899,173,718,854,539,330,250}

    Returns: 0.07570826731533475

  45. 1356959844

    {24,146,547,493,625,149,978,997,367}

    Returns: 0.00687036684791853

  46. 947891029

    {276,504,882,850,260,606,23,491,410,300,665,659,461,335,743,752,116,410,485,229,856,111,397,462,395,424,169,698,547,279}

    Returns: 0.09550184622459146

  47. 1972474448

    {855,722,379,229,548,134,199}

    Returns: 0.0023792731696898883

  48. 1071129590

    {243,403,513,845,625,247,30,119,486,221,977,77,131,925,354,465,873,480,861,307,630,835,732,61,540,550,690,676,265,772,788,369,631,112,869,786,888,5,981,58,889,936,105,987,289,438,305,159,740}

    Returns: 0.25771887524406545

  49. 1122096277

    {540,616,697,329,122,648,840,582,526,69,801,400,685,138,826,180,523,126,525,729,851,833,477,707,586,264,581,26,855,66,855,88,793,27,823,95,995}

    Returns: 0.14605270151404426

  50. 908650826

    {545,640,370,915,595,33,608,871,912,620,421,285,83,631,904,612,36,800,173,709,870,963,404,126,892,829,837,445,913,422,486,412,86,405,159,379,766,804,897,326,415,433,470,932,291,355,43,10,88,116}

    Returns: 0.29759162254485394

  51. 237427771

    {445,341,354,238,973,462,671,223,464,592,401}

    Returns: 0.05460026855438771

  52. 1017954527

    {194,976,182,713,728,502,221,822,148,289,827,653,168,802,480,420,457,444,796,286,636,289,469,289,468,788,831,835,999,527,616,48,885,355,299,534,228,495,178,11}

    Returns: 0.17656412160256385

  53. 972330507

    {331,422,210,837,793,400,301,69,431,506,617,304,631,440,858,320,154,591,984,394,479,646,939,250,729,818,421,774}

    Returns: 0.10447303675140107

  54. 741422245

    {497,448,676,568,256,767,125,911,723,563,367,870,441,797,682,350,918,952,186,850,551,898,104,954,551,683,528,718,157}

    Returns: 0.17879112991985335

  55. 1984873320

    {626,207,146,630,58,13,121,729,445,304,393,620,728,221,755,35,997,13}

    Returns: 0.01240898085468678

  56. 1217046996

    {801,192,799,774,215,300,202,256,24,249,89,340,598,82,584,384,149,339}

    Returns: 0.016565551433414982

  57. 232331807

    {458,199,234,130,569,352,59,826,797,136,693,829,625,962,484,427,326,64,814,57,51,202,827,368,742,433,322,230,814,266,406,646,437,596,202,606,295,788,12}

    Returns: 0.4742283333703391

  58. 149336740

    {151,145,937,388,631,838,552,444,925,160,711,646,831,397,472,221,673,297,212,654,565,433,229,936,261,821,688,122,54,51,529,358,177,544,876,880,676,433,373,445}

    Returns: 0.7285896913331884

  59. 2000000000

    {1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000 }

    Returns: 0.41080174472903797

  60. 2000000000

    {100, 150, 482, 71, 349, 57, 751, 673, 761, 942 }

    Returns: 0.004688119695273496

  61. 1000

    {1, 2 }

    Returns: 0.002998000000000056

  62. 1000

    {234, 543, 640 }

    Returns: 1.0

  63. 200000000

    {100, 150, 482, 71, 349, 57, 751, 673, 761, 942 }

    Returns: 0.04590472119127553

  64. 1000

    {100, 10 }

    Returns: 0.9980239332971031

  65. 4756

    {0, 1, 0, 0 }

    Returns: 0.0

  66. 1000

    {2, 7, 8 }

    Returns: 0.12781544076827323

  67. 200000000

    {100, 150, 482, 71, 349, 57, 751, 673, 761, 942, 127 }

    Returns: 0.04856616789453028

  68. 1000

    {0, 0, 0, 0, 0, 0 }

    Returns: 0.0

  69. 2000000000

    {900, 923, 999, 123, 126, 4, 194, 990, 920, 910, 990, 999, 246, 764, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0 }

    Returns: 0.020442934815579128

  70. 1000000

    {0, 100 }

    Returns: 0.00493793231202766

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: