logo

Dato un numero n, trovare le prime k cifre di n^n

Dato un numero n trovare le prime k cifre di nNdove k è un valore inferiore al numero di cifre in nN 
Esempi:
 

   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 


 


Il problema può essere risolto in diversi modi di cui due sono:
Metodo 1 (semplice): Un metodo ingenuo che consiste nel calcolare il valore effettivo e poi dividerlo per 10 fino ad ottenere la risposta richiesta. Tuttavia, questo metodo non può accettare input maggiori di n = 15 poiché causerebbe un overflow. 
 



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> 

Produzione : 
 

4378


Metodo 2: Il metodo successivo prevede l'utilizzo dei logaritmi per calcolare le prime k cifre. Il metodo e i passaggi sono spiegati di seguito:
 

  1. Sia prodotto = nN. Prendi il logaritmo in base 10 su entrambi i lati dell'equazione. Otteniamo il registro10(prodotto) = log10(NN) che possiamo anche scrivere come n*log10(N)
  2. In questo esempio otteniamo log10(prodotto) = 3871.137516. Possiamo dividere il lato destro come 3871 + 0,137516 quindi la nostra equazione può ora essere scritta come log10(prodotto) = 3871 + 0,137516
  3. Alza entrambi i lati con base 10 e usando l'esempio sopra otteniamo prodotto = 103871x100,137516. 103871non farà differenza per le nostre prime k cifre poiché sposta solo i punti decimali. Siamo interessati alla prossima parte 100,137516poiché ciò determinerà le prime cifre. 
    In questo caso il valore 100,137516è 1.37251.
  4. Quindi le nostre prime 5 cifre richieste sarebbero 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> 

Produzione :  
 

962948


Questo codice viene eseguito in tempo costante e può gestire grandi valori di input di n
 

Crea quiz