首页 > 代码库 > Find n’th number in a number system with only 3 and 4
Find n’th number in a number system with only 3 and 4
这是在看geeksforgeeks时看到的一道题,挺不错的,题目是
Given a number system with only 3 and 4. Find the nth number in the number system.
First few numbers in the number system are: 3, 4, 33, 34, 43, 44, 333, 334, 343, 344,
433, 434, 443, 444, 3333, 3334, 3343, 3344, 3433, 3434, 3443, 3444, …
(题目链接)
简单的说,就是:
在一个由3、4组成的数字序列中找出第n个数,这个序列是这样的:
3、4、33、34、43、44、333、334、343、344、433、434、......
比如要找出第5个数,则输出43。
这是Zoho面试的一道题,题目不算很难。
仔细看这个序列,可以看到每个数字由3或4组成,我们可以把这个序列分组,以数字的位数来分:
第一组就是只有一位的数字:3,4
第二组就是只有二位的数字:33,34,43,44
第三组就是只有三位的数字:333, 334, 343, 344, 433, 434, 443, 444
.......
仔细观察一下每一组,可以看到,每一组都是有规律的,废话,肯定有规律。
把每一组的3用0替代,4用1替代,则
第一组就是:0,1
第二组就是:00,01,10,11
第三组就是:000,001,010,011,100,101,110,111
所以,只要知道要求的数字是第几组第几个就行了,把要求的n转化为
n = 2^i + a
求出i和a,i是位数,也就是第i个分组,a是分组中的第a个(a可以为0)
然后把a转为二进制,对于这个二进制,0就用3替代,1就用4替代,就求出问题的解了。
geeksforgeeks里还有其他解法。
Find n’th number in a number system with only 3 and 4