小扇和小船的数字游戏 - 华为OD统一考试（C卷）

OD统一考试（C卷）

分值： 200分

题解： Java / Python / C++

题目描述

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

小船给小扇一个正整数 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是满足条件的最小数

题解

题解分析

这道题目要求找到一个比给定的正整数 n 大的数字 m，使得它们的二进制表示中 1 的个数相同。本质上，题目要求在二进制表示中，找到一个比 n 大的具有相同数量的 1 的数。

给出的解法是使用贪心算法。首先，将 n 转换为二进制表示，然后通过贪心地找到可以将某个 0 变成 1 的位置，使得数字变大，同时保持 1 的个数不变。最后输出这个结果。

解题思路

1. 将给定的十进制数 n 转换为二进制表示，并在末尾添加一个 0。
2. 使用贪心算法找到可以将某个 0 变成 1 的位置的索引 idx。
3. 调整 idx 位 0 变成 1，同时调整 idx 前的位，使得低位为 1，高位为 0，且二进制中 1 的个数不变。
4. 输出调整后的结果。

Java

import java.util.Scanner;
import java.util.ArrayList;
/**
 * @author code5bug
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        System.out.println(solve(n));
    }

    // 解决问题的函数
    public static int solve(int n) {
        ArrayList<Integer> bs = new ArrayList<>();
        // 转换为二进制
        while (n > 0) {
            bs.add(n % 2);
            n /= 2;
        }
        // 在列表末尾添加一个 0，以便处理
        bs.add(0);

        // 贪心的寻找可以将 0 变成 1 的地方的索引 idx（使得数字变大）
        // idx 满足低位存在 1 且 bs.get(idx) == 0
        int idx = 0, oneCnt = 0;
        for (; idx < bs.size(); idx++) {
            if (oneCnt > 0 && bs.get(idx) == 0) {
                break;
            }
            oneCnt += bs.get(idx);