DSA

1 flashcards · Computer Science · by VIVEK RAI

1. Given an integer n, return the least number of perfect square numbers that sum to n.

   class Solution { private: int is_square(int n) { int sqrt_n = (int)(sqrt(n)); return (sqrt_n*sqrt_n == n); } public: // Based on Lagrange's Four Square theorem, there // are only 4 possible results: 1, 2, 3, 4. int numSquares(int n) { // If n is a perfect square, return 1. if(is_square(n)) { return 1; } // The result is 4 if and only if n can be written in the // form of 4^k*(8*m + 7). Please refer to // Legendre's three-square theorem. while ((n & 3) == 0) // n%4 == 0 { n >>= 2; } if ((n & 7)…