题目描述
小扇和小船今天又玩起来了数字游戏,
小船给小扇一个正整数 n(1 ≤ n ≤ 1e9),小扇需要找到一个比 n 大的数字 m,使得 m 和 n 对应的二进制中 1 的个数要相同,如:
4对应二进制100
8对应二进制1000
其中1的个数都为1个
现在求 m 的最小值。
输入描述
输入一个正整数 n(1 ≤ n ≤ 1e9)
输出描述
输出一个正整数 m
用例
输入 | 2 |
输出 | 4 |
说明 |
2的二进制10, 4的二进制位100, 1的个数相同,且4是满足条件的最小数 |
输入 | 7 |
输出 | 11 |
说明 |
7的二进制111, 11的二进制位1011, 1的个数相同,且11是满足条件的最小数 |
题目解析
我们可以举几个例子来说明此题的解法:
n: 10010100
m:10011000
n: 11101001
m:11101010
n: 11100010
m:11100100
可以发现,想要找到符合要求的m,其实只需要将 n 二进制串中从右往左找到的第一组 "01" 子串 变为 "10" 即可。
这样就能在不新增二进制'1'的情况下,且差距最小的情况下,找到比n大的最小的m的二进制串
那么对于:
n = 111111
n = 10000
这种找不到 "01" 子串的情况,该怎么处理呢?
很简单,给n的二进制串最前面拼接一个0即可,即上面两个n的二进制串变为
n = 0111111 => m = 1011111
n = 010000 => m = 100000
此时前面方法依旧适用。
但是上面方法依旧是存在问题的,什么问题,因为我们将"01"变为"10"的过程中实际上对于该子串后面的部分也会产生影响。
比如
n = 10000111100
如果我们将 01 子串变为 10,则m的二进制串为
m = 10001011100
此时m虽然比n大,但是并不是最小的m,此时由于红色部分发生了进位操作,因此红色部分后面的子串还有变小的可能,比如更优的m二进制串应该为:
m = 10001000111
因此,我们还需要将红色子串后面的部分的'1'全部集中放到尾部。
JS算法源码
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
// 输入输出处理
void (async function () {
// 将整数n转为二进制字符串
const nBinStr = "0" + Number(await readline()).toString(2);
const mBinCharArr = [...nBinStr];
let countOne = 0;
for (let i = mBinCharArr.length - 2; i >= 0; i--) {
if (mBinCharArr[i] == "0" && mBinCharArr[i + 1] == "1") {
// 从右向左找到了第一组"01"子串,则替换为"10"
mBinCharArr[i] = "1";
mBinCharArr[i + 1] = "0";
// 如果第一组"01"子串右边存在1
if (countOne > 0) {
// 则将第一组"01"子串的右边部分的'1'要全部集中到尾部
for (let j = i + 2; j < mBinCharArr.length; j++) {
if (j < mBinCharArr.length - countOne) {
mBinCharArr[j] = "0";
} else {
mBinCharArr[j] = "1";
}
}
}
break;
}
if (mBinCharArr[i + 1] == "1") countOne++; // 记录第一组"01"子串右边1的个数
}
console.log(parseInt(mBinCharArr.join(""), 2));
})();
Java算法源码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
// 将整数n转为二进制字符串
String nBinStr = "0" + Integer.toBinaryString(n);
char[] mBinCharArr = nBinStr.toCharArray();
int countOne = 0;
for (int i = mBinCharArr.length - 2; i >= 0; i--) {
if (mBinCharArr[i] == '0' && mBinCharArr[i + 1] == '1') {
// 从右向左找到了第一组"01"子串,则替换为"10"
mBinCharArr[i] = '1';
mBinCharArr[i + 1] = '0';
// 如果第一组"01"子串右边存在1
if (countOne > 0) {
// 则将第一组"01"子串的右边部分的'1'要全部集中到尾部
for (int j = i + 2; j < mBinCharArr.length; j++) {
if (j < mBinCharArr.length - countOne) {
mBinCharArr[j] = '0';
} else {
mBinCharArr[j] = '1';
}
}
}
break;
}
if (mBinCharArr[i + 1] == '1') countOne++; // 记录第一组"01"子串右边1的个数
}
int m = Integer.parseInt(new String(mBinCharArr), 2);
System.out.println(m);
}
}
Python算法源码
# 输入获取
nBinStr = bin(int(input()))
mBinCharArr = list("0" + nBinStr[2:])
countOne = 0
for i in range(len(mBinCharArr) - 2, -1, -1):
# 从右向左找到了第一组"01"子串,则替换为"10"
if mBinCharArr[i] == '0' and mBinCharArr[i+1] == '1':
mBinCharArr[i] = '1'
mBinCharArr[i+1] = '0'
# 如果第一组"01"子串右边存在1
if countOne > 0:
# 则将第一组"01"子串的右边部分的'1'要全部集中到尾部
for j in range(i+2, len(mBinCharArr)):
if j < len(mBinCharArr) - countOne:
mBinCharArr[j] = '0'
else:
mBinCharArr[j] = '1'
break
# 记录第一组"01"子串右边1的个数
if mBinCharArr[i+1] == '1':
countOne += 1
m = int("".join(mBinCharArr), 2)
print(m)
C算法源码
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void dec2bin(int num, char *s) {
int i = 0;
while (num > 0) {
s[i++] = (char) (num % 2 + '0');
num /= 2;
}
// strrev(s); // 该函数只能在windows系统使用,OJ一般搭建在Linux系统上,因此无法使用该函数
int l = 0;
int r = i - 1;
while (l < r) {
char tmp = s[l];
s[l] = s[r];
s[r] = tmp;
l++;
r--;
}
}
int main() {
int n;
scanf("%d", &n);
char nBinStr[1000] = {'