Candy Discount
Easy · Online assessment (OA) · Full-time
Got this greedy problem in my Nokia OA. A candy shop has a deal where every third candy is free if you buy two, but the free one has to cost less than or equal to the cheaper of the two you paid for. Given an array of candy prices, find the minimum total cost to buy them all. The interviewer asked me to prove why the greedy approach gives the optimal result and whether it still works if the deal applies to every fourth candy instead.
