Previous portal:

C# brush through Leetcode interview question series (1) - Introduction and tools

C# brush the serial of Leetcode interview questions (2): No.38 - report number

C# brush over Leetcode interview question series (3): No.728 - self divisor

C# brush over Leetcode interview question series (4): No.633 - sum of squares

C # brush through Leetcode interview question series (5): No.593 - effective square

In the last LeetCode interview question, we analyzed a math problem with Medium difficulty - effective square, and provided three methods. Today, let's continue to analyze an interview question with Medium difficulty.

The interview question to be analyzed today is question 372 on LeetCode,

LeetCode - 372. Super power

https://leetcode.com/problems/super-pow/

### Title Description

Your task is to calculate the modulus of 1337. A is a positive integer and b is a very large positive integer and will be given in the form of an array.

Example 1:

a = 2 b = [3] result: 8

Example 2:

a = 2 b = [1,0] result: 1024

Example 3:

a = 2147483647 b = [2,0,0] result: 1198

thank:

Special thanks @ Stomach_ache adds this question and creates all test cases.

- Difficulty: Medium
- Submission times: 6.3K
- Pass times: 2.3K
- Passing rate: 35.95%
- Related labels
- mathematics https://leetcode-cn.com/tag/math

- Similar topics Pow(x, n) https://leetcode-cn.com/problems/powx-n

### Relevant knowledge and ideas:

Understand the meaning of the question:

This problem requires the calculation of% 1337. In the input, a is given in decimal form, while b is given in array form. Each digit in decimal system is stored in the array in turn.

Solution 1: directly use string processing

public class Solution { public int SuperPow(int a, int[] b) { int res = 0; StringBuilder sb = new StringBuilder(); foreach (var item in b) sb.Append(item); int.TryParse(sb.ToString(), out int p); var val = (int) Math.Pow(a, p); res = val - (val / 1337)*1337; return res; } }

You will find that when the logarithm b is large (example 3), it will be out of bounds. Therefore, we need to use the properties of modular operation to optimize~

The common properties of modular operation are as follows:

Distribution rate:

(a + b) mod n = [(a mod n) +(b mod n) ] mod n.

mod n = [(a mod n) (b mod n) ] mod n.

D mod() = (d mod a) + a [(D \ a) mod b] + [(D \ a \ b) mod C], where \ is the operator of the quotient of Euclidean division.

c mod(a + b) =(c mod a) + [ (a + b) ] mod b - [ (a + b) ] mod a.

Division: A/B

Mod n = [(a mod n) (MOD n)] mod n, when b and N are coprime, the right side is defined. vice versa.

Inverse multiplication:

[( mod n) ( mod n) ] mod n = a mod n.

Special properties: X% = = x & ()

In addition, a related concept is congruence relation.

This question needs to be used in the allocation rate: Mod n = [(a mod n) (b Mod n)] mod n

Solution 2 AC Code:

public class Solution { const int Mod0 = 1337; public int SuperPow(int a, int[] b) { if (b.Length == 0) return 1; var res = 1; for (int i = b.Length - 1; i >= 0; i--) { res = powMod(a, b[i]) * res % Mod0; a = powMod(a, 10); } return res; } private int powMod(int a, int m) { a %= Mod0; int result = 1; for (int i = 0; i < m; i++) result = result * a % Mod0; return result; } }

Rank:

Execution time: 116 ms, beating 100.00% of users in all csharp submissions

It is reasonable to say that if a%m is changed to a-(a/m)*m, the code will run faster, and the direct modular operation will be slower.

Solution 3 AC Code:

public class Solution { const int Mod0 = 1337; public int SuperPow(int a, int[] b) { if (b.Length == 0) return 1; var res = 1; for (int i = b.Length - 1; i >= 0; i--) { var powModResult = powMod(a, b[i]) * res; res = powModResult - (powModResult / Mod0) * Mod0; a = powMod(a, 10); } return res; } private int powMod(int a, int m) { a = a - (a / Mod0) * Mod0; int result = 1; for (int i = 0; i < m; i++) result = result * a - (result * a / Mod0) * Mod0; return result; } }

Rank: execution time: 112 ms, beating 100.00% of users in all csharp submissions

Example code:

https://github.com/yanglr/Leetcode-CSharp/tree/master/leetcode372 .

Welcome to propose better solutions~

End