Minimum Operations to Zero Out a Sequence

Given a positive integer \( n \), we have a sequence \( [1, 2, \ldots, n] \). In one operation, you are allowed to select an arbitrary subset of the sequence and subtract the same positive integer (which must not exceed any selected element) from every number in that subset. The task is to determine the minimum number of operations required to transform the entire sequence into zeros.

Observation: Each number \( i \) in the sequence can be expressed in binary. A greedy strategy is to subtract powers of \(2\) from all elements that have the corresponding bit set. In fact, the minimum number of operations required is equal to the number of bits in the binary representation of \( n \), i.e. \( \lfloor \log_2{n} \rfloor + 1 \).

Input: A single integer \( n \) (\(1 \le n \le 10^{9}\) or appropriate bound based on implementation).

Output: The minimum number of operations needed to reduce the sequence to all zeros.

Example:

• Input: 3
  Sequence: [1, 2, 3]
  Operations: subtract 1 from elements with odd numbers (1 and 3) to get [0, 2, 2], then subtract 2 from the non-zero elements; hence answer is 2.

inputFormat

The input consists of a single line containing a positive integer \( n \).

outputFormat

Output a single integer representing the minimum number of operations required.

sample

1

1