首页 > 代码库 > 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