TRICOINP - Editorial

editorial
, , ,
1

Problem Link - Coins And Triangle in Binary Search

Problem Statement:

Chef belongs to a very rich family which owns many gold mines. Today, he brought N gold coins and decided to form a triangle using these coins. Isn’t it strange? Chef has a unusual way of forming a triangle using gold coins, which is described as follows:
He puts 1 coin in the 1st row, then puts 2 coins in the 2nd row, then puts 3 coins in the 3rd row, and so on.
Chef is interested in forming a triangle with maximum possible height using at most N coins. Can you tell him the maximum possible height of the triangle?

Approach:

To form a triangle of height h, the total number of coins required is the sum of the first h natural numbers:
Total coins for height h=1+2+3+⋯+h=h(h+1)/2

  • Using Binary Search:
    • Initialize two pointers one with 1 and other with number of coins.
    • Calculate the midpoint. Compute the total number of coins required for a triangle of height mid using the formula mid(mid+1)/2.
    • Check if the total number of coins for height mid is less than or equal to N
    • Update the answer to mid (as it is a valid height).
    • Move the lower_bound to mid+1 to check if a larger height is possible.
    • If the total number of coins for height mid exceeds N, reduce the upper bound to mid−1 to try for a smaller height.

Complexity:

  • Time Complexity: O(log N) for binary search
  • Space Complexity: O(1) No extra space used.