Java, find cycle & mod approach


  • 0
    P
    public class Solution {
        public int superPow (int a, int [] b) {
    		W [] pow = new W [1337];
    		int index = 1, value = 1, count = 1;
    		while (pow[index] == null) {
    			int v = (int) (((long)value * (long)a) % 1337);
    			pow[index] = new W(v, count);
    			count++;
    			index = value = pow[index].value;
    		}
    		
    		BigInteger bigB = convertToBigInteger(b);
    		if (bigB.compareTo(new BigInteger(String.valueOf(pow[index].count))) > 0) {
    			bigB = bigB.subtract(new BigInteger(String.valueOf(pow[index].count)));
    			int oneCycle = count - pow[index].count;
    			bigB = bigB.mod(new BigInteger(String.valueOf(oneCycle)));
    		} else {
    			index = 1;
    		}
    		while (bigB.compareTo(BigInteger.ZERO) > 0) {
    			index = pow[index].value;
    			bigB = bigB.subtract(BigInteger.ONE);
    		}
    		return pow[index].value;
    	}
    	
    	private BigInteger convertToBigInteger(int [] b) {
    		StringBuilder sb = new StringBuilder();
    		for (int i = 0; i < b.length; i++) {
    			sb.append(b[i]);
    		}
    		return new BigInteger(sb.toString());
    	}
    	
    	class W {
    		int value, count;
    
    		W(int v, int c) {
    			value = v;
    			count = c;
    		}
    		
    		@Override
    		public String toString() {
    			return "[" + value + "," + count + "]";
    		}
    	}
    }
    

Log in to reply
 

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