Coupons

Moderate

0/80

Average time to solve is 20m

Contributed by

6 upvotes

Asked in company

Problem statement

You are given a list of coupons containing 'N' coupon numbers. Your task is to pick up the coupons from the list. You can pick up coupons consecutively. To use any coupons, you have to pick the same number at least two times. Your task is to find the minimum number of coupons you have to pick to avail yourself any coupon. Return -1 if it’s not possible to avail any coupons.

For example:

You are given,’coupons’ = [1, 2, 3, 4, 5, 3, 6], here you can pick up coupons that are [3, 4, 5, 3] and avail coupon number ‘3’, The total number of coupons picked up are 4. Hence the answer is 4.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains the integer ‘T’ representing the number of test cases.

The first line of each test case contains a single integer ‘N’ denoting the number of coupons.

The second line of each test case contains ‘N’ space-separated integers denoting the elements of the array ‘coupons’.

Output Format:

For each test case, print a single integer representing the minimum number of coupons you have picked up from the given array.

Print a separate line for each test case.

Constraints:

1 <= T <= 10
2 <= N <= 10^6
0 <= coupons[i] <= 10^9

Time Limit: 1 sec

Note:

You do not need to print anything. It has already been taken care of. Just implement the function.

Sample Input 1:

2 
7
1 2 3 4 5 3 6
6
2 2 0 1 4 5

Sample Output 1:

4
2

Explanation:

For the first test case, ’coupons’ = [1, 2, 3, 4, 5, 3, 6], here you can pick up coupons that are [3, 4, 5, 3] and avail coupon number ‘3’, The total number of coupons picked up are 4. Hence the answer is 4

For the second test case, ‘coupons’ = [2, 2, 0, 1, 4, 5], here you can pick up coupons that are [2, 2] and avail coupon number ‘2’, The total number of coupons picked up are 2. Hence the answer is 2

Sample Input 2:

Sample Output 2:

-1
3

Hint 1

Hint 2

Try to think of a brute force approach by traversing through the array.

Approaches (2)

Approach 1

Approach 2

Brute Force

In this approach, we will iterate through all the coupons, and if we find any coupon we as the same number as the current coupon, we will check its distance from the current coupon, and if it’s greater than the maximum distance till now, then we will update the maximum distance.

Algorithm:

Set minDistance as n + 1
Iterate i in from 0 to n -1
- Iterate j from i + 1 to n - 1
  - If coupons[i] is equal to coupons[j] then
    - Set minDistance as the minimum of minDistance and j - i + 1
if minDistance is equal to n + 1, return -1. Otherwise return minDistance.

Time Complexity

O(N^2), Where N is the number of coupons.

We are iterating over the array, and for each element, we are iterating over the remaining elements in the array, which will cost O(N^2) time. Hence the overall time complexity is O(N^2).

Space Complexity

O(1).

We are not using extra space. Hence the overall space complexity is O(1).

(100% EXP penalty)

Coupons

Console