Minimum number of squares whose sum equals to a given number N | Set-3
A number can always be represented as a sum of squares of other numbers. Note that 1 is a square, and we can always break a number as (1*1 + 1*1 + 1*1 + …). Given a number n, find the minimum number of squares that sum to N.
Examples:
Input: N = 13
Output: 2
Explanation:
13 can be expressed as, 13 = 32 + 22. Hence, the output is 2.Input: N = 100
Output: 1
Explanation:
100 can be expressed as 100 = 102. Hence, the output is 1.
Naive Approach: For [O(N*sqrt(N))] approach, please refer to Set 2 of this article.
Efficient Approach: To optimize the naive approach the idea is to use Lagrange’s Four-Square Theorem and Legendre’s Three-Square Theorem. The two theorems are discussed below:
Lagrange’s four-square theorem, also known as Bachet’s conjecture, states that every natural number can be represented as the sum of four integer squares, where each integer is non-negative.
Legendre’s three-square theorem states that a natural number can be represented as the sum of three squares of integers if and only if n is not of the form : n = 4a (8b+7), for non-negative integers a and b.
Therefore, it is proved that the minimum number of squares to represent any number N can only be within the set {1, 2, 3, 4}. Thus, only checking for these 4 possible values, the minimum number of squares to represent any number N can be found. Follow the steps below:
- If N is a perfect square, then the result is 1.
- If N can be expressed as the sum of two squares, then the result is 2.
- If N cannot be expressed in the form of N = 4a (8b+7), where a and b are non-negative integers, then the result is 3 by Legendre’s three-square theorem.
- If all the above conditions are not satisfied, then by Lagrange’s four-square theorem, the result is 4.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function that returns true if N // is a perfect square bool isPerfectSquare( int N) { int floorSqrt = sqrt (N); return (N == floorSqrt * floorSqrt); } // Function that returns true check if // N is sum of three squares bool legendreFunction( int N) { // Factor out the powers of 4 while (N % 4 == 0) N /= 4; // N is NOT of the // form 4^a * (8b + 7) if (N % 8 != 7) return true ; else return false ; } // Function that finds the minimum // number of square whose sum is N int minSquares( int N) { // If N is perfect square if (isPerfectSquare(N)) return 1; // If N is sum of 2 perfect squares for ( int i = 1; i * i < N; i++) { if (isPerfectSquare(N - i * i)) return 2; } // If N is sum of 3 perfect squares if (legendreFunction(N)) return 3; // Otherwise, N is the // sum of 4 perfect squares return 4; } // Driver code int main() { // Given number int N = 123; // Function call cout << minSquares(N); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function that returns true if N // is a perfect square static boolean isPerfectSquare( int N) { int floorSqrt = ( int )Math.sqrt(N); return (N == floorSqrt * floorSqrt); } // Function that returns true check if // N is sum of three squares static boolean legendreFunction( int N) { // Factor out the powers of 4 while (N % 4 == 0 ) N /= 4 ; // N is NOT of the // form 4^a * (8b + 7) if (N % 8 != 7 ) return true ; else return false ; } // Function that finds the minimum // number of square whose sum is N static int minSquares( int N) { // If N is perfect square if (isPerfectSquare(N)) return 1 ; // If N is sum of 2 perfect squares for ( int i = 1 ; i * i < N; i++) { if (isPerfectSquare(N - i * i)) return 2 ; } // If N is sum of 3 perfect squares if (legendreFunction(N)) return 3 ; // Otherwise, N is the // sum of 4 perfect squares return 4 ; } // Driver code public static void main(String[] args) { // Given number int N = 123 ; // Function call System.out.print(minSquares(N)); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approach from math import sqrt, floor, ceil # Function that returns True if N # is a perfect square def isPerfectSquare(N): floorSqrt = floor(sqrt(N)) return (N = = floorSqrt * floorSqrt) # Function that returns True check if # N is sum of three squares def legendreFunction(N): # Factor out the powers of 4 while (N % 4 = = 0 ): N / / = 4 # N is NOT of the # form 4^a * (8b + 7) if (N % 8 ! = 7 ): return True else : return False # Function that finds the minimum # number of square whose sum is N def minSquares(N): # If N is perfect square if (isPerfectSquare(N)): return 1 # If N is sum of 2 perfect squares for i in range (N): if i * i < N: break if (isPerfectSquare(N - i * i)): return 2 # If N is sum of 3 perfect squares if (legendreFunction(N)): return 3 # Otherwise, N is the # sum of 4 perfect squares return 4 # Driver code if __name__ = = '__main__' : # Given number N = 123 # Function call print (minSquares(N)) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approach using System; class GFG{ // Function that returns true if N // is a perfect square static bool isPerfectSquare( int N) { int floorSqrt = ( int )Math.Sqrt(N); return (N == floorSqrt * floorSqrt); } // Function that returns true check // if N is sum of three squares static bool legendreFunction( int N) { // Factor out the powers of 4 while (N % 4 == 0) N /= 4; // N is NOT of the // form 4^a * (8b + 7) if (N % 8 != 7) return true ; else return false ; } // Function that finds the minimum // number of square whose sum is N static int minSquares( int N) { // If N is perfect square if (isPerfectSquare(N)) return 1; // If N is sum of 2 perfect squares for ( int i = 1; i * i < N; i++) { if (isPerfectSquare(N - i * i)) return 2; } // If N is sum of 3 perfect squares if (legendreFunction(N)) return 3; // Otherwise, N is the // sum of 4 perfect squares return 4; } // Driver code public static void Main(String[] args) { // Given number int N = 123; // Function call Console.Write(minSquares(N)); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript program for the above approach // Function that returns true if N // is a perfect square function isPerfectSquare(N) { let floorSqrt = Math.floor(Math.sqrt(N)); return (N == floorSqrt * floorSqrt); } // Function that returns true check if // N is sum of three squares function legendreFunction(N) { // Factor out the powers of 4 while (N % 4 == 0) N = Math.floor(N / 4); // N is NOT of the // form 4^a * (8b + 7) if (N % 8 != 7) return true ; else return false ; } // Function that finds the minimum // number of square whose sum is N function minSquares(N) { // If N is perfect square if (isPerfectSquare(N)) return 1; // If N is sum of 2 perfect squares for (let i = 1; i * i < N; i++) { if (isPerfectSquare(N - i * i)) return 2; } // If N is sum of 3 perfect squares if (legendreFunction(N)) return 3; // Otherwise, N is the // sum of 4 perfect squares return 4; } // Driver Code // Given number let N = 123; // Function call document.write(minSquares(N)); </script> |
3
Time Complexity: O(sqrt(N))
Auxiliary Space: O(1)
Contact Us