O(sqrt(n/2)) Applying Fermat's theorm with Brahmagupta–Fibonacci identity


  • 8
    Q

    First I check if number if perfect square, next I check if number fits Legendre's condition for 4 squares 4^a(8b+7) .
    I check if number is prime and is prime I check that n%4==1. See https://en.wikipedia.org/wiki/Fermat%27s_theorem_on_sums_of_two_squares
    If number is not a prime I check if the numbers it's composed of numbers that match Fermat's theorem.
    By Brahmagupta–Fibonacci identity
    https://en.wikipedia.org/wiki/Brahmagupta%E2%80%93Fibonacci_identity
    if all factors(or subfactors) are prime and match condtion n%4==1 I am guaranteed that my number is sum of 2 squares. Otherwise it's sum of 3 squares by Legendre's theorem .

    public class Solution {
        public int numSquares(int n) {
            if (Math.pow((int)Math.sqrt(n), 2) == n){
        	    return 1;
        	}
            while (n%4 == 0){
                n = n/4;
        	}
            if (n%8 == 7){
                return 4;
            }
            if (n%2 == 0){
                n = n/2; //OK to divide by 2. If N/2 has is sum of 2 squares so will be N.
            }
            if (isMod41PrimeOrSubP(n)){
                return 2;
            }
        	return 3;
        }
        private boolean isMod41PrimeOrSubP(int num) {
            if (num%4 != 1){
                return false;
            }
            for (int i=3; i*i<num; i=i+2){
                if (num%i == 0) {
                    if (num%(i*i) == 0){
             	        return isMod41PrimeOrSubP(num/(i*i));
                    } 
                    return isMod41PrimeOrSubP(i)&&isMod41PrimeOrSubP(num/i);
                }
            }
            return true;
        }
    }
    

  • 1
    Q

    Improved version

    public int numSquares(int n) {
            if (Math.pow((int)Math.sqrt(n), 2) == n){
                return 1;
            }
            while (n%4 == 0){
                n = n/4;
            }
            if (n%8 == 7){
                return 4;
            }
            if (n%2 == 0){
                n = n/2;
            }
            if (n%4 == 3){
                return 3;
            }
            return helper(n, 3);
        }
        private int helper(int num, int start) {
            int sq = (int)Math.sqrt(num);
            for (int i=start; i<sq; i=i+4){
                if (num%i == 0) {
                    int isq = i * i;
                    if (num%isq == 0){
                        return helper(num/isq, i);
                    }
                    return 3;
                }
            }
            return 2;
        }

  • 0

    You only have one recursive call now. Do you still prefer the helper and recursion? I think a loop inside numSquares is a bit simpler:

    public int numSquares(int n) {
        ...
        ...
        int sq = (int)Math.sqrt(n);
        for (int i=3; i<sq; i=i+4){
            if (n%i == 0) {
                int isq = i * i;
                while (n%isq == 0)
                    n /= isq;
                if (n%i == 0)
                    return 3;
                sq = (int)Math.sqrt(n);
            }
        }
        return 2;
    }
    

    Updating sq as follows also seems to work, though I didn't fully think it through and I don't think it's an advantage:

    public int numSquares(int n) {
        ...
        ...
        int sq = (int)Math.sqrt(n);
        for (int i=3; i<sq; i=i+4){
            if (n%i == 0) {
                int isq = i * i;
                while (n%isq == 0) {
                    n /= isq;
                    sq /= i;
                }
                if (n%i == 0)
                    return 3;
            }
        }
        return 2;
    }

  • 0
    Q

    I did try while loop. I know it sounds a little strange but recursive solution ended up being a little faster.


Log in to reply
 

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