Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

C/++/# Minimum # of ops to even out an array by...

  1. Apr 5, 2017 #1
    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:

    Code (Text):

            [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 (Text):

            [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 (Text):

        /// <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.
     
  2. jcsd
  3. Apr 5, 2017 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Why don't you test intermediate cases?
    [1,5,5] is a particularly interesting test case.

    You assume that it is optimal to bring the lowest colleague to the level of the next-lowest. That is not always optimal.

    There is a simplification to the problem that saves a lot of trouble with adding numbers. Subtract.
     
  4. Apr 5, 2017 #3
    Huh?
     
  5. Apr 6, 2017 #4

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    The absolute number of chocolates for everyone does not matter, only differences are interesting. Giving "everyone but X" N elements is equivalent to taking N away from X. The latter makes it much easier to find the optimal solution.
     
  6. Apr 6, 2017 #5
    I haven't studied the code... at all... but try to remove the call to Distinct() and see what happens.
     
  7. Apr 7, 2017 #6
    Boom.

    Code (Text):

            public static int OperationsToEven(int[] chocs)
            {
                if(chocs.Length < 2)
                    return 0;
                int min = chocs.Min();
                return chocs.Sum(i => StepsToCloseDiff(i - min));
            }
     
     
  8. Apr 7, 2017 #7
    Nevermind. This fails for {1, 5, 5}. Expected: 3. Actual: 4.
     
  9. Apr 7, 2017 #8

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    See post #2.
    Sometimes it is good to reduce all chocolates / pick every colleague at least once (but with different amounts).

    [2,5,5,5] is another interesting test case once your code handles [1,5,5] correctly.
     
  10. Apr 7, 2017 #9
    So the solution is

    Min(MyWay, OtherWay)

    ??

    How could one prove that?
     
  11. Apr 8, 2017 #10
    What do you mean by OtherWay?

    I admit I've looked at the discussion where the solution is described, I don't know if you want to figure it out yourself or not?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Minimum # of ops to even out an array by...
  1. C# arrays (Replies: 1)

  2. Array storage (Replies: 1)

Loading...