7ms Java solution


  • 0
    X

    if a^k % m = a^t % m, then a^(k+1) % m must be equal to a^(t+1).
    Let's say a^14 %m = a^27 %m, then a^28 % m is equal to a^15%m,
    a^k %m = a^(k-13)%m.

    let's have an array to keep the power of 'a' and the index is mod value, example:
    a=2, b=0, modToPower[1] = 0;
    a=2, b =1, modToPower[2] = 1;
    a=2, b =2, modToPower[4] = 2;
    ...
    the length of modToPower is 1337(it can be extended to any other positive integer).
    and once there is b=x, and modToPower[a^b%1337] is existing, then we can exit the loop.

    regarding array 'b', like above if a^k % m = a^(k-13)%m, we can easily map the value represented by array 'b' to mod by 13.
    like a^[1,2,3] = a^123 = a^110 =...= a^6;

    public int superPow(int a, int[] b) {
        if (a <= 0 || b == null || b.length == 0) {
        	return 0;
        }
    	int modNum = 1337;
    	a %= modNum;
    	int[] log = new int[modNum];
    	for (int i = 0; i < log.length; i++) {
    		log[i] = -1;
    	}
    	int startNum = 1;
    	Map<Integer, Integer> powerToModNum = new HashMap<Integer, Integer>();
    	int powerMod;
    	for (int startIndex = 0; ; startIndex++) {
    		startNum %= modNum;
    		if (log[startNum] == -1) {
    			log[startNum] = startIndex;
    			powerToModNum.put(startIndex, startNum);
    			startNum = (startNum*a)%modNum;
    			
    		} else {
    			powerMod = startIndex - log[startNum%modNum];
    			break;
    		}
    	}
    	
    	int j = 0;
    	for (int power : b) {
    		j = (j*10 + power%powerMod)%powerMod;
    	}
    	return powerToModNum.get(j);
    }

Log in to reply
 

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