Using free theater tickets can be such a tough decision – this algorithm is here to tell you how many different options you have

Kate is a girl that was given  a very nice birthday gift – three theater tickets. She can pick three performances in the next N days that she would like to attend.  On the program, performances are named by integers. Every day, one performance is staged. Kate wants to choose three days (not necessarily consecutive) to go to the theater.

In how many ways can she use her tickets?

Matrix.jpg

Briefly that was the task in the Zinc 2018 Challenge on the Codility platform, sixth challenge that was published this year and sixth Golden Award for my solution.

Zinc2018Performance.png

and here is another shiny golden certificate

ZincCertificate.png

These were the technical details that the solution needed to fulfill:

Two ways are different if the sequences of watched performances are different. Kate likes the theater, so she may watch one performance more than once. For example, if N = 4 and theater program looks as following: [1, 2, 1, 1], Kate has four possibilities to choose the dates: [1, 2, 1, 1], [1, 2, 1, 1], [1, 2, 1, 1], and [1, 2, 1, 1], but they create only three different sequences: (1, 2, 1), (1, 1, 1) and (2, 1, 1). The correct answer for this example is 3. Notice that the order of performances matters, so the first and the last sequences are considered different.

Write a function:

class Solution { public int solution(int[] A); }

that, given an array A consisting of N integers, denoting names of performances for the next N days, returns the number of possible ways to spend the tickets. Since the answer can be very large, provide it modulo 109 + 7 (1,000,000,007).

For example, given A = [1, 2, 1, 1], the function should return 3 as exmplained above.

Given A = [1, 2, 3, 4], the function should return 4. There are four ways to spend tickets: (1, 2, 3), (1, 2, 4), (1, 3, 4) and (2, 3, 4).

Given A = [2, 2, 2, 2], the function should return 1. There is only one way to spend tickets: (2, 2, 2).

Given A = [2, 2, 1, 2, 2], the function should return 4. There are four ways to spend tickets: (1, 2, 2), (2, 1, 2), (2, 2, 1) and (2, 2, 2).

Given A = [1, 2], the function should return 0. Kate cannot use all three tickets in only two days.

Assume that:

  • N is an integer within the range [0..100,000];
  • each element of array A is an integer within the range [1..N].

Complexity:

  • expected worst-case time complexity is O(N);
  • expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

This challenge is already closed, but you can test yourself and try to get to a solution anyways.

https://app.codility.com/programmers/challenges/zinc2018/

Happy coding,

J.

Advertisements

2 thoughts on “Using free theater tickets can be such a tough decision – this algorithm is here to tell you how many different options you have

  1. I couldn’t figure out the solution. I reached this recursion for all unique elements.
    f(n) = f(n-1) + ((n-1) * (n-2))/2
    where f(3) = 1 and f(2) = f(1) = 0
    I couldn’t figure out in case of duplicates what needs to be removed.
    Can you please help me with this?

    Like

  2. Hi Abhishek,

    I think for this problem you should avoid using recursion and try with dynamic programming approach in order to achieve complexity O(N). Work with the number of unique combinations for each of the positions, save that state and update with the next number. Work with the combinations of one and two elements to get to the combinations of three.
    I hope I gave you enough hints so you can came up to your own solution.

    J.

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s