BSEX02 - Editorial

editorial
,
1

Understanding the Problem

We are given N bricks and need to construct a pyramid in layers.

  • The 1st layer requires 1 brick.
  • The 2nd layer requires 2 bricks.
  • The 3rd layer requires 3 bricks.
  • … and so on.

The i-th layer requires exactly i bricks.

Our goal is to determine the maximum number of complete layers that can be built using the given N bricks.

Key Observations

If we build k complete layers, the total number of bricks required is given by the sum of the first k natural numbers:

Sk = k * (k + 1) / 2

We need to find the largest value of k such that: Sk <= N

This equation suggests a binary search approach to efficiently determine the maximum number of layers that can be built.

Approach

1. Understanding the Search Space

  • The number of layers is at most when all bricks form a complete pyramid.
  • This means that the maximum number of layers possible is somewhere between 0 and N.
  • We can apply binary search to efficiently find the largest k that satisfies the equation Sk <= N.

2. Binary Search Execution

  1. Initialize two pointers:

    • left = 0 (minimum possible layers)
    • right = N (maximum possible layers)
    • result = 0 (stores the maximum valid layer count)

  2. Perform binary search:

    • Compute mid = (left + right) / 2.
    • Calculate total_bricks = (mid * (mid + 1)) / 2.
    • If total_bricks <= N:
      • This means that mid layers can be built, so we increase the search range (left = mid + 1).
      • Update result = mid.
    • Otherwise, total_bricks > N, meaning mid layers exceed available bricks, so we decrease the search range (right = mid - 1).

  3. Return result, which stores the maximum number of complete layers that can be built.

Complexity Analysis

  • Binary search operates in O(log N) time, since we repeatedly halve the search space.
  • The space complexity is O(1) as we use only a few extra variables.
  • A naive approach using iteration would take O(sqrt(N)) time, but binary search is faster.