2022-03-23:在k进制下,最小多小的num,可以让1~num范围的数拥有1的个数不少于n个?
答案2022-03-23:
二分法。
代码用golang编写。代码如下:
package main
import "fmt"
func main() {
ret := minM(5, 2)
fmt.Println(ret)
}
func minM(n, k int) int {
len0 := bits(n, k)
l := 1
r := power(k, len0+1)
ans := r
for l <= r {
m := l + ((r - l) >> 1)
if ones(m, k) >= n {
ans = m
r = m - 1
} else {
l = m + 1
}
}
return ans
}
func bits(num, k int) int {
len0 := 0
for num != 0 {
len0++
num /= k
}
return len0
}
func power(base, power int) int {
ans := 1
for power != 0 {
if (power & 1) != 0 {
ans *= base
}
base *= base
power >>= 1
}
return ans
}
func ones(num, k int) int {
len0 := bits(num, k)
if len0 <= 1 {
return len0
}
offset := power(k, len0-1)
first := num / offset
curOne := num%offset + 1
if first != 1 {
curOne = offset
}
restOne := first * (len0 - 1) * (offset / k)
return curOne + restOne + ones(num%offset, k)
}
执行结果如下:
***
[左神java代码](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2021_12_3_week/Code03_OneCountsInKSystem.java)