logo

Givet et tal n, find de første k cifre i n^n

Givet et tal n, find de første k cifre i nnhvor k er en værdi mindre end antallet af cifre i nn 
Eksempler:
 

   Input :    n = 10 k = 2    Output :   10 The first 2 digits in 1010 are 10.    Input :    n = 144 k = 6    Output :   637087    Input:    n = 1250 k = 5    Output:    13725 


 


Problemet kan løses på flere måder, hvoraf to er:
Metode 1 (simpel): En naiv metode, der går ud på at beregne den faktiske værdi og derefter dividere med 10, indtil vi får det ønskede svar. Denne metode kan dog ikke modtage input større end n = 15, da det ville forårsage overløb. 
 



C++
// C++ program to find the first k digits of n^n #include    using namespace std; // function that manually calculates n^n and then // removes digits until k digits remain unsigned long long firstkdigits(int n int k) {  unsigned long long product = 1;  for (int i = 0 ; i < n ; i++)  product *= n;  // loop will terminate when there are only  // k digits left  while ((int)(product / pow(10 k)) != 0)  product = product / 10;  return product; } //driver function int main() {  int n = 15;  int k = 4;  cout << firstkdigits(n k);  return 0; } 
Java
// Java program to find the first k digits of n^n public class Digits {  // function that manually calculates n^n and then  // removes digits until k digits remain  static long firstkdigits(int n int k)  {  long product = 1;  for (int i = 0 ; i < n ; i++)  product *= n;    // loop will terminate when there are only  // k digits left  while ((int)(product / Math.pow(10 k)) != 0)  product = product / 10;  return product;  }    public static void main(String[] args)  {  int n = 15;  int k = 4;  System.out.println(firstkdigits(n k));  } } //This code is contributed by Saket Kumar 
Python 3
# Python 3 program to find the  # first k digits of n^n # function that manually calculates  # n^n and then removes digits until # k digits remain def firstkdigits(n k): product = 1 for i in range(n ): product *= n # loop will terminate when there  # are only k digits left while ((product // pow(10 k)) != 0): product = product // 10 return product # Driver Code n = 15 k = 4 print(firstkdigits(n k)) # This code is contributed  # by ChitraNayal 
C#
// C# program to find the // first k digits of n^n using System; class Digits {  // function that manually calculates  // n^n and then removes digits until  // k digits remain  static long firstkdigits(int n int k)  {  long product = 1;  for (int i = 0 ; i < n ; i++)  product *= n;    // loop will terminate when there   // are only k digits left  while ((int)(product / Math.Pow(10 k)) != 0)  product = product / 10;    return product;  }    // Driver code  public static void Main()  {  int n = 15;  int k = 4;  Console.Write(firstkdigits(n k));  } } // This code is contributed by nitin mittal. 
PHP
 // PHP program to find the // first k digits of n^n // function that manually  // calculates n^n and then // removes digits until k // digits remain function firstkdigits($n $k) { $product = 1; for ($i = 0 ; $i < $n ; $i++) $product *= $n; // loop will terminate when  // there are only k digits left while ((int)($product / pow(10 $k)) != 0) $product = (int) $product / 10; return floor($product); } // Driver Code $n = 15; $k = 4; echo firstkdigits($n $k); // This code is contributed by aj_36 ?> 
JavaScript
<script> // Javascript program to find the first k digits of n^n    // function that manually calculates n^n and then  // removes digits until k digits remain  function firstkdigits(nk)  {  let product = 1;  for (let i = 0 ; i < n ; i++)  product *= n;    // loop will terminate when there are only  // k digits left  while (Math.floor(product / Math.pow(10 k)) != 0)  product = Math.floor(product / 10);  return product;  }    let n = 15;  let k = 4;  document.write(firstkdigits(n k));    // This code is contributed by avanitrachhadiya2155 </script> 

Output: 
 

4378


Metode 2: Den næste metode involverer brug af logaritmer til at beregne de første k cifre. Metoden og trinene er forklaret nedenfor:
 

  1. Lad produkt = nn. Tag logaritmen base 10 på begge sider af ligningen. Vi får log10(produkt) = log10(nn) som vi også kan skrive som n*log10(n)
  2. I dette eksempel får vi log10(produkt) = 3871,137516. Vi kan opdele RHS som 3871 + 0,137516, så vores ligning kan nu skrives som log10(produkt) = 3871 + 0,137516
  3. Hæv begge sider med base 10 og ved at bruge ovenstående eksempel får vi produkt = 103871x 100,137516. 103871vil ikke gøre en forskel for vores første k cifre, da det kun flytter decimaler. Vi er interesserede i næste del 100,137516da dette vil bestemme de første par cifre. 
    I dette tilfælde er værdien 100,137516er 1,37251.
  4. Derfor ville vores nødvendige første 5 cifre være 13725.


 

C++
//C++ program to generate first k digits of // n ^ n #include    using namespace std; // function to calculate first k digits // of n^n long long firstkdigits(int nint k) {  //take log10 of n^n. log10(n^n) = n*log10(n)  long double product = n * log10(n);  // We now try to separate the decimal and  // integral part of the /product. The floor  // function returns the smallest integer  // less than or equal to the argument. So in  // this case product - floor(product) will  // give us the decimal part of product  long double decimal_part = product - floor(product);  // we now exponentiate this back by raising 10  // to the power of decimal part  decimal_part = pow(10 decimal_part);  // We now try to find the power of 10 by which  // we will have to multiply the decimal part to  // obtain our final answer  long long digits = pow(10 k - 1) i = 0;  return decimal_part * digits; } // driver function int main() {  int n = 1450;  int k = 6;  cout << firstkdigits(n k);  return 0; } 
Java
// Java program to find the first k digits of n^n import java.util.*; import java.lang.*; import java.io.*; class KDigitSquare {  /* function that manually calculates   n^n and then removes digits until   k digits remain */  public static long firstkdigits(int n int k)  {  //take log10 of n^n.   // log10(n^n) = n*log10(n)  double product = n * Math.log10(n);    /* We will now try to separate the decimal   and integral part of the /product. The   floor function returns the smallest integer  less than or equal to the argument. So in  this case product - floor(product) will  give us the decimal part of product */  double decimal_part = product - Math.floor(product);    // we will now exponentiate this back by   // raising 10 to the power of decimal part  decimal_part = Math.pow(10 decimal_part);    /* We now try to find the power of 10 by   which we will have to multiply the decimal   part to obtain our final answer*/  double digits = Math.pow(10 k - 1) i = 0;    return ((long)(decimal_part * digits));  }  // driver function  public static void main (String[] args)  {  int n = 1450;  int k = 6;  System.out.println(firstkdigits(nk));  } } /* This code is contributed by Mr. Somesh Awasthi */ 
Python3
# Python3 program to generate k digits of n ^ n  import math # function to calculate first k digits of n^n  def firstkdigits(n k): # take log10 of n^n. # log10(n^n) = n*log10(n) product = n * math.log(n 10); # We now try to separate the decimal  # and integral part of the /product. # The floor function returns the smallest  # integer less than or equal to the argument.  # So in this case product - floor(product)  # will give us the decimal part of product decimal_part = product - math.floor(product); # we now exponentiate this back # by raising 10 to the power of # decimal part decimal_part = pow(10 decimal_part); # We now try to find the power of 10 by  # which we will have to multiply the  # decimal part to obtain our final answer digits = pow(10 k - 1); return math.floor(decimal_part * digits); # Driver Code  n = 1450; k = 6; print(firstkdigits(n k)); # This code is contributed by mits 
C#
// C# program to find the first k digits of n^n using System; class GFG {    /* function that manually calculates   n^n and then removes digits until   k digits remain */  public static long firstkdigits(int n int k)  {    // take log10 of n^n.   // log10(n^n) = n*log10(n)  double product = n * Math.Log10(n);    /* We will now try to separate the decimal   and integral part of the /product. The   floor function returns the smallest integer  less than or equal to the argument. So in  this case product - floor(product) will  give us the decimal part of product */  double decimal_part = product -  Math.Floor(product);    // we will now exponentiate this back by   // raising 10 to the power of decimal part  decimal_part = Math.Pow(10 decimal_part);    /* We now try to find the power of 10 by   which we will have to multiply the decimal   part to obtain our final answer*/  double digits = Math.Pow(10 k - 1);    return ((long)(decimal_part * digits));  }  // driver function  public static void Main ()  {  int n = 1450;  int k = 6;  Console.Write(firstkdigits(nk));  } } // This code is contributed by nitin mittal 
PHP
 // PHP program to generate  // k digits of n ^ n // function to calculate  // first k digits of n^n function firstkdigits($n $k) { // take log10 of n^n.  // log10(n^n) = n*log10(n) $product = $n * log10($n); // We now try to separate the  // decimal and integral part  // of the /product. The floor  // function returns the smallest  // integer less than or equal to  // the argument. So in this case // product - floor(product) will  // give us the decimal part of product $decimal_part = $product - floor($product); // we now exponentiate this back  // by raising 10 to the power of // decimal part $decimal_part = pow(10 $decimal_part); // We now try to find the power  // of 10 by which we will have  // to multiply the decimal part  // to obtain our final answer $digits = pow(10 $k - 1); $i = 0; return floor($decimal_part * $digits); } // Driver Code $n = 1450; $k = 6; echo firstkdigits($n $k); // This code is contributed by m_kit ?> 
JavaScript
<script> // Javascript program to find the first k digits of n^n    /* function that manually calculates   n^n and then removes digits until   k digits remain */  function firstkdigits(nk)  {  //take log10 of n^n.   // log10(n^n) = n*log10(n)  let product = n * Math.log10(n);    /* We will now try to separate the decimal   and integral part of the /product. The   floor function returns the smallest integer  less than or equal to the argument. So in  this case product - floor(product) will  give us the decimal part of product */  let decimal_part = product - Math.floor(product);    // we will now exponentiate this back by   // raising 10 to the power of decimal part  decimal_part = Math.pow(10 decimal_part);    /* We now try to find the power of 10 by   which we will have to multiply the decimal   part to obtain our final answer*/  let digits = Math.pow(10 k - 1) i = 0;    return (Math.floor(decimal_part * digits));  }    // Driver code  let n = 1450;  let k = 6;  document.write(firstkdigits(n k));    // This code is contributed by rag2127 </script> 

Output:  
 

962948


Denne kode kører i konstant tid og kan håndtere store inputværdier på n
 

Opret quiz