Java Code for Online Shopping (TCS Codevita) | PrepInsta

November 28, 2023

Online Shopping

TCS CodeVita is a coding competition organized by TCS every year, in search of world’s best coder. This is a global level coding competition in which coders from all around the world compete for the title of World’s Best Coder. It is one of the sample problem of this year TCS CodeVita season 11 competition.

Question -: An online shopping store announced an offer for the upcoming festive season. In order to avail that offer, we have to collect the tokens for n consecutive days and using those tokens, we can buy items in the sale.
Mithra, a regular customer, wanted to claim those tokens and decided to buy something in the sale. When the tokens season began, she started claiming the tokens. Unfortunately, in between the days, she forgot claiming and missed few tokens. Now the token season is ended. Suddenly, the app gave bumper offer to all users i.e., for any k consecutive days, every user can claim the tokens if they were unclaimed in the token season.
Given an array tokens of size n denoting the number of tokens offered for n consecutive days and another array claim denoting the tokens are claimed or not on those particular days. If claim[i] is 1 then Mithra had claimed otherwise not. Another integer k is given denoting the number of days the bumper offer can be used. A list of items and costs are given. The only rule is that we can buy only one item using those tokens.
Help Mithra in selecting k consecutive days and finally print the item(s) which she can buy aiming for the minimal wastage of tokens. If there are more than one item of same cost, then print them in lexicographical (ascending) order.

Constraints
1 <= n <= 10 ^ 4
0 <= k <= 10 ^ 4
0 <= tokens[i] <= 10 ^ 4
1 <= number of items <= 100
Claim[i] is either 0 or 1
Tokens and claim are arrays of same size

Input
First line contains an integer n denoting the size of the tokens array.
Second line contains the array tokens denoting the number of tokens available for n consecutive days.
Third line contain claim array denoting whether Mithra claimed tokens or not, on these n days.
Fourth line contain the integer k denoting the number of consecutive days bumper offer can be applied.
Last line contains items denoting the items and their costs separated by colon.
Consider below Examples for better understanding.

Output
A single line of item(s) that Mithra can buy with the tokens. If there are more than one, print them in the lexicographical (ascending) order.

Time Limit (secs)
1

Examples

Example 1
Input
8
7 5 0 2 8 6 12 1
1 0 1 1 0 1 1 0
2
Bucket:8 Cot:32 Chair:27 Cooker:37 Gas:45 Fan:34 Mug:3 Ac:100
Output
Fan
Explanation
Of the 8 days of token season, 5 days are already claimed. So, she has to claim from days where a claim is not yet made (wherever the value is 0 in the claim array). By virtue of this she already has 7+2+6+12 = 27 tokens.
Suppose Mithra decided to use the bumper offer for the days 4,5 or 5,6 then the total number of tokens she gains will be 7+2+8+6+12=35. Among all the given items, she can buy a fan which will result in the wastage of only 1 token. Other than fan, buying any items will result in the wastage of a greater number of tokens.

Example 2
Input
12
8 3 6 22 5 0 11 1 0 4 9 6
0 1 0 1 1 0 1 0 1 0 0 0
3
Bucket:8 Cot:32 Geyser:45 Chair:27 Cooker:38 Gas:45 Fan:34 Mug:3 Ac:100 Bulb:15
Output
Gas Geyser
Explanation
Of the 12 days of token season, 5 days are already claimed. So, she has to claim from days where a claim is not yet made (wherever the value is 0 in the claim array). By virtue of this she already has 3+22+5+11 = 41 tokens.
Suppose Mithra decided to use the bumper offer for the days 10,11,12 then the number of tokens she gains will be 3+22+5+11+4+9+6=60. Among all the given items, she can buy gas or geyser which will result in the wastage of only 15 tokens. Other than these, buying any items will result in the wastage of a greater number of tokens.

Java

Run

import java.util.*;

class Item {
    String name;
    int cost;

    public Item(String name, int cost) {
        this.name = name;
        this.cost = cost;
    }
}

public class TokenShopping {

    static List< String> getItemsToBuy(int n, int[] tokens, int[] claim, int k, List< Item> items) {
        List< String> result = new ArrayList<>();

        int maxTokens = 0;
        int startIndex = 0;

        // Find the starting index for the bumper offer
        for (int i = 0; i < n - k + 1; ++i) {
            int currentTokens = 0;
            for (int j = i; j < i + k; ++j) {
                if (claim[j] == 0) {
                    currentTokens += tokens[j];
                }
            }

            if (currentTokens > maxTokens) {
                maxTokens = currentTokens;
                startIndex = i;
            }
        }

        // Calculate the total tokens and find the item(s) to buy
        int totalTokens = 0;
        Map availableItems = new HashMap<>();

        for (int i = startIndex; i < startIndex + k; ++i) {
            if (claim[i] == 0) {
                totalTokens += tokens[i];
            }
        }

        for (Item item : items) {
            if (item.cost <= totalTokens) {
                availableItems.put(item.name, item.cost);
            }
        }

        // Find the minimal wastage and lexicographically smallest item(s)
        int minimalWastage = totalTokens;
        for (Item item : items) {
            if (availableItems.containsKey(item.name)) {
                int wastage = totalTokens - availableItems.get(item.name);
                if (wastage < minimalWastage) {
                    minimalWastage = wastage;
                    result.clear();
                    result.add(item.name);
                } else if (wastage == minimalWastage) {
                    result.add(item.name);
                }
            }
        }

        return result;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int[] tokens = new int[n];
        for (int i = 0; i < n; ++i) {
            tokens[i] = scanner.nextInt();
        }

        int[] claim = new int[n];
        for (int i = 0; i < n; ++i) {
            claim[i] = scanner.nextInt();
        }

        int k = scanner.nextInt();

        scanner.nextLine(); // Consume the newline character
        String itemsInput = scanner.nextLine();
        List< Item> items = new ArrayList< >();

        StringTokenizer tokenizer = new StringTokenizer(itemsInput, ": ");
        while (tokenizer.hasMoreTokens()) {
            String itemName = tokenizer.nextToken();
            int itemCost = Integer.parseInt(tokenizer.nextToken());
            items.add(new Item(itemName, itemCost));
        }

        List< String> result = getItemsToBuy(n, tokens, claim, k, items);

        for (String item : result) {
            System.out.println(item);
        }
    }
}