博客

2022-03-23：在k进制下，最小多小的num，可以让1~num范围的数拥有1的个数不少于n个？

腾讯音乐2022校园招聘。

答案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代码