The target length is between 1 and 64. Since the original stick has length 64, every piece obtainable by repeatedly cutting it in half has a power-of-two length: 64, 32, 16, 8, 4, 2, 1.
Write the target in binary. Its set bits express it as a sum of distinct powers of two; each selected piece size is needed exactly once. For example, 23 = 16 + 4 + 2 + 1, so four pieces are needed. Therefore, the answer is the number of set bits in the target. Java’s Integer.bitCount computes this directly without simulating any cuts.
The time complexity is O(1), and the extra space complexity is O(1).
Java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
int target = Integer.parseInt(input.readLine());
System.out.println(Integer.bitCount(target));
}
}