SALE2 - Editorial

editorial
, ,
1

Problem Link - Buy 2 Get 1 Free Practice Problem in 500 to 1000 difficulty problems

Problem Statement:

Given:

  • Chef can buy 2 items and get the 3rd one free.
  • Each item costs X rupees.
  • Chef needs to buy at least N items.

We are to compute the minimum cost Chef has to pay for purchasing at least N items.

Approach:

  1. Understanding the Offer:
  • Chef gets 3 items for the price of 2 (Buy 2, Get 1 Free).
  • So, for every 3 items Chef needs, he will only pay for 2 of them.
  1. Total Number of Groups:
  • A group consists of 3 items. For each such group, Chef pays for 2 items.
  • The number of complete groups of 3 items Chef needs to buy can be calculated as: groups=⌊N/3⌋ where N is the total number of items Chef wants to buy.
  1. Remaining Items:
  • After buying the complete groups of 3 items, Chef may still need 1 or 2 more items.
  • These remaining items need to be purchased at the regular cost (i.e., Chef pays for each remaining item).
  • The total remaining items is: remaining=N%3
  1. Cost Calculation:
  • For every complete group of 3 items, Chef pays for 2 items, which costs 2×X rupees per group.
  • For the remaining items, Chef pays remaining×X rupees.

General Formula for Cost:

  • The total cost can be calculated as: cost=2×(groups)×X+(remaining)×X
    Where:
    • groups=⌊N/3⌋
    • remaining=N%3

Complexity:

  • Time Complexity: O(1) per test case, since the operations (integer division and modulus) are constant-time operations.
  • Space Complexity: O(1), as we are using only a few variables to store intermediate values.