Dados dos números enteros N y K , la tarea es encontrar el primer M y el último M dígitos del número N K .
Ejemplos:
Entrada: N = 2345, K = 3, M = 3
Salida: 128 625
Explicación:
2345 3 = 128 95213 625
Por lo tanto, los primeros M(= 3) dígitos son 128 y los últimos tres dígitos son 625.
Entrada: N = 12 , K = 12, M = 4
Salida: 8916 8256
Explicación:
12 12 = 8916 10044 8256
Enfoque ingenuo:
el enfoque más simple para resolver el problema es calcular el valor de N K e iterar a los primeros M dígitos y encontrar los últimos M dígitos por N K mod 10 M .
Complejidad de tiempo: O(K)
Espacio auxiliar: O(1)
Enfoque eficiente:
El enfoque anterior se puede optimizar mediante la siguiente observación:
Consideremos un número x que se puede escribir como 10 y Donde y es un número decimal.
Sea x = N K
N K = 10 y
Tomando log 10 en ambos lados de la expresión anterior, obtenemos:
K * log 10 (N) = log 10 (10 y )
=> K * log 10 (N) = y * (log 10 10)
=> y = K * log 10 (N)
Ahora y será un número decimal de forma abc—.xyz—
Por lo tanto,
N K = 10 abc—.xyz—
=> NK = 10 abc— + 0.xyz—
=> N K = 10 abc— * 10 0.xyz—
En la ecuación anterior, 10 abc— solo mueve el punto decimal hacia adelante.
Al calcular 10 0.xyz— , los primeros M dígitos se pueden averiguar moviendo el punto decimal hacia adelante.
Siga los pasos a continuación para resolver el problema:
- Encuentre los primeros M dígitos de N K calculando (N K )mod(10 M ) .
- Calcular K * log 10 (N) .
- Calcula 10 K * log 10 (N) .
- Encuentre los primeros M dígitos calculando 10 K * log 10 (N) * 10 M – 1 .
- Imprime el primer y último M dígito obtenido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement // the above approach #include <bits/stdc++.h> #define ll long long int using namespace std; // Function to find a^b modulo M ll modPower(ll a, ll b, ll M) { ll res = 1; while (b) { if (b & 1) res = res * a % M; a = a * a % M; b >>= 1; } return res; } // Function to find the first and last // M digits from N^K void findFirstAndLastM(ll N, ll K, ll M) { // Calculate Last M digits ll lastM = modPower(N, K, (1LL) * pow(10, M)); // Calculate First M digits ll firstM; double y = (double)K * log10(N * 1.0); // Extract the number after decimal y = y - (ll)y; // Find 10 ^ y double temp = pow(10.0, y); // Move the Decimal Point M - 1 digits forward firstM = temp * (1LL) * pow(10, M - 1); // Print the result cout << firstM << " " << lastM << endl; } // Driver Code int main() { ll N = 12, K = 12, M = 4; findFirstAndLastM(N, K, M); return 0; }
Java
// Java program to implement // the above approach class GFG{ // Function to find a^b modulo M static long modPower(long a, long b, long M) { long res = 1; while (b > 0) { if (b % 2 == 1) res = res * a % M; a = a * a % M; b >>= 1; } return res; } // Function to find the first and last // M digits from N^K static void findFirstAndLastM(long N, long K, long M) { // Calculate Last M digits long lastM = modPower(N, K, (1L) * (long)Math.pow(10, M)); // Calculate First M digits long firstM; double y = (double)K * Math.log10(N * 1.0); // Extract the number after decimal y = y - (long)y; // Find 10 ^ y double temp = Math.pow(10.0, y); // Move the Decimal Point M - 1 digits forward firstM = (long)(temp * (1L) * Math.pow(10, (M - 1))); // Print the result System.out.print(firstM + " " + lastM + "\n"); } // Driver Code public static void main(String[] args) { long N = 12, K = 12, M = 4; findFirstAndLastM(N, K, M); } } // This code is contributed by Rajput-Ji
Python3
# Python3 program to implement # the above approach from math import * # Function to find a^b modulo M def modPower(a, b, M): res = 1 while (b): if (b & 1): res = res * a % M a = a * a % M b >>= 1 return res # Function to find the first and # last M digits from N^K def findFirstAndLastM(N, K, M): # Calculate Last M digits lastM = modPower(N, K, int(pow(10, M))) # Calculate First M digits firstM = 0 y = K * log10(N * 1.0) # Extract the number after decimal y = y - int(y) # Find 10 ^ y temp = pow(10.0, y) # Move the Decimal Point M - 1 # digits forward firstM = int(temp * pow(10, M - 1)) # Print the result print(firstM, lastM) # Driver Code N = 12 K = 12 M = 4 findFirstAndLastM(N, K, M) # This code is contributed by himanshu77
C#
// C# program to implement // the above approach using System; using System.Collections.Generic; class GFG{ // Function to find a^b modulo M static long modPower(long a, long b, long M) { long res = 1; while (b > 0) { if (b % 2 == 1) res = res * a % M; a = a * a % M; b >>= 1; } return res; } // Function to find the first and last // M digits from N^K static void findFirstAndLastM(long N, long K, long M) { // Calculate Last M digits long lastM = modPower(N, K, (1L) * (long)Math.Pow(10, M)); // Calculate First M digits long firstM; double y = (double)K * Math.Log10(N * 1.0); // Extract the number after decimal y = y - (long)y; // Find 10 ^ y double temp = Math.Pow(10.0, y); // Move the Decimal Point M - 1 digits forward firstM = (long)(temp * (1L) * Math.Pow(10, (M - 1))); // Print the result Console.Write(firstM + " " + lastM + "\n"); } // Driver Code public static void Main(String[] args) { long N = 12, K = 12, M = 4; findFirstAndLastM(N, K, M); } } // This code is contributed by gauravrajput1
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find a^b modulo M function modPower(a, b, M) { var res = 1; while (b) { if (b & 1) res = res * a % M; a = a * a % M; b >>= 1; } return res; } // Function to find the first and last // M digits from N^K function findFirstAndLastM(N, K, M) { // Calculate Last M digits var lastM = modPower(N, K, Math.pow(10, M)); // Calculate First M digits var firstM; var y = K * Math.log10(N * 1.0); // Extract the number after decimal y = y - parseInt(y); // Find 10 ^ y var temp = Math.pow(10.0, y); // Move the Decimal Point M - 1 digits forward firstM = temp * Math.pow(10, M - 1); // Print the result document.write( parseInt(firstM) + " " + parseInt(lastM) ); } // Driver Code var N = 12, K = 12, M = 4; findFirstAndLastM(N, K, M); </script>
8916 8256
Complejidad temporal: O(log K)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por sri_srajit y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA