C# brush over Leetcode interview question series serial: No.372 - super power

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 = 

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

Added by hismightiness on Sat, 25 Dec 2021 01:15:57 +0200