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?

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.

and here is another shiny golden certificate

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 10^{9} + 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.

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?

LikeLike

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.

LikeLike

Can you share solution

LikeLike