Java solution, Pigeonhole principle.


  • 1
    S

    The idea is to find a cycle in the power. As the number is modded by 1337, there must be a duplication among the power of from 1 to 1337. This tells which position in cycle b corresponds to.

    public int superPow(int a, int[] b) {
    	int []pows = new int[1337];    // max cycle is 1337 	
        Set<Integer> set = new HashSet<Integer>();
        
        // pigeon hole principle dictates that must be a duplicate among the power from 1 to 1337 if moded by 1337
        int cycle = 0;
        int val = 1;
        for (int i = 0; i < 1337; i++)  {
            val = (int)(((long)val * a) % 1337);
            // cycle found
            if (set.contains(val)) break;
            set.add(val);
            pows[cycle++] = val;
        }
        
        // b: String -> BigInteger
        StringBuilder str = new StringBuilder();
        for(int v: b) str.append(v);
        BigInteger bVal = new BigInteger(str.toString());
        
        bVal = bVal.subtract(new BigInteger("1")).mod(new BigInteger("" + cycle));
        return pows[bVal.intValue()];
    }

Log in to reply
 

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