[DailyCoding] 25 | power

✏️ Description

Return power input two numbers

• input
  
  • base: int (base >= 2)
  • exponent: int (exponent >= 0)
• output
  
  • return long
  • return rest of divided by 94,906,249 of the actual calculation results
• caution
  
  • Avoid using Math.pow, power operators
  • Time Complexity O(logN)
• example of in/output

ong output = power(3, 40);
System.out.println(output); // --> 19334827

📚 TIL

• Power: Multiply the same number multiple times
• Why return with the rest divided by 94,906,249?
  • Sometimes description shows the rest of the answer divided by a specific number, which is to prevent overflow in the final operation.
  • temp * temp || temp * temp * base is under 94,906,249 both can exceed or not 94_906_249, but when the exponent is odd,  multiply the base once more will exceed the specific number, so the rest must be obtained one more time so divide it make it doesn't exceed this number in the middle of the operation!

👩🏻‍💻 Implementation

final static int MOD = 94_906_249;

power(int base, int exponent) {
    if(exponent == 0) return 1;

    long half = power(base, exponent / 2);
    long result = half * half % MOD;

    if(exponent % 2 == 1)
        return result * base % MOD;

    return result;
}