Statistics

Problem Statement for "PerfectParty"

Problem Statement

You are hosting a party.

Each of your friends is willing to bring you some number of candies if you invite them to the party. These numbers of candies are given in the int[] candies.

You can invite an arbitrary subset of these friends to your party. Once all the invited guests arrive, you are going to collect all the candies they brought and then divide them among everyone at the party (including yourself). The party is perfect if it's possible to divide the candies evenly, i.e., with no remainder.

Return the number of ways in which you can have a perfect party. (Two ways differ iff the set of participants differs.)

Definition

Class:
PerfectParty
Method:
invite
Parameters:
int[]
Returns:
long
Method signature:
long invite(int[] candies)
(be sure your method is public)

Constraints

  • candies will have between 1 and 50 elements, inclusive.
  • Each element of candies will be between 0 and 2,500, inclusive.

Examples

  1. {0, 0, 0, 0}

    Returns: 16

    Nobody is willing to bring any candies. On one hand that means that everyone at the party will be hungry, but on the other hand you can invite any subset of your friends (including none of them or all of them) and the party will be perfect: you can divide 0 candies evenly among any number of participants.

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

    Returns: 1

    Regardless of how many friends you invite, you'll always have one fewer candies than participants and so the party will never be perfect - except for one case. If you don't invite anyone, you will be alone with no candies. That is clearly a perfect party. (In real life opinions may differ, but in our problem a perfect party has an exact definition.)

  3. {0, 0, 0, 0, 125}

    Returns: 20

    Let's call the last friend (the one willing to bring 125 candies) Peter. There are 2^4 = 16 ways to have a perfect party without Peter. If we do invite Peter, the party will be perfect if and only if the total number of participants is exactly 5. There are four distinct ways to do this: you need to choose one of the four other friends who won't get invited.

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

    Returns: 31

  5. {840, 840, 840, 840, 840, 840, 840, 840, 840, 840, 840, 840, 840, 840, 840, 840, 840, 840, 840, 840, 840, 840, 840, 840, 840, 840, 840, 840, 840, 840, 840, 840, 840, 840, 840, 840, 840, 840, 840, 840, 840, 840, 840, 840, 840, 840, 840, 840, 840, 840}

    Returns: 367245340781671

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

    Returns: 38254020911070

  7. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

    Returns: 1125899906842624

  8. {2455, 2470, 2458, 2473, 2443, 2432, 2465, 2449, 2450, 2478, 2405, 2453, 2484, 2403, 2413, 2400, 2433, 2461, 2492, 2469, 2401, 2440, 2472, 2454, 2429, 2430, 2466, 2465, 2445, 2456, 2430, 2404, 2471, 2447, 2491, 2488, 2445, 2476, 2443, 2471, 2473, 2497, 2425, 2430, 2500, 2493, 2404, 2416, 2442}

    Returns: 22517998117443

  9. {2368, 1571, 2082, 2212, 1035, 397, 929, 1371, 895, 1929, 451, 1706, 2476, 1446, 1172, 978, 2274, 1071, 1462, 2181, 2315, 164, 1982, 1278, 2304, 1619, 1065, 2127, 904, 2483, 466, 848, 1555, 1988, 1036, 2472, 2285, 611, 1818, 62, 697, 2240, 339, 305, 1088, 2094, 2239}

    Returns: 5864061984249

  10. {1497, 135, 2489, 1085, 2492, 2117, 1932, 1290, 91, 2363, 995, 865, 1417, 1767, 753, 723, 1924, 813, 523, 403, 559, 2333, 1409, 2160, 1607, 442, 1093, 1818, 1, 501, 1696, 275, 1512, 84, 1082, 170, 575, 742, 2095, 2011, 823, 2026, 2163, 1857, 2308, 2323, 40, 302, 717, 616}

    Returns: 44152937445501

  11. {2479, 2430, 2491, 2407, 2448, 2415, 2402, 2411, 2438, 2406, 2470, 2439, 2430, 2478, 2493, 2468, 2419, 2470, 2474, 2497, 2434, 2479, 2473, 2410, 2472, 2462, 2443, 2471, 2406, 2414, 2452, 2453, 2445, 2438, 2472, 2497, 2462, 2476, 2417, 2408, 2465, 2414, 2459, 2483, 2500, 2458, 2402, 2455, 2472}

    Returns: 22517998036389

  12. {2007, 2057, 467, 1004, 1442, 1356, 683, 1894, 92, 2407, 402, 1881, 1886, 1133, 2231, 97, 2294, 775, 1175, 167, 1078, 2221, 1977, 1571, 280, 446, 2133, 2416, 2453, 1955, 2200, 1482, 2369, 1276, 1687, 839, 374, 420, 2098, 1249, 1659, 1362, 2207, 1475, 445, 381, 1745}

    Returns: 5864062034923

  13. {2444, 2474, 2407, 2450, 2481, 2434, 2432, 2426, 2437, 2426, 2459, 2484, 2438, 2456, 2499, 2456, 2440, 2486, 2407, 2419, 2474, 2461, 2400, 2403, 2454, 2458, 2466, 2456, 2478, 2432, 2437, 2413, 2438, 2415, 2421, 2454, 2443, 2463, 2454, 2430, 2464, 2472, 2465, 2433, 2440, 2471, 2402, 2477, 2486}

    Returns: 22517998373641

  14. {2286, 735, 1544, 175, 743, 743, 319, 1986, 1683, 246, 919, 1891, 720, 2449, 1629, 18, 569, 298, 2294, 1593, 3, 1574, 2045, 1864, 1528, 501, 2094, 1640, 418, 352, 1721, 1687, 2254, 427, 716, 2042, 1948, 1799, 2442, 383, 1619, 2148, 2071, 1341, 1771, 805, 1295, 1626, 305, 542}

    Returns: 44152937635610

  15. {429, 1034, 1988, 379, 1462, 121, 1616, 333, 2463, 918, 2112, 863, 2079, 1055, 1255, 2048, 2480, 465, 2302, 255, 1175, 726, 1999, 988, 1656, 1941, 28, 2412, 1636, 2494, 963, 2270, 1532, 437, 1383, 263, 643, 2416, 433, 978, 750, 327, 580, 2109, 688, 677, 316, 379, 515, 2412}

    Returns: 44152937457343

  16. {498, 1698, 1207, 2249, 899, 1420, 369, 1286, 417, 146, 826, 2290, 554, 1352, 372, 1307, 1757, 2073, 2236, 2345, 1442, 2135, 2127, 1742, 1798, 1786, 1692, 2009, 92, 797, 1337, 200, 2456, 1755, 414, 1798, 2387, 508, 394, 1370, 1790, 241, 1366, 767, 1674, 1920, 2121, 1945, 2115, 489}

    Returns: 44152937539675

  17. {108, 2211, 2021, 1332, 581, 671, 1184, 297, 192, 2476, 1223, 181, 25, 1049, 1411, 787, 2275, 880, 1512, 1518, 547, 829, 1832, 141, 1235, 2468, 1227, 1727, 453, 1731, 1713, 1423, 2038, 1051, 185, 2314, 2010, 940, 1108, 1661, 239, 98, 1610, 781, 1709, 1502, 2130, 363}

    Returns: 11488774667906

  18. {1807, 277, 268, 1938, 1092, 263, 664, 838, 931, 1728, 1935, 808, 1215, 24, 467, 2476, 2311, 48, 1028, 2184, 872, 2180, 1526, 1929, 877, 1361, 1640, 157, 2402, 1698, 1333, 2202, 1411, 30, 447, 84, 1273, 199, 2494, 895, 2147, 13, 143, 2271, 2409, 201, 1570, 1900, 782}

    Returns: 22517998096175

  19. {1619, 2089, 1424, 154, 267, 1245, 2463, 1274, 213, 2499, 1809, 1898, 1666, 1362, 368, 1037, 1722, 1529, 402, 1545, 1546, 722, 1211, 122, 124, 2355, 2362, 783, 516, 2298, 912, 353, 31, 1732, 1751, 1705, 1732, 2368, 522, 630, 1538, 2207, 1884, 1075, 604, 307, 162}

    Returns: 5864061944268

  20. {288, 71, 561, 502, 2123, 521, 1196, 2334, 2468, 1713, 2242, 1999, 2379, 96, 685, 2448, 2219, 2368, 597, 947, 480, 620, 1167, 1983, 2007, 1886, 2478, 1266, 1678, 1842, 2480, 751, 52, 1752, 1996, 2005, 1671, 1406, 1535, 2276, 1236, 1258, 1615, 1542, 145, 2155, 1100, 580}

    Returns: 11488774420767

  21. {415, 440, 2428, 139, 1506, 1393, 2341, 604, 4, 1066, 1438, 655, 162, 1688, 1969, 1324, 604, 1088, 1049, 1354, 1674, 456, 841, 723, 944, 1155, 1006, 1886, 2161, 1396, 639, 2162, 1478, 456, 599, 727, 2312, 931, 2211, 2340, 2160, 1312, 2219, 843, 1020, 167, 1497, 1558, 704, 2007}

    Returns: 44152937616081

  22. {1649, 219, 1920, 1338, 2246, 2209, 305, 1060, 390, 567, 2110, 2373, 853, 1121, 2446, 1595, 454, 1046, 2264, 1465, 489, 1539, 1524, 2183, 921, 1191, 1027, 2492, 1314, 2333, 156, 849, 1213, 1827, 1332, 467, 599, 2424, 749, 1066, 1405, 1122, 387, 1206, 851, 155, 1108, 889}

    Returns: 11488774588821

  23. {2028, 317, 1563, 95, 2428, 614, 435, 1717, 1232, 902, 1695, 777, 352, 877, 915, 2244, 365, 2275, 1717, 1265, 1291, 1531, 486, 373, 1287, 1862, 867, 481, 354, 2194, 1395, 2321, 1983, 896, 243, 1306, 1263, 1552, 1084, 2424, 243, 310, 1048, 1872, 2064, 902, 2100, 2093}

    Returns: 11488792482096

  24. {1304, 1787, 2114, 1019, 2498, 1345, 2336, 859, 2341, 726, 775, 980, 170, 120, 2490, 2087, 2480, 1067, 2494, 1207, 813, 1406, 2424, 2476, 2290, 1379, 2065, 711, 1342, 1526, 756, 643, 2021, 309, 144, 1601, 1901, 1843, 1205, 384, 2016, 1107, 1367, 1156, 888, 1750, 309, 1046, 1566, 1325}

    Returns: 44152937427599

  25. {659, 991, 747, 1485, 943, 1265, 148, 887, 2353, 1940, 100, 1456, 37, 1164, 1121, 2264, 1703, 2169, 966, 1860, 1860, 216, 338, 533, 1648, 1815, 766, 1015, 188, 1645, 1852, 2179, 2145, 408, 2285, 108, 2230, 1836, 2213, 1988, 2412, 660, 649, 976, 1128, 1304, 793, 2282, 2019, 2083}

    Returns: 44152937567244

  26. {1046, 1380, 2150, 477, 904, 1041, 925, 133, 564, 1001, 1834, 347, 1327, 2243, 884, 1325, 385, 1065, 2123, 643, 1138, 1478, 571, 674, 322, 754, 228, 2085, 735, 2473, 2275, 420, 1171, 171, 1313, 759, 354, 1841, 1129, 404, 1222, 800, 2427, 2027, 589, 558, 996, 2205, 984}

    Returns: 22517997851434

  27. {1861, 107, 1265, 772, 104, 1764, 713, 1100, 1994, 772, 1837, 52, 1513, 1013, 1644, 2077, 733, 722, 733, 2469, 205, 881, 1290, 2498, 1649, 1228, 1096, 380, 1240, 942, 178, 2296, 1930, 1253, 966, 1211, 1869, 733, 724, 2270, 1240, 1884, 1184, 1193, 212, 1256, 155, 280, 2500}

    Returns: 22517998112906

  28. {599, 1550, 1575, 2223, 918, 2171, 2294, 1693, 1822, 2210, 747, 1034, 1640, 1312, 1372, 510, 1548, 1783, 575, 367, 1776, 1022, 965, 14, 1052, 2220, 103, 1380, 1624, 2176, 1240, 811, 1038, 277, 207, 994, 715, 2500, 1444, 1418, 342, 2044, 1068, 1149, 2447, 1507, 837, 196, 1066, 1995}

    Returns: 44152940046385

  29. {2467, 2439, 2423, 2450, 2435, 2494, 2475, 2491, 2425, 2467, 2435, 2497, 2420, 2420, 2440, 2419, 2435, 2461, 2412, 2436, 2488, 2433, 2419, 2450, 2486, 2428, 2428, 2496, 2422, 2411, 2437, 2466, 2418, 2459, 2499, 2437, 2404, 2413, 2487, 2471, 2428, 2426, 2413, 2425, 2463, 2449, 2438, 2491}

    Returns: 11488774690660

  30. {2442, 2446, 2453, 2412, 2411, 2442, 2433, 2468, 2429, 2474, 2492, 2488, 2417, 2431, 2486, 2463, 2470, 2489, 2480, 2425, 2498, 2404, 2494, 2421, 2403, 2472, 2440, 2429, 2487, 2446, 2429, 2431, 2462, 2447, 2425, 2454, 2423, 2459, 2476, 2478, 2428, 2404, 2498, 2452, 2459, 2429, 2454, 2498, 2402}

    Returns: 22517998181731

  31. {2462, 2424, 2450, 2424, 2492, 2400, 2430, 2463, 2466, 2401, 2470, 2437, 2461, 2440, 2439, 2478, 2489, 2485, 2466, 2490, 2488, 2495, 2480, 2464, 2448, 2479, 2428, 2486, 2406, 2427, 2427, 2497, 2462, 2475, 2456, 2463, 2451, 2469, 2451, 2417, 2453, 2445, 2401, 2489, 2467, 2443, 2469, 2495, 2413, 2497}

    Returns: 44152937618244

  32. {1073, 626, 216, 881, 216, 2306, 1072, 1059, 721, 1533, 1530, 946, 2336, 2370, 2268, 545, 965, 434, 550, 1472, 210, 594, 715, 1597, 1108, 2139, 257, 2180, 630, 986, 1319, 1861, 2123, 1075, 385, 1436, 1050, 38, 2265, 1143, 2185, 1096, 1904, 2148, 1912, 616, 1488, 552, 851}

    Returns: 22517998844284

  33. {2406, 2449, 2463, 2426, 2484, 2486, 2467, 2486, 2473, 2420, 2480, 2489, 2447, 2407, 2471, 2495, 2423, 2470, 2430, 2461, 2499, 2461, 2454, 2407, 2489, 2463, 2488, 2489, 2488, 2499, 2429, 2465, 2473, 2441, 2465, 2428, 2449, 2494, 2458, 2417, 2481, 2421, 2421, 2425, 2442, 2400, 2475}

    Returns: 5864062180340

  34. {670, 1194, 2136, 1779, 1934, 2270, 1786, 87, 683, 2385, 1753, 1633, 132, 2283, 202, 248, 2481, 417, 850, 1974, 771, 2258, 131, 2185, 492, 67, 1358, 1059, 1964, 1139, 403, 479, 1469, 1979, 37, 1140, 2340, 1884, 1826, 760, 504, 1059, 1510, 1908, 220, 2015, 134, 1744}

    Returns: 11488774511448

  35. {1518, 803, 943, 2397, 586, 843, 2029, 2105, 436, 1190, 2481, 2213, 407, 2007, 795, 154, 615, 2073, 1058, 606, 1148, 1527, 601, 1362, 2178, 1516, 520, 587, 1754, 1665, 2337, 1300, 736, 2477, 1536, 77, 428, 1738, 683, 266, 412, 531, 422, 313, 892, 117, 741}

    Returns: 5864062659118

  36. {2408, 2471, 2461, 2495, 2402, 2415, 2422, 2442, 2485, 2493, 2416, 2489, 2416, 2435, 2428, 2417, 2406, 2449, 2420, 2453, 2470, 2403, 2409, 2431, 2486, 2489, 2464, 2454, 2465, 2480, 2476, 2408, 2499, 2445, 2431, 2445, 2434, 2424, 2405, 2439, 2405, 2422, 2407, 2467, 2439, 2439, 2455, 2491, 2443, 2406}

    Returns: 44152936973616

  37. {749, 2131, 669, 780, 98, 2181, 1907, 942, 1063, 1710, 1966, 21, 213, 1397, 1667, 380, 310, 1400, 854, 1063, 1400, 494, 622, 2439, 1845, 1550, 2381, 1376, 828, 1055, 1123, 1874, 1023, 1975, 726, 2352, 1676, 1591, 812, 144, 1325, 182, 963, 276, 477, 1121, 980, 1974, 1807}

    Returns: 22517997734326

  38. {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 28, 29, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49 }

    Returns: 44152937520943

  39. {2500, 2499, 2498, 2497, 2496, 2495, 2494, 2493, 2492, 2491, 2490, 2489, 2488, 2487, 2486, 2485, 2484, 2483, 2482, 2481, 2480, 2479, 2478, 2477, 2476, 2475, 2474, 2473, 2472, 2471, 2470, 2469, 2468, 2467, 2466, 2465, 2464, 2463, 2462, 2461, 2460, 2459, 2458, 2457, 2456, 2455, 2454, 2453, 2452, 2451 }

    Returns: 44152937520670

  40. {950, 950, 950, 950, 950, 950, 950, 950, 950, 950, 950, 950, 950, 950, 950, 950, 950, 950, 950, 950, 950, 950, 950, 950, 950, 950, 950, 950, 950, 950, 950, 950, 950, 950, 950, 950, 950, 950, 950, 950, 950, 950, 950, 950, 950, 950, 950, 950, 950, 950 }

    Returns: 139959555102776

  41. {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 2339, 2318, 2295, 2270, 2243, 2214, 2183, 2150, 2115, 2078, 2039, 1998, 1955, 1910, 1863, 1814, 1763, 1710, 1655, 1598, 1539, 1478, 1415, 1350, 1283, 1214, 1143, 1070, 995, 918, 839, 758, 675, 590, 503, 414, 323, 230, 135, 38 }

    Returns: 44152721574738

  42. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    Returns: 1

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

    Returns: 562949953421313

  44. {2500, 2500, 0, 0, 2500, 2500, 0, 0, 249, 2394, 2500, 2500, 0, 0, 2500, 2500, 0, 0, 249, 2394, 2500, 2500, 0, 0, 2500, 2500, 0, 0, 249, 2394, 2500, 2500, 0, 0, 2500, 2500, 0, 0, 249, 2394, 2500, 2500, 0, 0, 2500, 2500, 0, 0, 249, 2394 }

    Returns: 46719342637269

  45. {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

    Returns: 562949953421312

  46. {0, 0, 0, 0 }

    Returns: 16

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: