在只允许使用2位数字(4和7)的序列中查找第n个元素|S2 (log(n)方法)

本文概述

C ++
Java
Python3
C#
的PHP

考虑仅由数字4和7组成的一系列数字。该系列中的前几个数字是4、7、44、47、74、77、444, ..等。给定数字n, 我们需要找到第n个系列中的编号。
【在只允许使用2位数字(4和7)的序列中查找第n个元素|S2 (log(n)方法)】例子：

Input : n = 2 Output : 7Input : n = 3 Output : 44Input: n = 5 Output : 74Input: n = 6 Output : 77

我们在下面的文章中讨论了O(n)解决方案。
在只允许两位数字(4和7)的序列中查找第n个元素
在这篇文章中, 将讨论O(log n)解决方案, 该解决方案基于以下数字模式。可以看到数字

"" /\ 47 /\/\ 44477477 /\/\/\/\

这个想法是从头开始填写所需的数字。我们知道可以观察到, 如果n为奇数, 则最后一位为4, 如果n为偶数, 则最后一位为7。填完最后一位数字后, 我们移至树中的父节点。如果n为奇数, 则父节点对应于(n-1 / 2。其他父节点对应于(n-2)/ 2。
C ++

//C++ program to find n-th number containing //only 4 and 7. #include< bits/stdc++.h> using namespace std; string findNthNo( int n) { string res = "" ; while (n> = 1) { //If n is odd, append 4 and //move to parent if (n & 1) { res = res + "4" ; n = (n-1)/2; }//If n is even, append 7 and //move to parent else { res = res + "7" ; n = (n-2)/2; } }//Reverse res and return. reverse(res.begin(), res.end()); return res; }//Driver code int main() { int n = 13; cout < < findNthNo(n); return 0; }

Java

//java program to find n-th number //containing only 4 and 7. public class GFG {static String findNthNo( int n) { String res = "" ; while (n> = 1 ) {//If n is odd, append //4 and move to parent if ((n & 1 ) == 1 ) { res = res + "4" ; n = (n - 1 ) /2 ; }//If n is even, append //7 and move to parent else { res = res + "7" ; n = (n - 2 ) /2 ; } }//Reverse res and return. StringBuilder sb = new StringBuilder(res); sb.reverse(); return new String(sb); }//Driver code public static void main(String args[]) { int n = 13 ; System.out.print( findNthNo(n) ); } }//This code is contributed by Sam007

Python3

# Python3 program to find # n-th number containing # only 4 and 7. def reverse(s): if len (s) = = 0 : return s else : return reverse(s[ 1 :]) + s[ 0 ]def findNthNo(n): res = ""; while (n> = 1 ):# If n is odd, append # 4 and move to parent if (n & 1 ): res = res + "4" ; n = ( int )((n - 1 ) /2 ); # If n is even, append7 # and move to parent else : res = res + "7" ; n = ( int )((n - 2 ) /2 ); # Reverse res # and return. return reverse(res); # Driver code n = 13 ; print (findNthNo(n)); # This code is contributed # by mits

//C# program to find n-th number //containing only 4 and 7. using System; class GFG {static string findNthNo( int n) { string res = "" ; while (n> = 1) {//If n is odd, append 4 and //move to parent if ((n & 1) == 1) { res = res + "4" ; n = (n - 1) /2; }//If n is even, append 7 and //move to parent else { res = res + "7" ; n = (n - 2) /2; } }//Reverse res and return. char [] arr = res.ToCharArray(); Array.Reverse(arr); return new string (arr); }//Driver Code public static void Main() { int n = 13; Console.Write( findNthNo(n) ); } }//This code is contributed by Sam007

的PHP

< ?php //PHP program to find //n-th number containing //only 4 and 7.function findNthNo( $n ) { $res = "" ; while ( $n> = 1) { //If n is odd, append //4 and move to parent if ( $n & 1) { $res = $res . "4" ; $n = (int)(( $n - 1) /2); }//If n is even, append //7 and move to parent else { $res = $res . "7" ; $n = (int)(( $n - 2) /2); } }//Reverse res //and return. return strrev ( $res ); }//Driver code $n = 13; echo findNthNo( $n ); //This code is contributed //by mits ?>

输出如下：