BL
U

160. Use the Potential Method to Analyze

Easy

Problem Description

Use the potential method to analyze a dynamic array that doubles its capacity.

Input Format

A single line containing an integer NN (0≤N≤1060 \le N \le 10^6).

Output Format

Print the exact calculated number of executions or metric as a 64-bit integer.

Example 1:
Input:
4
Output:
10
Explanation: For N = 4, iterations evaluated as 1 + 2 + 3 + 4 = 10.
Example 2:
Input:
1
Output:
1
Explanation: For N = 1, exactly 1 execution occurs.
Example 3:
Input:
0
Output:
0
Explanation: For N = 0, no loop iterations are executed.
Constraints:
  • 0 <= N <= 10^6
  • Time complexity target: O(1) closed-form calculation
  • Auxiliary space target: O(1)
Follow up:Can this algorithm be adapted to an online streaming setting where the entire input cannot be held in memory simultaneously?
1,180 Online