2554. Maximum Number of Integers to Choose From a Range I - Detailed Explanation

Problem Statement

You are given two positive integers, n and maxSum. The task is to choose some number of distinct integers from the range [1, n] such that their total sum does not exceed maxSum. Return the maximum number of integers you can choose.

Example 1

• Input: n = 4, maxSum = 6
• Output: 3
• Explanation: The optimal selection is [1, 2, 3] with a sum of 6. Although 4 is available, 1 + 2 + 3 + 4 = 10 exceeds maxSum.

Example 2

• Input: n = 5, maxSum = 15
• Output: 5
• Explanation: You can choose all the integers [1, 2, 3, 4, 5] because their sum is exactly 15.

Example 3

• Input: n = 2, maxSum = 1
• Output: 1
• Explanation: The only valid selection is [1] since 1 ≤ maxSum, and choosing 2 would exceed it.

Constraints:

• 1 ≤ n
• 1 ≤ maxSum
• (n and maxSum can be large, so an efficient solution is needed.)

Hints

1. Greedy Insight:
   To maximize the number of integers while keeping the sum as small as possible, you should choose the smallest available numbers first.

2. Sum Formula:
   The sum of the first k natural numbers is given by the formula:
   [ \text{sum} = \frac{k(k+1)}{2} ] Use this formula to determine the largest k such that (\frac{k(k+1)}{2} \leq \text{maxSum}). However, remember that you cannot choose more than n integers, so the answer is the minimum between n and this k.

Approaches

Greedy / Mathematical Approach

• Idea:
  The optimal way to maximize the count is to start with the smallest numbers. The sum of the first k natural numbers is the smallest possible sum for k distinct numbers in the range [1, n]. Find the largest k such that: [ \frac{k(k+1)}{2} \leq \text{maxSum} ] Then, the answer is: [ \text{answer} = \min(n, k) ]

• Steps:

  1. Use the quadratic formula to solve the inequality: [ k^2 + k - 2 \times \text{maxSum} \leq 0 ]
  2. Compute: [ k_{\text{candidate}} = \left\lfloor \frac{\sqrt{1 + 8 \times \text{maxSum}} - 1}{2} \right\rfloor ]
  3. The final answer is: [ \min(n, k_{\text{candidate}}) ]

• Complexity:

  • Time: O(1) – Constant time arithmetic operations.
  • Space: O(1)

Binary Search Approach

• Idea:
  Instead of using a closed-form solution, use binary search to find the maximum k such that: [ \frac{k(k+1)}{2} \leq \text{maxSum} ] Iterate over the possible values of k (from 0 to n) to find the largest valid k.

• Steps:

  1. Initialize two pointers: low = 0 and high = n.
  2. While low ≤ high, compute mid = low + (high - low) // 2.
  3. If (\frac{\text{mid} \times (\text{mid} + 1)}{2} \leq \text{maxSum}), then move the search to the right (i.e., set low = mid + 1).
  4. Otherwise, move the search to the left (i.e., set high = mid - 1).
  5. The largest mid that satisfies the condition is your candidate, and the answer is: [ \min(n, \text{candidate}) ]

• Complexity:

  • Time: O(log n)
  • Space: O(1)

Complexity Analysis

• Greedy / Mathematical Approach:

  • Time: O(1)
  • Space: O(1)

• Binary Search Approach:

  • Time: O(log n)
  • Space: O(1)

Python Code