Solution to Count-Distinct-Slices by codility

17 Apr

Question: https://codility.com/demo/take-sample-test/count_distinct_slices

Question Name: Count-Distinct-Slices or CountDistinctSlices

17 thoughts on “Solution to Count-Distinct-Slices by codility

  1. Hi,

    I was trying to solve this problem in Java, and couldn’t figure out where I went wrong. Perhaps, could you take a look at it and point out the mistake?

  2. I will explain a little bit of code which was cryptic to me:

    result += (newBack – back) * (front – back + front – newBack + 1) / 2

    The above line of code is equal to the below ones:
    result += (front – back) * (front – back + 1) / 2
    result -= (front – newBack) * (front – newBack + 1) / 2

  3. Hey Sheng ,
    Can you please explain following line
    ‘ result += (newBack – back) * (front – back + front – newBack + 1) / 2 ‘
    Almost every solution uses this but I havent found why this formula is used .
    Have you used any theorem to derive this ?

    • Just like Mr. Botond Orban said, you can deduce the formula from his equation set:
      (front – back) * (front – back + 1) / 2 – (front – newBack) * (front – newBack + 1) / 2
      = (newBack – back) * (front – back + front – newBack + 1) / 2

      PS: the formula: 1+2+3+4+…+n-1+n = n*(n+1)/2

    • Please refer to comment from @Botond Orban:
      result += (newBack – back) * (front – back + front – newBack + 1) / 2 is the same as:
      result += (front – back) * (front – back + 1) / 2 – (front – newBack) * (front – newBack + 1) / 2.
      And
      (front – back) * (front – back + 1) / 2 is the number of slices in A[back : front + 1],
      (front – newBack) * (front – newBack + 1) / 2. is for A[newBack : front + 1]

  4. Ok, I got 90 and always failed the range check. I didn’t figure out the reason until 2016! 🙂
    For whatever ever reason, I thought the int_max is something starting with 2 and with 11 digits, but it only has 10 digits. So, after this great discovery, I finally got my first successful submit in 2016!
    BTW, the cleanup of the lookup table may not be necessary.

  5. Well, the reason I came back here is because I fall into the same trap again 🙁

    First of all, I overlooked the integer overflow here again. Then, when I tried to fix it, I put 1e10 instead of 1e9, which took me 4 hours to figure that out!

    “got 705082704 expected 1000000000”

    Sad, old enough to count 0s wrong…

    I present here a slight different solution than above using array, which is almost as same as Sheng’s python solution.

  6. another one that’s 100/100 but doesn’t use the n(n+1)/2 formula, as it instead adds up the new slices on each loop iteration, making the code longer but the math simpler

  7. Hi

    Here is my solution… it was easier for me to understand… basically I am counting the eligible slice ending at a given index.

  8. Codility 100%, no math, one plain cycle solution.
    Hope code is tagged correctly now 🙂

  9. this is my sample code

Leave a Reply

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