所有两个数字的组合

huangapple go评论70阅读模式
英文:

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.

huangapple
  • 本文由 发表于 2020年8月30日 21:26:51
  • 转载请务必保留本文链接:https://go.coder-hub.com/63657919.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定