372. Super Pow #

Problem #

Your task is to calculate ab mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.

Example 1:

Input: a = 2, b = [3]
Output: 8

Example 2:

Input: a = 2, b = [1,0]
Output: 1024

Problem Summary #

Your task is to calculate a^b modulo 1337, where a is a positive integer and b is an extremely large positive integer given in the form of an array.

Solution Approach #

Find the result of a^b mod p, where b is a large number.

This problem can be attempted with a brute-force solution. Several operational properties of mod calculation are needed:

  Modular arithmetic property one: (a + b) % p = (a % p + b % p) % p
  Modular arithmetic property two: (a - b) % p = (a % p - b % p + p) % p
  Modular arithmetic property three: (a * b) % p = (a % p * b % p) % p
  Modular arithmetic property four: a ^ b % p = ((a % p)^b) % p

This problem needs properties three and four. For example:

  12345^678 % 1337 = (12345^670 * 12345^8) % 1337
                   = ((12345^670 % 1337) * (12345^8 % 1337)) % 1337  ---> use property three
                   = (((12345^67)^10 % 1337) * (12345^8 % 1337)) % 1337  ---> exponentiation property
                   = ((12345^67 % 1337)^10) % 1337 * (12345^8 % 1337)) % 1337  ---> use property four
                   = (((12345^67 % 1337)^10) * (12345^8 % 1337)) % 1337  ---> use property three in reverse

After the transformations above, the units digit of the exponent 678 is separated out and can be solved independently. Continuing the transformations above can also separate out the 6 and 7 of the exponent. Ultimately, the large number b can be separated digit by digit. As for computing a^b, use fast exponentiation to solve it.

Code #


package leetcode

// Solution 1: fast exponentiation res = res^10 * qpow(a, b[i])
// Modular arithmetic property one: (a + b) % p = (a % p + b % p) % p
// Modular arithmetic property two: (a - b) % p = (a % p - b % p + p) % p
// Modular arithmetic property three: (a * b) % p = (a % p * b % p) % p
// Modular arithmetic property four: a ^ b % p = ((a % p)^b) % p
// For example
// 12345^678 % 1337 = (12345^670 * 12345^8) % 1337
//                  = ((12345^670 % 1337) * (12345^8 % 1337)) % 1337  ---> use property three
//                  = (((12345^67)^10 % 1337) * (12345^8 % 1337)) % 1337  ---> exponentiation property
//                  = ((12345^67 % 1337)^10) % 1337 * (12345^8 % 1337)) % 1337  ---> use property four
//                  = (((12345^67 % 1337)^10) * (12345^8 % 1337)) % 1337  ---> use property three in reverse
func superPow(a int, b []int) int {
	res := 1
	for i := 0; i < len(b); i++ {
		res = (qpow(res, 10) * qpow(a, b[i])) % 1337
	}
	return res
}

// Fast exponentiation to compute x^n
func qpow(x, n int) int {
	res := 1
	x %= 1337
	for n > 0 {
		if (n & 1) == 1 {
			res = (res * x) % 1337
		}
		x = (x * x) % 1337
		n >>= 1
	}
	return res
}

// Solution 2: brute-force solution
// Using the properties above, we can get: a^1234567 % 1337 = (a^1234560 % 1337) * (a^7 % 1337) % k = ((((a^123456) % 1337)^10)% 1337 * (a^7 % 1337))% 1337;
func superPow1(a int, b []int) int {
	if len(b) == 0 {
		return 1
	}
	last := b[len(b)-1]
	l := 1
	// First compute the result of a^x for the units digit, corresponding to (a^7 % 1337)% 1337 in the example above
	for i := 1; i <= last; i++ {
		l = l * a % 1337
	}
	// Then compute the result of a^y excluding the units digit, corresponding to (a^123456) % 1337) in the example above
	temp := superPow1(a, b[:len(b)-1])
	f := 1
	// Corresponds to (((a^123456) % 1337)^10)% 1337 in the example above
	for i := 1; i <= 10; i++ {
		f = f * temp % 1337
	}
	return f * l % 1337
}