Étant donné un nombre n, trouver les k premiers chiffres de nnoù k est une valeur inférieure au nombre de chiffres de nn
Exemples :
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
Le problème peut être résolu de plusieurs manières, dont deux :
Méthode 1 (simple) : Une méthode naïve qui consiste à calculer la valeur réelle puis à la diviser par 10 jusqu'à obtenir la réponse souhaitée. Cependant, cette méthode ne peut pas accepter une entrée supérieure à n = 15 car cela provoquerait un débordement.
C++
// C++ program to find the first k digits of n^n #include
// 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 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# 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 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 ?> <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>
Sortir :
4378
Méthode 2 : La méthode suivante consiste à utiliser des logarithmes pour calculer les k premiers chiffres. La méthode et les étapes sont expliquées ci-dessous :
- Soit produit = nn. Prenons le logarithme en base 10 des deux côtés de l'équation. Nous obtenons le journal10(produit) = journal10(nn) que nous pouvons également écrire sous la forme n*log10(n)
- Dans cet exemple, nous obtenons le journal10(produit) = 3871.137516. Nous pouvons diviser le RHS comme 3871 + 0,137516 afin que notre équation puisse maintenant être écrite sous forme de log10(produit) = 3871 + 0,137516
- Élevons les deux côtés avec la base 10 et en utilisant l'exemple ci-dessus, nous obtenons produit = 103871x100,137516. 103871ne fera aucune différence avec nos k premiers chiffres car cela ne décale que les points décimaux. Nous sommes intéressés par la prochaine partie 100,137516car cela déterminera les premiers chiffres.
Dans ce cas, la valeur de 100,137516est 1,37251. - Par conséquent, nos 5 premiers chiffres requis seraient 13725.
//C++ program to generate first k digits of // n ^ n #include
// 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 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# 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 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 ?> <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>
Sortir :
962948
Ce code s'exécute en temps constant et peut gérer de grandes valeurs d'entrée de n