Pick Up Coupons Google OA 2023 Solution

Pick Up Coupons Google OA 2023 Solution

Several coupons are placed in a row, and to win the prize you need to pick at least 2 coupons of the same value. You can only pick consecutive coupons from the row. Each coupon costs 1 coin, find the minimum number of coins needed to obtain the prize or, -1 if it’s not possible.

Example 1:

Input: coupons = [5, 3, 4, 2, 3, 4, 5, 7]
Output: 4

Explanation:
Because you can buy coupons with values [3, 4, 2, 3] or [4, 2, 3, 4]

Example 2:

Input: coupons = [3, 6, 1, 9]
Output: -1

Pick Up Coupons Google OA

SOLUTION

Program: Pick Up Coupons Google OA Solution in Python

def min_cost_to_win(coupons):
    output = len(coupons) + 1
    di = collections.defaultdict(int)
    basket = []
    for i in range(len(coupons)):
        itm = coupons[i]
        if itm not in basket:
            basket.append(itm)
            di[itm] = i
        else:
            crnt = i - di[itm] + 1
            output = min(output,crnt)
            di[itm] = i
    if output>len(coupons):
        output = -1
    return output

Program: Pick Up Coupons Google OA Solution in Python

def min_cost_to_win(nums):
    last_seen_idx = {}
    ans = len(nums) + 1

    for i, num in enumerate(nums):
        if num in last_seen_idx:
            ans = min(ans, i - last_seen_idx[num] + 1)

        last_seen_idx[num] = i

    return ans if ans < len(nums) + 1 else -1

Program: Pick Up Coupons Google OA Solution in Java

private static int findPrice(int[] coupons) {
        Map<Integer, Integer> hmap = new HashMap<>();
        int price = Integer.MAX_VALUE;
        for(int i=0;i<coupons.length;i++) {
            if(hmap.containsKey(coupons[i])) price = Math.min(price, i - hmap.get(coupons[i]) + 1);
            hmap.put(coupons[i], i);
        }
        
        return price == Integer.MAX_VALUE?-1:price;
}

Related:

Google OA 2023 Questions

Leave a Comment

five − three =