Last Updated: 5 Sep, 2021

Coupons

Moderate

Asked in company

Solve now

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.

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.

Solve now

Approaches

01 Approach

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.

Solve now

02 Approach

In this approach, we will maintain a Hashmap. In it, we will store the index of the current coupon number, and if the coupon number is already in the hash map, we will get its last occurrence and calculate the number of coupons to be picked up.

Each time we calculate the distance, we will check against the current minimum distance.

Algorithm:

Initialise an empty hash map hashMap
Set minDistance as n + 1
Iterate i from 0 to n - 1
- If coupons[i] is in hashMap, then
  - Set minDistance as minimum of minDistance and i - hashMap[coupons[i]]
- Set hashMap[coupon[i]] as i
if minDistance is equal to n + 1, return -1. Otherwise return minDistance.

Solve now