Java 6 ms AC solution using HashMap, easy to understand.


  • 0
    Z

    Since an integer mod 1337 can only be 0 - 1336, we can build a HashMap record a sequence of the (a mod 1337) to certain power. The sequence will be repeated afterwards.

    After we build the map, we need to figure out (b mod map.size()), and find out the key in the map and return the value.

    However, (b mod map.size()) is not easy to find, since b is out of integer bound. So we cut the array b by 4 digits each time and mode 1337, and continuously shrink the length until finally calculate it out.

    public class Solution {
        static final int N = 1337;
        public int superPow(int a, int[] b) {
            int aMod = a % N;
            if (aMod == 0 || aMod == 1) return aMod;
            HashMap<Integer, Integer> map = buildModMap(aMod);
            int key = findKey(b, map.size());
            return map.get(key);
        }
        
        private HashMap<Integer, Integer> buildModMap(int aMod) {
            HashMap<Integer, Integer> map = new HashMap<>();
            int count = 1;
            int mod = aMod;
            while (map.isEmpty() || mod != aMod) {
                map.put(count, mod);
                count++;
                mod = (mod * aMod) % N;
            }
            return map;
        }
        
        private int findKey(int[] b, int mapSize) {
            int n = b.length / 4;
            int last = b.length % 4;
            int fourCut = 0;
            for (int i = 0; i < n; i++) {
                fourCut = 10000 * fourCut + 1000 * b[4 * i] + 100 * b[4 * i + 1] + 10 * b[4 * i + 2] + b[4 * i + 3];
                fourCut %= mapSize;
            }
            int tenPower = 1;
            int lastSum = 0;
            for (int i = 0; i < last; i++) {
                lastSum += b[b.length - 1 - i] * tenPower;
                tenPower *= 10;
            }
            fourCut = fourCut * tenPower + lastSum;
            return (fourCut - 1) % mapSize + 1;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.