英文:
All combinations of two numbers
问题
一个整数如果每一位数字都是3或7,那么它就是一个幸运数。举个例子,数字7、73和33777都是幸运数。你的任务是计算在整数a和b之间有多少个幸运数。
如何在高效的方式下实现这个目标(在1秒内),而不需要遍历所有数字?我已经尝试了很多Java的解决方案,但是它们都不够快。
英文:
An integer is a lucky number if each number in it is 3 or 7. To give an example, the numbers 7, 73, and 33777 are lucky numbers. Your task is to calculate the number of lucky numbers between int(a) and int(b).
How could one achieve this efficiently (in less than 1 sec) without going through all the numbers? I have attempted many solutions in Java however none of them are fast enough.
答案1
得分: 4
由于您需要计算数字而不是列出数字,您可以使用排列和组合来找到答案。
例如,假设在1至999之间查找可以使用3和7的数字。
然后您有3种长度的数字:个位数、两位数和三位数,其中个位数和三位数有约束条件。
对于个位数,由于最小数字是1,而3和7都比它们大,所以有2个数字。
对于两位数,没有约束条件,因此有2 * 2 = 4种组合。
类似地,对于三位数,由于每个位置上允许的最大数字是9,而3和7都比它们小,所以有2 * 2 * 2 = 8种组合。
因此答案是14,将它们全部相加后得到... 这个算法运行速度快,因为它取决于生成数字的大小,即O(n)时间复杂度,其中n是数字的最大长度。
英文:
Since you have to count the numbers and not list the numbers, you can use permutation and combination to find the answer.
Eg let say find between 1 and 999 where you can use 3, 7
Then you have 3 lengths single, double and triple digits with constraints on single and triple digits.
For single since minimum number is 1 and 3, 7 both are greater there 2 numbers.
For double digits you have no constraints hence you have 2 * 2 = 4 combinations
Similarly for 3 digits as max number allowed is 9 in each place and 3,7 are lesser than them there will be 2 * 2 * 2 = 8
So answer is 14 after summing them all... This algorithm will run fast as it depends on the size of the numbers to generate ie o(n) time complexity where n is max length of number.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论