首页 > 其他 > 详细

编程之美 set 4 找到符合条件的数

时间:2014-02-25 13:28:27      阅读:326      评论:0      收藏:0      [点我收藏+]

题目

任意给定一个正整数 N, 求一个最小的正整数 M (M > 1), 使得 N*M 的十进制表达式中只有 0 和 1.

 

解法

1. 枚举0,1能够组成的数字, 可以组成一颗二叉树

 

bubuko.com,布布扣

 

然后由 BFS 算法最终能够得到目标解. 但时间复杂度太高

2. 优化. 考虑对每一个节点加上一个属性, 对 N 求余的值. 假设两个节点X, Y的余相同, 那么由该节点扩展的下一层的 4 个子节点, 分别为 10*X, 10*X+1, 10*Y, 10*Y+1. 由取模的定理知道 10*X MOD N == 10*Y MOD N, 10*X +1 MOD N == 10*Y +1 MOD N

假设 X < Y, 那么 Y 节点的存在便失去了意义. 因为假如 X,Y 对 N 取模为0, 那么返回的结果肯定在 X 的子树上

bubuko.com,布布扣

时间复杂度的计算. 因为对N求余有 N 个节点, 所以每一层的搜索空间由 指数大小缩小到 o(n) 大小 

编程之美 set 4 找到符合条件的数

原文:http://www.cnblogs.com/xinsheng/p/3564857.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!