Statistics

Problem Statement for "DistancesBetweenNumbers"

Problem Statement

Given two non-negative integers X and Y, their distance is defined as the number of base-10 digits in which they differ.

For example:

  • distance(47, 47) = 0
  • distance(42, 47) = distance(47, 42) = 1: these numbers have the same tens digit and different ones digits
  • distance(24, 42) = 2: we are comparing each position separately, not just the sets of digits
  • distance(1234, 37) = 3: if one number is shorter, the missing digits are zero, so distance(1234, 37) = distance(1234, 0037)

You are given a long sequence A that consists of N non-negative integers.

For each pair of indices i and j (0 <= i < j < N), Lucy calculated the distance between A[i] and A[j]. Then, Lucy computed the sum of all those distances.

Return the final value obtained by Lucy.


In order to keep the input size small, you are only given a prefix of A, the rest is generated pseudorandomly. Please use the pseudocode or code given below to generate A. 


Pseudocode:

A = an empty array of length N
L = length(Aprefix)

for i = 0 to L-1:
    A[i] = Aprefix[i]

for i = L to N-1:
    A[i] = (A[i-1] * 1103515245 + 12345) modulo 2^31

-------------------------------------------------------------------------------------

Java:

int[] A = new int[N];
int L = Aprefix.length;
for (int i=0; i<L; ++i) A[i] = Aprefix[i];
for (int i=L; i<N; ++i) A[i] = (int)((A[i-1] * 1103515245L + 12345L) % (1L << 31));

-------------------------------------------------------------------------------------

C++:

vector<int> A(N);
int L = Aprefix.size();
for (int i=0; i<L; ++i) A[i] = Aprefix[i];
for (int i=L; i<N; ++i) A[i] = (A[i-1] * 1103515245LL + 12345LL) % (1LL << 31);

Definition

Class:
DistancesBetweenNumbers
Method:
count
Parameters:
int, int[]
Returns:
long
Method signature:
long count(int N, int[] Aprefix)
(be sure your method is public)

Notes

  • The reference solution does not depend on A being pseudorandom. It would correctly solve any input of the given size.

Constraints

  • N will be between 2 and 100,000, inclusive.
  • Aprefix will contain between 1 and min(100, N) elements, inclusive.
  • Each element of Aprefix will be between 0 and 2^31 - 1, inclusive.

Examples

  1. 4

    {47, 47, 47, 47}

    Returns: 0

    All numbers are the same, all pairwise distances are zero.

  2. 4

    {47, 47, 42, 47}

    Returns: 3

    Three pairs have distance 0, three pairs have distance 1.

  3. 4

    {1, 10, 100, 1000}

    Returns: 12

    Each pair of elements of this sequence has distance 2.

  4. 10

    {1234567, 1234890}

    Returns: 389

    The full array A looks as follows: A = { 1234567, 1234890, 1979817275, 1396317272, 1752240561, 191800982, 48419351, 727754244, 1439963117, 1491506722 }. If you are writing your own code to generate A, please watch out for integer overflows.

  5. 100000

    {1234567, 1234890}

    Returns: 43301479228

  6. 2

    {0, 1999999999}

    Returns: 10

  7. 91529

    {1948501517, 1475191316, 1105644294, 1660249968, 1685411311, 175701600, 1797583853, 101618320, 440044526, 2690834, 1133040875, 2068253425, 39237771, 1355395163, 1836955051, 988044144, 1021093428, 1542245923, 1899324723, 1039591800, 142868263, 1607036031, 1518067261, 1468508435, 841741944, 1024861607, 151521850, 539016619, 1434210114, 420679459, 1558380042, 1647457924, 1085916001, 417035555, 974776318, 1438208187, 938681896, 2023059399, 473072173, 1789542187, 1516333974, 1229727803, 1026423979, 1123519141, 1533059612, 172270288, 2078532398, 1340917328, 1698564564, 1117738417, 948917258, 489349967, 889428824, 1631517495, 2084771948, 1087222470, 640818900, 1906477425, 65241470, 731414135, 355519765, 320425005, 1141387247, 2046595582, 1870943262, 1570148161, 142514072, 1138224035, 2026408624, 1352884873, 95491659}

    Returns: 36275063373

  8. 98904

    {1485905588}

    Returns: 42347366322

  9. 94143

    {2017745344}

    Returns: 38378644408

  10. 86510

    {586949650}

    Returns: 32400818708

  11. 99967

    {1146177193, 1906624755, 1940892, 525600088, 1778417307, 288469429, 1585910533, 88998632, 1134935596, 179122525, 603178428, 778158833, 2108757054, 863925910}

    Returns: 43266478472

  12. 99972

    {317163642}

    Returns: 43274835528

  13. 85738

    {200513682, 1007175254, 263002937, 1626629292, 528916607, 95408474, 380485713, 1300208178, 231464469, 1321413367, 1027003835, 649419618, 1173215853, 346617440, 2109919775, 1471952835, 224121999, 492182829, 1775873863, 1793775065, 1519313155, 1300568894, 2101334812, 599801112, 272886230, 502796335, 1981116652, 1948911863, 76784397, 1866519440, 284290351, 1235357188, 2105402687, 490178290, 1052781061, 1512640368, 1422105126, 716905769, 1986684762, 97040700, 421704849, 1973409169, 1977954749, 1188790660, 102151484, 812974551, 1232890504, 175604815, 1130699910, 2073107849, 1647993519, 294059352, 468300517, 2050067571, 1554617535, 1338728498, 1769937956, 879909240, 392755518, 441009962, 1309953612, 1739803388, 1429174780, 1546714289, 467288229, 400206914, 1830200175, 1548461477, 215800586, 1502298833, 242563618, 1683014802, 1150680127, 1092362325, 904566712, 1244362723, 898538742, 1997165977, 1286402574, 1912313258, 1891726748, 1363446327}

    Returns: 31819028640

  14. 81794

    {118213281}

    Returns: 28961301321

  15. 99966

    {1106908031, 1262555971, 440265580, 1301697396, 531924256, 729061624, 1817147801, 1445927722, 2136870386, 1829642579, 1007203776, 1130011384, 1344280466, 99073865, 1629169908, 1983527925, 770947798, 1619264208, 183808378, 780112910, 779372551, 334718070, 2082862941, 1765314531, 258860437, 963875836, 1983085133, 755530463, 1708937855, 19173630, 597387838, 312614420, 1671227102, 3240676, 1650855086, 2144595767, 1954741865, 1602883242, 526066028, 1720060055, 438548027, 369525243, 1805133931, 1769321186, 447805518, 750893228, 2141323295, 2043547395, 1886553272, 402545275, 1698673775, 1406159933, 1857911432, 844576579, 1358865986, 1705603794, 320361304, 569139255, 2094311409, 1430484067, 450297558, 1084462447, 2085040342, 398184188, 1533974457, 127702674, 1694565277, 349278773, 963098471, 905302894, 1106723769, 1316725677, 488502684, 268214787, 1232241399, 761358727, 2097118814, 1036425125, 1736740490}

    Returns: 43264587005

  16. 95534

    {1010397418, 1606747649, 458337118, 1451054712, 276132858, 674631869, 454791749, 1026431827, 786955937, 343476289, 608660236, 722198280, 710429624, 331716879, 398097787, 540951194, 1691293679, 1495990781, 523104350, 1780980161, 1266477948, 942936922, 1489995248, 386977452, 1349285998, 437721575, 153700843, 866820893, 581846500, 1418230283, 390384469, 1371506773, 1842399888, 1512485082, 1827507600, 1886014563, 1872780971, 1774309568, 2107368689, 97389444, 836719993, 1402024454, 210761941, 1840506704, 434271713, 1885893272, 532716181, 413576938, 1437375278, 1877567921, 253456038, 1433250621, 805196287, 1755671568, 2013497170, 2040058862, 513342065, 985434944, 853014838, 113301998, 2119888712, 1396777957, 609918436, 703601087, 1241566301, 311775786, 201701043, 1282909328, 189901465, 27067550, 1100292491, 1480332796, 825599650, 923670932, 1586454074, 1592078892, 573850115, 869290136}

    Returns: 39516184724

  17. 94660

    {1286708360, 1811514463, 475863717, 1815175106, 1796636626, 1492517263, 2137947429, 1103050310, 194969798, 2107943633, 986661569, 1162101126, 1741737939, 251147389, 103084142, 1688417412, 819222983, 1792312856, 1575552978, 381028443, 1482412642, 1456006488, 1894985334, 291109345, 281126873, 2032222347, 1145921960, 276409821, 696908412, 879293777, 976808686, 1812898707, 2029977897, 848052615, 1274375336, 25507263, 490428354, 50952394, 1078492894, 914822941, 1600605750, 2022974035, 920232792, 1427747666, 1719980576, 164647511, 1781210239, 1397798546, 1480581755, 32134090, 469387628, 88290928, 1335612918, 208686395, 939197325, 14434277, 149953646, 211560378, 1646888126, 1993026474, 820206654, 385572705, 1190803699, 1698357684, 1494062160, 162392144, 280319007, 1305849986, 1336545990, 223473455, 1897296966, 1990334092, 1747055184, 1428569044, 386253728, 1087525279, 1805700976, 1604168383}

    Returns: 38793187747

  18. 99948

    {1269988112}

    Returns: 43253089003

  19. 80976

    {541089867}

    Returns: 28392257681

  20. 98387

    {32711815}

    Returns: 41913708679

  21. 99953

    {547953963, 661377199, 1613667693, 1976025263, 1128032479, 633779308, 322479051, 170172939, 1037122419, 550903416, 302814616, 75299242, 588301709, 526733968, 546676137, 1254627237, 1796659924, 2096236884, 100759776, 718999374, 626459750, 993117026, 503727537, 650746088, 1224666764, 2080174925, 2104757794, 1978364326, 1328065760, 1759733058, 1931485369, 788047505, 54946856, 1838018123, 2093174743, 2102970538, 1752511678, 1475246228, 1610355287, 1296605483, 1319841797, 1694248403, 1616927188, 152715243, 1154162604, 608350938, 2007325964, 1685263483, 435262418, 462328888, 145801974, 1579559189, 1461150219, 633475780, 4707179, 1118338495, 1508573983, 687165806, 170833432, 1770891939, 2065566509, 1389334378, 633585412, 1141028568, 1100177516, 1420626755, 1755553326, 479048571, 882615665, 758499011, 990054825, 1211853205, 1055259076, 1978518580, 1464275582}

    Returns: 43255840324

  22. 99914

    {763289261}

    Returns: 43225024443

  23. 98501

    {884531409, 1070188718, 175238726, 1569761181, 1633727531, 738465732, 2105433006, 731368979, 830231936, 1729290520, 230505136, 2013949324, 1403536925, 320615195, 1111797574, 409042122, 594880192, 894454129, 1175507290, 1672863266, 476696165, 1097630447, 1536326541, 513778974, 1614232738, 1598783037, 966306144, 1249569344, 1077773616, 1377899115, 164618037, 891024322, 1272289836, 1915757346, 1396738263, 490564103, 628167979, 786294352, 1118550262, 1473378479, 1176778127, 406616854, 1265146490, 893358536, 162634232, 1162002437, 932258961, 851928981, 2114618606, 2126875059, 332609510, 1639593703, 99993258, 643825690, 457101440, 1800951242, 1292774826, 946299483, 1778314963, 815144405, 370040610, 920046261, 959964665, 383441804, 1800803545, 1327370580, 1354475536, 1605916986, 510006733, 391153318, 1349762487, 1952515208, 909922665, 504504633, 372122540, 1463139209, 2079845253, 940300094, 254969676, 1369957303, 1324603655, 1627755384}

    Returns: 42004632358

  24. 88677

    {1099769852}

    Returns: 34046189695

  25. 94982

    {1368005969, 1874417835, 1068579840, 1411322655, 900783919, 762222613, 813484984, 1027681558, 178274192, 126190217, 1118999809, 1265713409, 852796077, 1474467706, 1446214333, 746521710, 1407805355, 1600737448, 793729814, 675143724, 2119271741, 324413221, 151130011, 1678817963, 1993797869, 1932976813, 1263893249, 403484092, 2114487398, 1161698913, 1433593740, 1212353529, 931976390, 1836036144, 324171803, 1097067930, 1643056859}

    Returns: 39059294087

  26. 99937

    {1039615084}

    Returns: 43244493961

  27. 99929

    {930267020, 2034373739, 105888022, 1527085586, 39643438}

    Returns: 43240482646

  28. 99970

    {1013905843, 1950366309, 1951000664, 227225975, 355257045, 558904637, 1728285218, 1903699727, 803987253, 1064632107, 197167745, 1725399245, 1941996298, 428277337, 113798054, 1925648166, 2085166864, 692558964, 680887895, 1023844058, 1183739994, 1367970987, 831775688, 2117736493, 1180000954, 1974736149, 1096858599, 1447448202, 500483254, 948566712, 1091928841, 970637124, 140387836, 592262195, 1050286011, 1923717191, 364089447, 1392073882, 927974519, 1389486286, 404082448, 1117747418, 674632493, 1193956246, 1549814366, 599247253, 707070557, 338159775, 791381517, 239635179, 771189307, 440977433, 1228772217, 180261467, 1376812842, 796590148, 371200567, 1931177944, 1184530319, 423637403, 1281809169, 839049594, 2125728832, 618455383, 585226110, 1044945908, 1032825637, 1342102521, 1103142649, 1951484737, 112917720, 1327415188, 809585589, 109238195, 1850157600, 748525937, 1154103055, 2091280058, 810442206, 1926371173, 55204629, 1587141872, 1062406038, 1724136063, 769082629, 757526682, 768838461, 215547127, 924006094, 1353578174, 1729117449, 1288002828, 1149474177, 398727950, 1300383302, 988172213, 186729023}

    Returns: 43273231184

  29. 99939

    {1270390786}

    Returns: 43249773367

  30. 94957

    {1300349233}

    Returns: 39040138855

  31. 99937

    {1317151207}

    Returns: 43239720089

  32. 81243

    {1825303454, 628633173, 1625351247, 1651736160, 962903142, 1776223674, 1911113707, 783406726, 1084500388, 1720674880, 1375771134, 1439575192, 535331009, 1623874294, 1870066971, 603678092, 385591403, 1862495166, 1072105422, 1012235679, 15182937, 1103924062, 109021556, 1447671307, 1703477034, 1300856391, 850468948, 1089189562, 290646314, 217439203, 1043269191, 749984089, 1514336675, 1487188586, 359040361, 2143973154, 1120538438, 1205196993, 1580579742, 877770776, 205944372, 1118603551, 2092700209, 999784310, 469698387, 1312811137, 792770046, 1704187837, 1207634144, 865947664, 1203725907, 689103832, 693409053, 1374832992, 658136679, 1194980152, 2070518832, 423967412, 1227048125, 1122725448, 648575493, 1679514370, 942085340, 952639852, 764995245, 370362191, 1245826810, 625973473, 1997726696, 1267874231, 135606474, 457796175, 948638990}

    Returns: 28575447851

  33. 86793

    {2144880760}

    Returns: 32616419493

  34. 99991

    {1440610433, 1547798334}

    Returns: 43286241639

  35. 93761

    {1415570502}

    Returns: 38060278548

  36. 88521

    {1056330759}

    Returns: 33929512712

  37. 100000

    {114514 }

    Returns: 43296320898

  38. 100000

    {1234567, 1234890 }

    Returns: 43301479228

  39. 100000

    {1, 2, 7, 13 }

    Returns: 43293186128

  40. 100000

    {1234244433, 1234244432 }

    Returns: 43299083786

  41. 100000

    {1, 2, 3, 4, 5 }

    Returns: 43301501035

  42. 100000

    {54, 120, 97, 17 }

    Returns: 43295382994

  43. 99821

    {1255596826, 1638938402, 286348889 }

    Returns: 43138685284

  44. 50000

    {1234567, 12345890 }

    Returns: 10825243684

  45. 100000

    {1, 10, 100, 1000 }

    Returns: 43296972577

  46. 100000

    {100000 }

    Returns: 43295635161

  47. 2

    {2345, 1 }

    Returns: 4

  48. 100000

    {47, 47, 47, 7, 7 }

    Returns: 43298388570

  49. 100000

    {1000001, 1000002, 1000003, 1000004, 1000005, 1000006, 1000007, 1000008, 1000009, 1000010, 1000011, 1000012, 1000013, 1000014, 1000015, 1000016, 1000017, 1000018, 1000019, 1000020, 1000021, 1000022, 1000023, 1000024, 1000025, 1000026, 1000027, 1000028, 1000029, 1000030, 1000031, 1000032, 1000033, 1000034, 1000035, 1000036, 1000037, 1000038, 1000039, 1000040, 1000041, 1000042, 1000043, 1000044, 1000045, 1000046, 1000047, 1000048, 1000049, 1000050, 1000051, 1000052, 1000053, 1000054, 1000055, 1000056, 1000057, 1000058, 1000059, 1000060, 1000061, 1000062, 1000063, 1000064, 1000065, 1000066, 1000067, 1000068, 1000069, 1000070, 1000071, 1000072, 1000073, 1000074, 1000075, 1000076, 1000077, 1000078, 1000079, 1000080, 1000081, 1000082, 1000083, 1000084, 1000085, 1000086, 1000087, 1000088, 1000089, 1000090, 1000091, 1000092, 1000093, 1000094, 1000095, 1000096, 1000097, 1000098, 1000099, 1000100 }

    Returns: 43300621384

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: