如何使用最小的幻数集来获得总和？幻数是只有0和1的组合的整数,例如0, 1, 10, 11, 100, 101, 110, 111.....等等.
例子:
23 requires 3 magic numbers - 11 + 11 + 1
120 requires 2 magic numbers - 110 + 10
我尝试了什么:
我的想法是从最接近总和的幻数开始,但这不会导致最小数量的幻数.
例如,在总和120的情况下,最接近120的幻数是111,这使我得到9.然而,要添加缺失的9,所需的幻数总数为10 [111 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1]
但是,只需2个幻数即可达到120 - [ 110 + 10] - 这意味着我的逻辑不能产生正确的结果.
问题已经得到解答,我只是想改进这个问题.
Era*_*ran 10
这是一个提示:
2 3:1 1 + 1 1 + 1(3个 幻数)
1 2 0:1 1 0+ 1 0(2个幻数)
目标数字中的最高位是答案,因为您需要精确的k幻数(在相关位置都有1),以便总和包含数字k.
因此,算法将通过将目标总和分成数字来开始.例如,如果输入为3052,则应创建以下数组:
int[] digits = {3,0,5,2};
将目标总和拆分为数字时,您也可以找到最大的数字.
int max = 5;
现在我们知道我们需要5个幻数,剩下的就是找到它们.您可以通过迭代数字max时间数组来完成此操作.
在每次迭代中,您将创建一个幻数,其1数字对应于数组的正值.您还减少了这些值.
第一次迭代:
3,0,5,2 -> create magic number 1011 & decrement the array values to 2,0,4,1
第二次迭代:
2,0,4,1 -> create magic number 1011 & decrement the array values to 1,0,3,0
第3次迭代:
1,0,3,0 -> create magic number 1010 & decrement the array values to 0,0,2,0
第四次迭代:
0,0,2,0 -> create magic number 10 & decrement the array values to 0,0,1,0
第五次迭代:
0,0,1,0 -> create magic number 10 & decrement the array values to 0,0,0,0
我们完成了,神奇的数字是1011 + 1011 + 1010 + 10 + 10 = 3052.