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

本文概述

• C ++
• Java
• Python3
• C#
• 的PHP

考虑仅由数字4和7组成的一系列数字。该系列中的前几个数字是4、7、44、47、74、77、444, ..等。给定数字n, 我们需要找到第n个系列中的编号。

例子：

Input : n = 2
Output : 7

Input : n = 3
Output : 44

Input  : n = 5
Output : 74

Input  : n = 6
Output : 77

我们在下面的文章中讨论了O(n)解决方案。

在只允许两位数字(4和7)的序列中查找第n个元素

在这篇文章中, 将讨论O(log n)解决方案, 该解决方案基于以下数字模式。可以看到数字

""
              /     \
            4         7
          /  \     /  \ 
        44    47   74    77
       /\   /\   /\  /\

这个想法是从头开始填写所需的数字。我们知道可以观察到, 如果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#

//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
?>

输出如下：

774

在此代码中, 总复杂度为O(log n)。因为while循环运行log(n)次。

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。