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