Solution to Tape-Equilibrium by codility

16 Jan

Question: http://codility.com/demo/take-sample-test/tape_equilibrium

Question Name: TapeEquilibrium

The variable of head stores the sum of the heading part of the tape. And the variable of tail stores the sum of tailing part. Then, we move the index from 2nd position to the last 2nd position. Every time we move the index, we adjust both head and tail, compute and compare the difference. 

75 Replies to “Solution to Tape-Equilibrium by codility

  1. Why is this solution wrong?

    • You should change the last for loop from “for(i=0;i<N;++i)” to “for(i=0;i<N-1;++i)”. Neither the head part nor the tail part could be empty here.
      In addition, the if(N==1) is useless. The problem states that N >= 2.

  2. Thank you very much, it worked perfectly ! But why if the tail and the head part must not be counted should not change the for-loop to “for(i=1;i<N-1;++i)" ?
    Thank you again for your advise,
    Theodoros (Theo)

    • When i == 0, the head part is A[0], and the tail part is the remaining part A[1] ~ A[N-1]
      When i == N-2, the head part is A[0] ~ A[N-2], and the tail part is the last element A[N-1]
      My pleasure to see my code be helpful!

  3. Tape-Equilibrium by Codility : C Program

    Edited by Admin: The last two lines are missing in your orginal comments. I added it according your method.

    • Not 100% sure about compiler output, but in case it misbehaves:
      last_minimum = (current_min < last_minimum) ? current_min : last_minimum;
      will probably execute assignment no matter what..
      if(current_min < last_minimum)
      {
      last_minimum = current_min;
      }
      will wave the execution of the rest if true

      • 🙁 Missing the last check in that case… But surely there is a way to stick the last check without executing the inner scope a billion times :))

      • Yes, your solution is right and kind of better.
        “? :” is simple and clean. But it costs a little bit more time (should be very very little here). IMO, persons sometimes use this kind of “?:” to keep the code short.
        BTW, thanks for your awesome discussion!

      • totalSum-A[0] is the sum of the tail.
        A[0] is the sum of the head
        So last_minimum = abs(totalSum-A[0]-A[0]); is the difference between head and tail.

  4. I keep getting 91% on this and I can’t figure out why:

    It says that I’m getting the wrong answer on small elements. “Got 0 Expected 20”.
    Any idea why?

    • My experience is, you would better to print out that test case, and debug according to that data.
      Please do give us an update message, after you try to debug and fix it.
      PS: what is the programming language? JavaScript?

      • Yeah I used JavaScript. The problem is that they don’t give the specific test case that it’s failing. On the list that shows scores for correctness tests, it is labeled Small with a subheading of small elements. It says that it got 0 and was expecting 20.
        I wish I simply knew what the test case was but it doesn’t say what data it is using. I was hoping someone would be able to see some obvious problem with this.

        • B gave the right fix. But for your information, as Codility says:
          you can use console.log for debugging purposes, i.e. console.log(‘this is a debug message’);
          So you could use the console.log to output ALL the test cases.

  5. Hi, could you please verify what’s wrong with this java code? I got 91% in the test.

    • Hello! FIrst of all, you can use “System.out.println(XXXX);” in your submission to show the input content A in the test. So you can debug locally, and find out your bug.
      Both head and tail part must be NON-EMPTY. So you need to change

      to

  6. Not sure why this is wrong 🙁

    • Line 2-4 can be rewritten as totalSum = sum(A)
      I cannot find a good reason to initialize the currMin and maxMin as 1000, which may be the reason for failure.
      To debug the submission on codility, please add a line at the very beginning of function as: print A. It will show you the test case. And you can debug locally.

  7. I wrote exactly same code as given in the blog. But after sometime i thought this is the wrong code. This will not give correct result for array which is mix of +ve and -ve numbers
    example: int arr[] ={ 5 ,10, 1, -5, 5 , 3 ,4};

  8. Why loop on an index ? That is neither pythonic nor necessary.

    P.S. Sorry, I can’t find how to format the code properly

    • I agree with you. Your solution is more pythonic. While mine is probably more readable to the non-Pythoner.
      Anyway, thanks for your reminder.

  9. And the Pascal solution (100%)

    • there should be an edit-post in case there is something wrong with my formatting and I see it after posting. For example the “less than” sign… if I add it as “the sign” then it cuts all my following text, if I replace it with &lt then it is displayed exactly like that (less than). I am not too good with manually formatting code but it should not be that difficult… 🙁
      Please correct my code and make it look like it should

  10. Here is a nice C++ solution for TapeEquilibrium from codility, which makes use of iterators. The solution will score you 100% on both correctness and performance. Have fun using it.

  11. Here’s my Java solution, for 100% on both correctness and performance. Didn’t find one here yet so I thought might as well post 🙂

  12. Got 100% solution

  13. #test the method
    A= [3,1,2,4,3]
    print solution(A)
    #Not sure why performance is 0% here. Detected O(N*N)?

    • Your other solution is incomplete. And I removed them.
      If you want to post any comment, please read the guideline firstly on the right column.
      In addition, if you have any bug question, stackoverflow might be a better place to ask. Thanks!

  14. Hi All,
    Thanks for your valuable comments. Here is another solution in C#.
    I hope you like it,
    erncab

    ———————————————————-
    Hi All,
    After some thoughts I implemented a second solution (100/100) https://codility.com/demo/results/demoR47NP2-Q5B/

    which looks simpler than the previous one I implemented above https://codility.com/demo/results/demo7WFVZK-MP6/ (83/91)
    Thanks in advance for any suggestions to improve it even further,
    erncab

    • Thanks for your visiting and discussion!
      PS: please do read the “Guideline for Comments” in the right column, before posting any code.

  15. My solution

  16. === Ruby ===

  17. I didn’t see a solution like mine so sharing. It uses just one loop for calculating sum and min diff. It scored 100/100. As is often said thanks so much for this very helpful forum!

  18. Why is my

    incorrect, but my

    isn’t (apart from being O(N*N))? I can’t figure it out for the life of mine. Anyone?

  19. Isn’t using a function like sum() kind of a cheat if you want to reach O(n) time complexity. It seems like a lower level way to achieve this would be to first make the total sum of the array using some kind of iteration but that would yield a O(2N) complexity no ?

    • Big O is used to measure the order of complexity, rather than the exact complexity. O(2N) is exactly the same as O(N).

  20. My c# solution. 100% ok.
    https://codility.com/demo/results/demo742QXH-MV7/

  21. Hi, thank you for share your solution. I got 100% in correctnes but 0% in performance. I think that my problem was execute a slice twice in each loop iteration, looks:

    What do you think that was my problem?

    • It’s because of the sum(). sum() takes O(N) complexity. Therefore the total time complexity of your solution is O(N^2).

  22. Hi Sheng,
    Thank you for your help. i am fairly new to programming. I just don’t understand why instead of the index, the result is min? I thought the result should be the index that abs(head – tail) = 0 happens and that index would be the result. would you please kindly explain it ?
    Thanks,
    Aram

    • Hello Aram, it’s nothing about programming. The problem says: returns the minimal difference that can be achieved. The return value is not the index.

  23. PHP solution 100%:

  24. I got this 100% on JavaScript (With a little help of reduce).

  25. My C# version..

  26. You can use:

    instead of:

  27. I got this 100% on Java

  28. My Java solution 100%

  29. Thanks for sharing your solution, it helped a lot. My solution is slightly different, with a small optimization:

    Explanation: you don’t need to test every index in the array, going up to the middle element is enough because after it, you’re just swapping the right and the left elements. And abs(left – right) is the same as abs(right – left).

  30. Why is this recursive solution slow?

  31. Solution in overly bulky but comprehensible VB.

  32. https://app.codility.com/demo/results/trainingN2FUQA-EV7/

  33. My Codility Java 100% success solution:

  34. My solution in Python. Detected time complexity O(N). 100%. The basic idea is to slice the list A at index i. Take the absolute value of subtraction of the sum of two sliced list A[:i] and A[i:]. Then return the minimum value. Instead of slicing and using for loop which makes time complexity O(N*N), a mathematical simplification of the form sum(A) – 2*sum(elements up to index i). Sum(A) is constant, whereas using just a for loop for 2*sum(elements up to index) leads to a time complexity of just O(N).

Leave a Reply

Your email address will not be published. Required fields are marked *

Please put your code into a <pre>YOUR CODE</pre> section. Thanks and Happy Coding!