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