Find the first and last M digits from K-th power of N

Namachila November 18, 2025

0 0 6 minutes read

Given a two integers N and K, the task is to find the first M and last M digits of the number N^K.
Examples:

Input: N = 2345, K = 3, M = 3
Output: 128 625
Explanation:
2345³ = 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¹² = 8916100448256

Naive Approach:
The simplest approach to solve the problem is to calculate the value of N^K and iterate to first M digits and find the last M digits by N^K mod 10^M.
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 10^yWhere y is a decimal number.
Let x = N^K
N^K = 10^y
Taking log₁₀ on both sides of the above expression, we get:
K * log₁₀(N) = log₁₀(10^y)
=> K * log₁₀(N) = y * (log₁₀10)
=> y = K * log₁₀(N)
Now y will be a decimal number of form abc—.xyz—
Therefore,
N^K = 10^{abc—.xyz—}
=> N^K = 10^{abc— + 0.xyz—}
=> N^K = 10^abc— * 10^0.xyz—
In the above equation, 10^abc— only moves the decimal point forward.
By calculating 10^0.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 N^K by calculating (N^K)mod(10^M).
Calculate K * log₁₀(N).
Calculate 10^{K * log}_¹⁰^(N).
Find the first M digits by calculating 10^{K * log}_¹⁰^(N) * 10^{M – 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 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>

Output:

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 inputs
N, K, M = 2345, 3, 3
first_M_digits, last_M_digits = find_digits_1(N, K, M)
print(first_M_digits, last_M_digits)  # Output: 128 625
 
N, K, M = 12, 12, 4
first_M_digits, last_M_digits = find_digits_1(N, K, M)
print(first_M_digits, last_M_digits)  # Output: 8916 8256

Output

128 625
8916 8256

Time Complexity: O(KlogN + M)
Auxiliary Space: O(KlogN)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!