Compute Power(x, n) (Binary Exponentiation)
Advanced Maths DSA practice problem on Onlearn.
Difficulty: medium.
Topics: Different approaches to compute power(n, x) efficiently, Mathematical Algorithms, Modular Arithmetic, Recursion, Divide and Conquer, Time Complexity, Space Complexity, iteration, divide and conquer, recursion, time complexity analysis, exponentiation.
Problem Statement You are given three integers, N, X, and M. Your task is to calculate (N^X) % M. This means you need to find the remainder when N raised to the power of X is divided by M. The result should be non negative. Input Specification The input consists of a single line containing three space separated integers: N, X, and M. 1 <= N <= 10^9 0 <= X <= 10^9 1 <= M <= 10^9 + 7 Output Specification Print a single integer, the result of (N^X) % M. Sample Test Cases Input: 2 10 1000 Output: 24 Explanation: 2^10 = 1024. 1024 % 1000 = 24. Difficulty: Medium