题目 2740: 蓝桥杯2022年第十三届决赛真题-最少的 1（C/C++/Java组）

 时间限制: 1s 内存限制: 256MB

题目描述

给定一个正整数 n ，找出所有 n 的倍数的二进制表示中最少有多少个 1。 

输入格式

输入一行包含一个整数 n 。

输出格式

输出一行包含一个整数表示答案。 

样例输入

7

样例输出

3

提示

14 是 7 的倍数，其二进制表示为 1110，有 3 个 1。7 也是 7 的倍数，二进制表示中也有 3 个 1 。可以证明 7 的其他倍数的二进制表示不会具有更少的 1。

对于 10% 的评测用例，n ≤ 10；

对于 25% 的评测用例，n ≤ 200；

对于 50% 的评测用例，n ≤ 5000；

对于所有评测用例，1 ≤ n ≤ 106。

标签