Given a two integers N and K, the task is to find the first M and last M digits of the number NK .
Examples:
Input: N = 2345, K = 3, M = 3
Output: 128 625
Explanation:
2345 3 = 12895213625
Therefore, the first M(= 3) digits are 128 and the last three digits are 625.Input: N = 12, K = 12, M = 4
Output: 8916 8256
Explanation:
12 12 = 8916100448256
Naive Approach:
The simplest approach to solve the problem is to calculate the value of NK and iterate to first M digits and find the last M digits by NK mod 10M.
Time Complexity: O(K)
Auxiliary Space: O(1)
Efficient Approach:
The above approach can be optimized by the following observation:
Let us consider a number x which can be written as 10y Where y is a decimal number.
Let x = NK
NK = 10 y
Taking log10 on both sides of the above expression, we get:
K * log10(N) = log10(10 y)
=> K * log10(N) = y * (log1010)
=> y = K * log10(N)
Now y will be a decimal number of form abc—.xyz—
Therefore,
NK = 10abc—.xyz—
=> NK = 10abc— + 0.xyz—
=> NK = 10abc— * 100.xyz—
In the above equation, 10abc— only moves the decimal point forward.
By calculating 100.xyz—, the first M digits can be figured out by moving the decimal point forward.
Follow the steps below to solve the problem:
- Find the first M digits of NK by calculating (NK)mod(10M).
- Calculate K * log10(N).
- Calculate 10K * log10(N).
- Find the first M digits by calculating 10K * log10(N) * 10M – 1 .
- Print the first and last M digits obtained.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>#define ll long long intusing namespace std;// Function to find a^b modulo Mll 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^Kvoid 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 Codeint main(){ ll N = 12, K = 12, M = 4; findFirstAndLastM(N, K, M); return 0;} |
Java
// Java program to implement// the above approachclass GFG{// Function to find a^b modulo Mstatic 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^Kstatic 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 Codepublic 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 approachfrom math import *# Function to find a^b modulo Mdef 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^Kdef 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 CodeN = 12K = 12M = 4findFirstAndLastM(N, K, M) # This code is contributed by himanshu77 |
C#
// C# program to implement// the above approachusing System;using System.Collections.Generic;class GFG{// Function to find a^b modulo Mstatic 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^Kstatic 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 Codepublic 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 Mfunction 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^Kfunction 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 Codevar N = 12, K = 12, M = 4;findFirstAndLastM(N, K, M);</script> |
8916 8256
Time Complexity: O(log K)
Auxiliary Space: O(1)
Using Math and String Operations:
Approach:
In this approach, we will use math and string operations to calculate the required digits. We will first calculate the result of N^K and then convert it to a string. We will then extract the first M digits and last M digits from the string.
- Calculate N^K using the ** operator for exponentiation.
- Convert the result to a string.
- Extract the first M digits using slicing: result[:M].
- Extract the last M digits using slicing: result[-M:].
- Convert the extracted digits from strings to integers.
- Return the first and last M digits as a tuple.
Python3
def find_digits_1(N, K, M): # Calculate N^K result = str(N ** K) # Extract first and last M digits first_M_digits = result[:M] last_M_digits = result[-M:] return int(first_M_digits), int(last_M_digits)# Test the function with the given inputsN, K, M = 2345, 3, 3first_M_digits, last_M_digits = find_digits_1(N, K, M)print(first_M_digits, last_M_digits) # Output: 128 625N, K, M = 12, 12, 4first_M_digits, last_M_digits = find_digits_1(N, K, M)print(first_M_digits, last_M_digits) # Output: 8916 8256 |
128 625 8916 8256
Time Complexity: O(KlogN + M)
Auxiliary Space: O(KlogN)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
