Perfect Squares - Amazon Top Interview Questions

                        Solution in C++ :

int solve(int n) {
    int m = 1;
    while (n % 2 == 0) {
        if (n % 4 == 0) {
            n /= 4;
        } else {
            n /= 2;
            m *= 2;
        }
    }
    // now n is odd.
    bool check_4p3 = false;

    // prime factorize with O(sqrt(n))
    // you can reduce time by any other prime factorize method.
    for (int i = 3; i <= n / i; i += 2) {
        if (n % i == 0) {
            int state = 0;
            while (n % i == 0) {
                n /= i;
                state ^= 1;
            }
            if (state) {
                m *= i;
                if (i % 4 == 3) {
                    check_4p3 = true;
                }
            }
        }
    }
    if (n > 1) {
        m *= n;
        if (n % 4 == 3) check_4p3 = true;
    }
    // now original n = m * (some square number)
    // case 1 : n is already square number.
    if (m == 1) return 1;
    // case 2 : there is no prime factor s.t. p%4 == 3
    if (!check_4p3) return 2;
    // case 3 : m % 8 is not 7. I don't know why!
    if (m % 8 != 7) return 3;
    // case 4 : else. by lagrange four square theorem
    return 4;
}
                    

                        Solution in Java :

import java.lang.Math;

class Solution {
    public int solve(int n) {
        if (isSquare(n)) {
            return 1;
        }
        for (int i = (int) Math.floor(Math.sqrt(n)); (int) Math.pow(i, 2) >= n / 2; i--) {
            if (isSquare(n - (int) Math.pow(i, 2))) {
                return 2;
            }
        }
        // Legendre's three-square theorem
        return isLegendres(n) ? 4 : 3;
    }

    private boolean isSquare(int n) {
        double root = Math.sqrt(n);
        return root == Math.floor(root);
    }
    private boolean isLegendres(int n) {
        for (int a = 1; a <= n - 7; a *= 4) {
            if (n % a == 0 && (((n / a) - 7) % 8 == 0)) {
                return true;
            }
        }
        return false;
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, n):
        squares = []
        for i in range(1, int(n ** 0.5) + 1):
            squares.append(i ** 2)

        squares = squares[::-1]  # start from the largest one would reduce the time
        q = deque([0])  # cur value
        visited = set()
        step = 0
        while q:
            for _ in range(len(q)):
                node = q.popleft()
                if node == n:
                    return step

                if node > n:
                    continue

                if node in visited:
                    continue
                visited.add(node)

                for s in squares:
                    q.append(node + s)

            step += 1