- #1
SlurrerOfSpeech
- 141
- 11
I'm trying to solve https://www.hackerrank.com/challenges/equal which is how to make an array's N elements equal through operations restricted to (1) adding 1 to N-1 elements, (2) adding 2 to N-1 elements or (3) Adding 5 to N-1 elements.
I started out by writing some test cases that might be weak:
Those all pass with the algorithm I wrote.
Then I added some large test cases from the problem:
Those all fail and I they're too big to debug and figure out why.
I've detailed my algorithm below.
Can someone help me figure out where I'm going wrong with these larger test cases?
They are all off by "a little", e.g. Expected=16931 and Actual=16292.
I started out by writing some test cases that might be weak:
Code:
[TestMethod]
public void EmptyInput()
{
int[] chocstart = { };
Assert.AreEqual(0, Equal.OperationsToEven(chocstart));
}
[TestMethod]
public void SingleElement()
{
int[] chocstart = { 1 };
Assert.AreEqual(0, Equal.OperationsToEven(chocstart));
}
[TestMethod]
public void TwoOfSameElement()
{
int[] chocstart = { 1, 1 };
Assert.AreEqual(0, Equal.OperationsToEven(chocstart));
}
[TestMethod]
public void ManyOfSameElement()
{
int[] chocstart = Enumerable.Repeat(2384, 50).ToArray();
Assert.AreEqual(0, Equal.OperationsToEven(chocstart));
}
[TestMethod]
public void OneTwo()
{
int[] chocstart = { 1, 2 };
Assert.AreEqual(1, Equal.OperationsToEven(chocstart));
}
[TestMethod]
public void OneThree()
{
int[] chocstart = { 1, 3 };
Assert.AreEqual(1, Equal.OperationsToEven(chocstart));
}
[TestMethod]
public void OneSix()
{
int[] chocstart = { 1, 6 };
Assert.AreEqual(1, Equal.OperationsToEven(chocstart));
}
[TestMethod]
public void OneOneTwo()
{
int[] chocstart = { 1, 1, 2 };
Assert.AreEqual(1, Equal.OperationsToEven(chocstart));
}
[TestMethod]
public void TwoManyOnes()
{
int[] chocstart = new int[] { 2 }.Concat(Enumerable.Repeat(1, 50)).ToArray();
Assert.AreEqual(1, Equal.OperationsToEven(chocstart));
}
[TestMethod]
public void OneEleven()
{
int[] chocstart = { 1, 11 };
Assert.AreEqual(2, Equal.OperationsToEven(chocstart));
}
[TestMethod]
public void OneFive()
{
int[] chocstart = { 1, 5 };
Assert.AreEqual(2, Equal.OperationsToEven(chocstart));
}
[TestMethod]
public void OneManyFives()
{
int[] chocstart = new int[] { 1 }.Concat(Enumerable.Repeat(5, 12)).ToArray();
Assert.AreEqual(2, Equal.OperationsToEven(chocstart));
}
[TestMethod]
public void OneSixteen()
{
int[] chocstart = { 1, 16 };
Assert.AreEqual(3, Equal.OperationsToEven(chocstart));
}
[TestMethod]
public void OneSeven()
{
int[] chocstart = { 1, 7 };
Assert.AreEqual(2, Equal.OperationsToEven(chocstart));
}
[TestMethod]
public void FiveAscending()
{
int[] chocstart = { 1, 2, 3, 4, 5 };
Assert.AreEqual(6, Equal.OperationsToEven(chocstart));
}
[TestMethod]
public void SampleInput()
{
int[] chocstart = { 2, 2, 3, 7 };
Assert.AreEqual(2, Equal.OperationsToEven(chocstart));
}Those all pass with the algorithm I wrote.
Then I added some large test cases from the problem:
Code:
[TestMethod]
public void TestCase_0_0()
{
int[] chocstart = { 53, 361, 188, 665, 786, 898, 447, 562, 272, 123, 229, 629, 670, 848, 994, 54, 822, 46, 208, 17, 449, 302, 466, 832, 931, 778, 156, 39, 31, 777, 749, 436, 138, 289, 453, 276, 539, 901, 839, 811, 24, 420, 440, 46, 269, 786, 101, 443, 832, 661, 460, 281, 964, 278, 465, 247, 408, 622, 638, 440, 751, 739, 876, 889, 380, 330, 517, 919, 583, 356, 83, 959, 129, 875, 5, 750, 662, 106, 193, 494, 120, 653, 128, 84, 283, 593, 683, 44, 567, 321, 484, 318, 412, 712, 559, 792, 394, 77, 711, 977, 785, 146, 936, 914, 22, 942, 664, 36, 400, 857 };
Assert.AreEqual(10605, Equal.OperationsToEven(chocstart));
}
[TestMethod]
public void TestCase_0_1()
{
int[] chocstart = { 520, 862, 10, 956, 498, 956, 991, 542, 523, 664, 378, 194, 76, 90, 753, 868, 837, 830, 932, 814, 616, 78, 103, 882, 452, 397, 899, 488, 149, 108, 723, 22, 323, 733, 330, 821, 41, 322, 715, 917, 986, 93, 111, 63, 535, 864, 931, 372, 47, 215, 539, 15, 294, 642, 897, 98, 391, 796, 939, 540, 257, 662, 562, 580, 747, 893, 401, 789, 215, 468, 58, 553, 561, 169, 616, 448, 385, 900, 173, 432, 115, 712 };
Assert.AreEqual(8198, Equal.OperationsToEven(chocstart));
}
[TestMethod]
public void TestCase_0_2()
{
int[] chocstart = { 761, 706, 697, 212, 97, 845, 151, 637, 102, 165, 200, 34, 912, 445, 435, 53, 12, 255, 111, 565, 816, 632, 534, 617, 18, 786, 790, 802, 253, 502, 602, 15, 208, 651, 227, 305, 848, 730, 294, 303, 895, 846, 337, 159, 291, 125, 565, 655, 380, 28, 221, 549, 13, 107, 166, 31, 245, 308, 185, 498, 810, 139, 865, 370, 790, 444, 27, 639, 174, 321, 294, 421, 168, 631, 933, 811, 756, 498, 467, 137, 878, 40, 686, 891, 499, 204, 274, 744, 512, 460, 242, 674, 599, 108, 396, 742, 552, 423, 733, 79, 96, 27, 852, 264, 658, 785, 76, 415, 635, 895, 904, 514, 935, 942, 757, 434, 498, 32, 178, 10, 844, 772, 36, 795, 880, 432, 537, 785, 855, 270, 864, 951, 649, 716, 568, 308, 854, 996, 75, 489, 891, 331, 355, 178, 273, 113, 612, 771, 497, 142, 133, 341, 914, 521, 488, 147, 953, 26, 284, 160, 648, 500, 463, 298, 568, 31, 958, 422, 379, 385, 264, 622, 716, 619, 800, 341, 732, 764, 464, 581, 258, 949, 922, 173, 470, 411, 672, 423, 789, 956, 583, 789, 808, 46, 439, 376, 430, 749, 151 };
Assert.AreEqual(18762, Equal.OperationsToEven(chocstart));
}
[TestMethod]
public void TestCase_0_3()
{
int[] chocstart = { 134, 415, 784, 202, 34, 584, 543, 119, 701, 7, 700, 959, 956, 975, 484, 426, 738, 508, 201, 527, 816, 136, 668, 624, 535, 108, 1, 965, 857, 152, 478, 344, 567, 262, 546, 953, 199, 90, 72, 900, 449, 773, 211, 758, 100, 696, 536, 838, 204, 738, 717, 21, 874, 385, 997, 761, 845, 998, 78, 703, 502, 557, 47, 421, 819, 945, 375, 370, 35, 799, 622, 837, 924, 834, 595, 24, 882, 483, 862, 438, 221, 931, 811, 448, 317, 809, 561, 162, 159, 640, 217, 662, 197, 616, 435, 368, 562, 162, 739, 949, 962, 713, 786, 238, 899, 733, 263, 781, 217, 477, 220, 790, 409, 383, 590, 726, 192, 152, 240, 352, 792, 458, 366, 341, 74, 801, 709, 988, 964, 800, 938, 278, 514, 76, 516, 413, 810, 131, 547, 379, 609, 119, 169, 370, 502, 112, 448, 695, 264, 688, 399, 408, 498, 765, 749, 925, 918, 458, 913, 234, 611 };
Assert.AreEqual(16931, Equal.OperationsToEven(chocstart));
}
[TestMethod]
public void TestCase_0_4()
{
int[] chocstart = { 512, 125, 928, 381, 890, 90, 512, 789, 469, 473, 908, 990, 195, 763, 102, 643, 458, 366, 684, 857, 126, 534, 974, 875, 459, 892, 686, 373, 127, 297, 576, 991, 774, 856, 372, 664, 946, 237, 806, 767, 62, 714, 758, 258, 477, 860, 253, 287, 579, 289, 496 };
Assert.AreEqual(5104, Equal.OperationsToEven(chocstart));
}Those all fail and I they're too big to debug and figure out why.
I've detailed my algorithm below.
Code:
/// <summary>
/// Provides a solution to https://www.hackerrank.com/challenges/equal
/// </summary>
public static class Equal
{
#region LongExplanation
/// <summary>
/// Computes the minimum number of operations needed to even out
/// the elements of the array through operations limited to adding
/// either the same number 1, 2 or 5 to every element besides one.
///
/// The following describes how it works.
///
/// chocs = { 5, 1, 11, 6, 1, 4, 1 }
///
/// Put in ascending order, remove repeats, make into a queue:
///
/// Q = { 1, 4, 5, 6, 11 }
///
/// Dequeue the first two elements, save into variables:
///
/// last = 1,
/// cur = 4,
/// Q = { 5, 6, 11 }
///
/// It takes 2 operations to increment 1 to 4, because we increment
/// by 2 and then 1. Save this total number of operations into a variable:
///
/// ops = 2
///
/// We have to add 4-1=3 to every element after the current one, so save
/// that number in a variable too:
///
/// extra = 3
///
/// Move our current and last elements:
///
/// last = cur = 4
/// cur = Q.Dequeue() = 5,
/// Q = { 6, 11 }
///
/// Add the extra to the current element:
///
/// cur = 5 + 3 = 8
///
/// It takes 2 operations to increment last=4 to cur=8, because we incremenet
/// by 2 twice. Update the total number of oprations:
///
/// ops = 2 + 2 = 4
///
/// And add the difference of 4 to extra:
///
/// extra = 3 + 4 = 7
///
/// We repeat this process for two more iterations, until the queue is empty:
///
/// -------------------------
/// last = cur = 8
/// cur = Q.Dequeue() = 6
/// Q = { 11 }
/// cur += 7
/// ops += 1 (add 5 to last=8 to get cur=13)
/// extra += 5
/// --------------------------
/// last = cur = 13
/// cur = Q.Dequeue() = 11
/// Q = { }
/// cur += 12
/// ops += 2 (add 5 twice to last=13 to get cur=23)
/// extra += 10
/// ---------------------------
///
/// Finally we return the cumulative number of operations,
///
/// ops = 7
///
/// Time-Complexity: O(n*log(n)) where n = chocs.Length
/// </summary>
#endregion
public static int OperationsToEven(int[] chocs)
{
Queue<int> q = new Queue<int>(chocs.Distinct().OrderBy(c => c));
if(q.Count < 2)
{
return 0;
}
int extra = 0;
int ops = 0;
int last = q.Dequeue(), cur;
do
{
cur = q.Dequeue() + extra;
int diff = cur - last;
extra += diff;
ops += StepsToCloseDiff(diff);
last = cur;
} while(q.Count > 0);
return ops;
}
/// <summary>
/// Computes the least number of steps it takes to raise the
/// number of chocolates by increments of 1, 2 and 5.
///
/// For example, if we need to raise the number by 14, we do
///
/// Step 1: Add 5
/// Step 2: Add 5
/// Step 3: Add 2
/// Step 4: Add 2
///
/// Time-Complexity: O(1)
/// </summary>
private static int StepsToCloseDiff(int diff)
{
int steps = 0;
steps += diff / 5;
diff %= 5;
steps += diff / 2;
diff %= 2;
steps += diff;
return steps;
}
}Can someone help me figure out where I'm going wrong with these larger test cases?
They are all off by "a little", e.g. Expected=16931 and Actual=16292.