Minimum Steps to Reach Target

Given an integer \(T\), representing the target number, the task is to find the minimum number of operations needed to transform the number 1 into \(T\). At each step, you are allowed to either add 1 to the current number or multiply the current number by 2. Formally, if you start from \(1\), in each move you can perform one of the following operations:

• \(x \to x+1\)
• \(x \to 2x\)

Your goal is to determine the least number of steps required such that the resultant number is exactly \(T\). This problem can be solved efficiently using a Breadth-First Search (BFS) strategy or a reverse greedy approach.

inputFormat

The input consists of a single integer \(T\) (\(1 \leq T \leq 10^5\) or larger based on problem constraints) read from standard input.

outputFormat

Output a single integer representing the minimum number of steps required to reach \(T\) starting from 1. The output should be written to standard output.

1

0