2024年华为OD机试真题- 找数字-(C++/Java/python)-OD统一考试（C卷D卷）

2024华为OD机试真题目录-(B卷C卷D卷)-【C++ Java Python】    

题目描述

小扇和小船今天又玩起来了数字游戏，

小船给小扇一个正整数 n（1 ≤ n ≤ 1e9），小扇需要找到一个比 n 大的数字 m，使得 m 和 n 对应的二进制中 1 的个数要相同，如：

• 4对应二进制100
• 8对应二进制1000
• 其中1的个数都为1个

现在求 m 的最小值。

输入描述

输入一个正整数 n（1 ≤ n ≤ 1e9）

输出描述

输出一个正整数 m

用例1

输入

2

输出

4

说明

2的二进制10，

4的二进制位100，

1的个数相同，且4是满足条件的最小数

用例2

输入

7

输出

11

说明

7的二进制111，

11的二进制位1011，

1的个数相同，且11是满足条件的最小数

用例3

输入

6

输出

9

说明

6的二进制0110，

9的二进制位1001，

1的个数相同，且11是满足条件的最小数

解题思路

本题可以通过把十进制数转化成二进制，然后移动1的位置来得到1个数不变，但更小的数。比如：

1000001

1000010

11101

11110

即只需要把最右边开始查到的第一对01变为10即可。

如果没有01的情况如何处理，比如1000，1111，只需要前面加个0，依然可以用前面的方法解答，

01000

10000

01111

10111

但还有一些特殊情况，上述方法不能解决，比如1001111000

1001111000

1010111000  //按照上述方法的答案

1010000111  //实际的正确答案

即01右边存在1时，需要把1全移到最右边。

考点

逻辑分析

代码

c++

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n,ans=0;
    cin>>n;
    string str;
    while(n>0) {
        int res=n%2;
        str=to_string(res)+str;
        n=n/2;
    }
    str="0"+str; //十进制转成二进制字符串
    int onecnt=0; // 记录01右边1的个数
    int len=str.size();
    // 从最右边开始查找
    for(int i=len-