Statistics

Problem Statement for "CommonFactors"

Problem Statement

You are given a list of numbers in a int[] n. A number k is a factor of number m if m can be exactly divided into k. Find the factor greater than 1 that is shared by the most elements in n. If there are several such factors, return the largest one among them.

Definition

Class:
CommonFactors
Method:
mostCommon
Parameters:
int[]
Returns:
int
Method signature:
int mostCommon(int[] n)
(be sure your method is public)

Constraints

  • n will contain between 1 and 50 elements, inclusive.
  • Each element of n will be between 2 and 1000000000, inclusive.

Examples

  1. {2, 3, 4, 6}

    Returns: 2

    2 is a factor of 3 elements of n (2, 4 and 6). 3 is a factor of two elements (3 and 6). 4 and 6 are not factors of any numbers except themselves.

  2. {2, 3, 6}

    Returns: 3

    Both 2 and 3 are factors of exactly two numbers. Based on the tie-breaker rule, we pick the larger.

  3. {2, 3, 5, 7}

    Returns: 7

    No factor appears more than once, so again we use the tie-breaker rule.

  4. {2, 3, 5, 6, 7, 9, 11, 12}

    Returns: 3

  5. {24, 12, 37, 18, 11}

    Returns: 6

  6. {3, 49, 7, 100, 100}

    Returns: 100

  7. {123456789, 987654321, 246813579, 975318642}

    Returns: 9

  8. {260920719}

    Returns: 260920719

  9. {141374913, 377707870, 667262683}

    Returns: 667262683

  10. {5, 5, 5, 10}

    Returns: 5

  11. {23,28,40,70,81}

    Returns: 2

  12. {1000000000, 999999999, 999999999}

    Returns: 999999999

  13. {404441476,638341248,97469569,925101697,764654040,466150820,138699055,477438629,329567075,355640233,967545270,748956620,490843177,194321692,733971596,852265536,223152757,120683968,835011720,158764303,724799037,602317393,680394649,1765907,308343053,764038861,708169699,629622400,541228652,966016829,650331497,408849895,636407494,631896317,48444987,277253568,92964054,326923907,19270421,447052658}

    Returns: 2

  14. {86072743,270388365,358005464,110962272,992167532,365824700,880534350,366861940,4009545,241675616,768850744,404305339,34501613,971732616,364080131,512416005,278773129,783107519,547387063,360200286,792305052,321857453,943100154,387172341,319054902,168609858,371837080,443979144,369581759,604187488}

    Returns: 2

  15. {683025479,549171269,625233412,61048449,699098944,135960639,209836006,522328556,919994950,909063637,833153963,74493826,247141719,226695597,233041287,66482246,946225285,354298413,425672293,12270868,787814498,42665542,971166610,794000804,437986016,356067002,489214182,115102232}

    Returns: 2

  16. {750374377,424700260,203419388,399671674,401185811}

    Returns: 2

  17. {764335572,536503196,781951010,797255516}

    Returns: 2

  18. {663801789,492096245,640696764,981943547,534558177,335149348,995570659,515222251,391020894,646864712}

    Returns: 3

  19. {930523812,105321289,873348295,129508973,367801845,570098519,399182618,41507960,413299024,339124561,625551760,12058735,802672088,517929196,298366368,615929365,374116838,904425025,86388648,659333229,271493137,379532457,409357369,695554018,397449911,547804713,516112864,790570736,116550148,628052831,812722027,538682699,208395899,593970656}

    Returns: 2

  20. {328134537,70753277,564759850,104651750,856741190,172677458,445754886,151363910,897512912,757637679,819048047,896962940,314280272,796642244,84114433,205523551,327319145,191363514,848436951,317097008,28975726,227262914,568131328}

    Returns: 2

  21. {149291516,276715934,438571096,508120358,71628333,752137124,535012603,900680601,98293305,309105098,203220010,128724397,966163873,299487531,700090289,484060824,612312794,474566162,84278226,853225529,189633131,938161790,356821418,295605719,332463265,349759281,851765275,871565163,672211885,377632558,876788020,720569193,602982998,401969612,603825688,389309704,297200918,467997491,209697128,409830153,971235275,489107311,266728997,127650559,401026011,699979245,383380771}

    Returns: 2

  22. {687708378,359707534,94869733,823404133,273237944,704925477,3795982,512885153,206015587,152930439,170767427,729011833,656512499,754808843,755024791,56562007,682895183,898561179,905066609,112540067,246650458,262226999,899274230,124301970,478210449,17009914,536536813,757680237,192577601,280402601,776876330,195108950,654949665,819311797,632072568,463748753,596344709,3183306,306288123}

    Returns: 2

  23. {479226112}

    Returns: 479226112

  24. {586693406}

    Returns: 586693406

  25. {13127566,265041769,484091640,90064586,920278072,172740639,123543859,334061444,951226949,41075647,884993910,200346053,150468827,299062908,793893456,675063431,372068644,947007596,161826969,885960161,45286656,259628952,477136731,430509389,190203429,739185273,545547843,954035818}

    Returns: 2

  26. {318598926,880793213,977840721,773307085,814581334,345238567,977326929,846381664,630757987,40507436,710123837,442180395,710793435,448106170,794212401,519260406,741516292,820048928,536050141,970749139,606044233,819482684,8696139,389969349,86908997,411312223,379936040,86064101,819181382,2825141,490407050,349621773,493596256,834316849,681722939}

    Returns: 2

  27. {309677541,619715571,874599039,992455959,678863227,437207341,896977245,750760793,177630365,869861006,62151015,115835190,750620067,396253228,996890366,19869090,163762510,31093479,719566881,220247746,707401931,215849042,968278706,315176726,149421633,959370017,778975546,9306908,938368976,228514314,313583672,629359484,656580388,588772654,938130915,889750957,723306358,94893575,550871670,908218145,347836435,431508422,160411895,471443176,732624233,303756356,713834107,550678492,526412427}

    Returns: 2

  28. {174822390,67371846,527357757,671997189}

    Returns: 3

  29. {908791303,636156022,696432471,975991308,193650246,59167088,844635605,529672921,787732362,761539876,533659816,324172557,69516659,170337379,794816136,328057110,945802450,127661646,414298415,245245040,117334366,93778789,323808313,343131364,594427347,600243986,241180301,530712664,462591648,953026473,561006665,686712086,898157835,185634554,495262504,237704337,433901787,262240589,463930726,986240684,474669695,530806005,735627055}

    Returns: 2

  30. {63003064,426206291,318225026,884783566,894763708,423355997,99480987,472900450,584758758,240333736}

    Returns: 2

  31. {541032135,182365656,291507185,802156329,943487703,937157154,390658081,664127469,129302800,314526320,704107225,637110114}

    Returns: 3

  32. {261311531,953839480,867649674,339536965,721421480,870628774,475924373,688785136,401460171,897163093,446370244,877301037,786351919,141169489,768306136,999628126,404966354,578539073,826558709,963786423,345743418,506452024,42087436,569397509,22318364,246502579,762609601,835809528,189146757,97824037,403225303,580222189,207129479,540213764,837042451,245811761,559237719}

    Returns: 2

  33. {35801769,979856073,616137981,989457786,960501790,961859524,651817083,187352121,702023864,981678068,109207154,514644802,871757149,267644227,115810633,151328504,242223621,564692080,249325276,926809966,637703061,462482274,553269148,273034990,74858070,973527014,802605629,427613437,153359056,361315072,19368411,886944234,696509242,218436778,238286495}

    Returns: 2

  34. {641869664,794709027,522409201,468153894,181884170,575300276}

    Returns: 2

  35. {454900920,154504419,108855546,523817301,132386625,683814883,85621417,149427891,837830245,70657850,665571034,438143492}

    Returns: 3

  36. {933258414,56529105,578989983,22288502,597849488,342296899,133063555}

    Returns: 3

  37. {739296794,560777247,799155712,663060844,271723867,32099545,429378271,889824807,489137054,936744749,294788361,805557429,456050515,143670380,601013422,355876386,648111224,288435519,253876210}

    Returns: 2

  38. {842723965,101325810,875019788,592939317,259676337,985478460,67532540,730488956,951763749,845007240,931573152,60486258,445414424,163127482,829995632,56869209,631314397,330281079,403974295,358614862}

    Returns: 2

  39. {222261489,838628769,972864329,557645440,28338731,378648996,728047788,416362643,329384387,93920231,977009475,735151410,425996602,895148038,550132692,335361839,916625082,799483299,958464801,996351838,525696099,446147203,846842229,96112132,181737483,862056255,697015464,501891255,345503628,477447271,780774057,710820555,588100493,391502380,363071621,240539193,419110596,887974023,155150831,269819141,364718020,200809956,17668427,529190183,295833409,529778242}

    Returns: 3

  40. {441564918,6218970,306092262,112466038,512863755,40613473,708035707,641254842,972639918,772857249,426587582,989749610,664704442,734017193,681047201,62552393,187751174,190511763,484659195,382429302,285981775,972235977,160238505,543435514,489730716,550686419,105795384,914040267,6090284,367086232,810160398,590251863,859535575,410510123,118609429,598742664,282549501,46009362,748488664,349974096,356247783,92736781,54839611,341321647,901003956,152071774}

    Returns: 3

  41. {110199869,617074370,185745299}

    Returns: 617074370

  42. {437187374,475223184,343964875,226692438,799151838,357347369,43539584,340126515,72375000,947101712,296005070,767544508,485677660,870523810,285748542,768284797,823544681,86659074,198133767,598756075,879249990,528185725,297626078,278062344,157981575,992039799,255917371,603627920,829966485,280040145,730051100,416822434,933595836}

    Returns: 2

  43. {931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240,931170240}

    Returns: 931170240

  44. {341430232,91207992,925993652,780674848,142523556,627667532,595811024,227031736,750264860,984507952,833789392,142040820,211214564,631044544,242113616,391918100,894083832,384253240,885270312,844273456,82534652,892544220,741284408,762127236,799707352,625186364,163968056,987878156,244121480,318853180,935971308,332360816,140943064,543418088,709523300,585257508,442984700,75920056,153463448,916639932,322295388,851742660,296523192,333926989,971776020,72629528,764990980,402453964,712570592,641891748}

    Returns: 4

  45. {828407440,858359964,548429056,887317844,257607644,227197348,48358100,503231204,543706408,610259384,504601244,970895968,600939080,606882304,91486192,746353440,650491464,725134368,474688956,596300992,414505168,300507872,163807336,496734336,353701264,557615408,540569652,344243984,172343024,602916104,175916692,75797960,959897680,116096428,712643876,37106300,323138928,462832832,32370632,733521124,992171040,575660288,471100532,379375472,693434980,424285316,646601256,211288728,574039872,905989448}

    Returns: 28

  46. {595605472,310411495,118890057,503027454,386561998,640832355,623316247,573315800,890180777,21855648,467714808,927410994,181068719,972648042,796333300,978280243,790054969,723985690,45572355,490746219,758301612,419433813,342695172,853155253,616920770,395404790,294884441,743946842,660988961,257669259,343321847,501286614,635363593,404428591,168158461,377271161,969993776,109982620,569710939,377073768,930804328,312850426,674910387,129901220,315874680,457353061,560389047,626048933,8062469,622700097}

    Returns: 163

  47. {366065700,998761309,75340083,671284432,292095349,729546272,12062323,943123181,559106275,308869743,352252628,762284796,347424805,300154582,416822952,209530412,210977312,570580192,216157214,881552763,331306339,326213251,716770145,408093322,646576203,755310738,246696450,890991374,334137440,454746201,568805328,717792621,4509505,792307971,843480001,478374078,894377120,291603403,228856173,677510925,600637128,214305182,383500845,996070075,64044617,579391813,834784132,638140776,835092804,36341305}

    Returns: 4823

  48. {25249987,779058569,546188257,325313786,842728802,460279279,876619150,122305583,595087932,258539734,137910228,290165133,718871209,495043792,996661447,381769737,165715035,105110411,292742996,804644104,389815356,492500577,701379207,91772378,127373614,224908301,993210731,516911694,988859956,821893106,13433401,244043092,534752626,342108368,18392663,681171099,800617528,728894143,530392684,554576957,479246431,881736257,815633301,682420745,888195556,886725684,592223989,992047662,86823045,682993150}

    Returns: 83887

  49. {74794988,478037532,190030012,558523443,364219072,517061004,947132185,308935820,917051592,15639951,582913113,741445968,59348197,972334844,975586800,420315313,556084476,11381846,950437396,736568034,542263663,779656451,926373005,944693218,180483558,143086064,517061004,395925643,734942056,39023472,995098536,212190129,666650980,113818460,827622802,938189306,438201071,365032061,661773046,426819225,419502324,878841109,725999177,537385729,304057886,791038297,259343491,931685394,747949880,172353668}

    Returns: 812989

  50. {914854312,496774867,370476172,446255389,303116868,749372257,92619043,319956694,370720051,732532431,875670952,202077912,387315998,513614693,682012953,387315998,589393910,429415563,404155824,900930691,185238086,631493475,463095215,176818173,252597390,101038956,606233736,269437216,867251039,673593040,193657999,530454519,799891735,294696955,808311648,33679652,176818173,917770517,467433447,210497825,33679652,25259739,564134171,261017303,505194780,505194780,454675302,976709908,404155824,471515128}

    Returns: 8419913

  51. {279434213,471453569,745722098,397672091,962968992,802474160,240742248,421298934,580419266,70216489,611886547,983030846,936425077,812505087,150463905,411268007,368669893,621917474,571762839,331020591,581793766,451391715,772381379,171923025,882721576,20061854,942907138,481484496,10030927,601855620,331035878,444153670,922445945,371144299,993061773,210649467,351082445,371144299,160494832,892752503,614316060,20061854,130402051,300927810,150463905,411362317,200618540,622557579,323207878,3877655}

    Returns: 10030927

  52. {830504231,830504231,830504231,830504231,830504231,830504231,830504231,830504231,830504231,491354437,830504231,830504231,830504231,830504231,830504231,830504231,830504231,788622800,378784234,572419750,830504231,724907918,830504231,830504231,244447061,830504231,830504231,830504231,223925552,830504231,830504231,830504231,830504231,830504231,225025666,830504231,830504231,830504231,830504231,830504231,338139136,949903042,830504231,280118679,830504231,830504231,830504231,67916805,248209549,830504231}

    Returns: 830504231

  53. {1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000}

    Returns: 1000000000

  54. {1000000000, 999999999, 999999999 }

    Returns: 999999999

  55. {565901664, 848852496, 754535552, 471584720, 848852496, 188633888, 377267776, 94316944, 754535552, 282950832, 848852496, 282950832, 754535552, 660218608, 754535552, 565901664, 754535552, 848852496, 377267776, 94316944, 94316944, 660218608, 565901664, 94316944, 471584720, 754535552, 660218608, 565901664, 848852496, 565901664, 282950832, 94316944, 282950832, 94316944, 660218608, 471584720, 848852496, 188633888, 754535552, 377267776, 282950832, 660218608, 282950832, 377267776, 660218608, 282950832, 377267776, 754535552, 282950832, 188633888 }

    Returns: 94316944

  56. {232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 232792560, 298629240 }

    Returns: 10920

  57. {24, 12, 37, 18, 11 }

    Returns: 6

  58. {100000000, 1000000000, 1000000000 }

    Returns: 100000000

  59. {30, 42, 70 }

    Returns: 2

  60. {1000000000, 750000000 }

    Returns: 250000000

  61. {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    Returns: 1000000000

  62. {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    Returns: 1000000000

  63. {370370367, 246913578, 246913578, 246913578 }

    Returns: 123456789

  64. {14, 21, 28 }

    Returns: 7

  65. {12347, 12347, 12347, 12347, 12347, 104729 }

    Returns: 12347

  66. {1000000000, 44444444, 4444444 }

    Returns: 4

  67. {210, 462, 770 }

    Returns: 14

  68. {200002, 300003, 500005 }

    Returns: 100001

  69. {220000034, 330000051, 550000085 }

    Returns: 110000017

  70. {180, 300, 450 }

    Returns: 30

  71. {45, 12, 23, 45, 12, 12, 2, 3, 4, 17, 33, 56, 81, 8, 9, 27, 56, 45, 12, 23, 45, 12, 12, 2, 3, 4, 2, 56, 2, 12, 2, 3, 4, 2, 56, 45, 12, 23, 45, 12, 12, 2, 3, 4, 17, 33, 56 }

    Returns: 2

  72. {990001699, 990001699, 990001699, 990001699, 990001699, 990001699, 990001699, 990001699, 990001699, 990001699, 990001699, 990001643, 990001643, 990001643, 990001643, 990001643, 990001643, 990001643, 990001643 }

    Returns: 990001699

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: