Given a number N, the task is to find the number of ways of writing N as a sum of 4 squares. Two representations are considered different if their terms are in a different order or if the integer being squared (not just the square) is different.
Examples:
Input : n=1
Output :8
12 + 02 + 02 + 02
02 + 12 + 02 + 02
02 + 02 + 12 + 02
02 + 02 + 02 + 12
Similarly there are 4 other possible permutations by replacing 1 with -1
Hence there are 8 possible ways.Input :n=5
Output :48
Approach:
Jacobi’s four-square theorem states that the number of ways of writing n as a sum of 4 squares is 8 times the sum of divisor of n if n is odd and is 24 times the sum of odd divisor of n if n is even.Find the sum of odd and even divisor of n by running a loop from 1 to sqrt(n) .
C++
// C++ implementation of above approach#include <bits/stdc++.h>using namespace std;// Number of ways of writing n// as a sum of 4 squaresint sum_of_4_squares(int n){ // sum of odd and even factor int i, odd = 0, even = 0; // iterate from 1 to the number for (i = 1; i <= sqrt(n); i++) { // if i is the factor of n if (n % i == 0) { // if factor is even if (i % 2 == 0) even += i; // if factor is odd else odd += i; // n/i is also a factor if ((n / i) != i) { // if factor is even if ((n / i) % 2 == 0) even += (n / i); // if factor is odd else odd += (n / i); } } } // if n is odd if (n % 2 == 1) return 8 * (odd + even); // if n is even else return 24 * (odd);}// Driver codeint main(){ int n = 4; cout << sum_of_4_squares(n); return 0;} |
Java
// Java implementation of above approachimport java.io.*;class GFG{ // Number of ways of writing n// as a sum of 4 squaresstatic int sum_of_4_squares(int n){ // sum of odd and even factor int i, odd = 0, even = 0; // iterate from 1 to the number for (i = 1; i <= Math.sqrt(n); i++) { // if i is the factor of n if (n % i == 0) { // if factor is even if (i % 2 == 0) even += i; // if factor is odd else odd += i; // n/i is also a factor if ((n / i) != i) { // if factor is even if ((n / i) % 2 == 0) even += (n / i); // if factor is odd else odd += (n / i); } } } // if n is odd if (n % 2 == 1) return 8 * (odd + even); // if n is even else return 24 * (odd);} // Driver code public static void main (String[] args) { int n = 4; System.out.println (sum_of_4_squares(n)); }}// This code is contributed by tushil. |
Python3
# Python3 implementation of above approach# Number of ways of writing n# as a sum of 4 squaresdef sum_of_4_squares(n): # sum of odd and even factor i, odd, even = 0,0,0 # iterate from 1 to the number for i in range(1,int(n**(.5))+1): # if i is the factor of n if (n % i == 0): # if factor is even if (i % 2 == 0): even += i # if factor is odd else: odd += i # n/i is also a factor if ((n // i) != i): # if factor is even if ((n // i) % 2 == 0): even += (n // i) # if factor is odd else: odd += (n // i) # if n is odd if (n % 2 == 1): return 8 * (odd + even) # if n is even else : return 24 * (odd)# Driver coden = 4print(sum_of_4_squares(n))# This code is contributed by mohit kumar 29 |
C#
// C# implementation of above approachusing System;class GFG{ // Number of ways of writing n// as a sum of 4 squaresstatic int sum_of_4_squares(int n){ // sum of odd and even factor int i, odd = 0, even = 0; // iterate from 1 to the number for (i = 1; i <= Math.Sqrt(n); i++) { // if i is the factor of n if (n % i == 0) { // if factor is even if (i % 2 == 0) even += i; // if factor is odd else odd += i; // n/i is also a factor if ((n / i) != i) { // if factor is even if ((n / i) % 2 == 0) even += (n / i); // if factor is odd else odd += (n / i); } } } // if n is odd if (n % 2 == 1) return 8 * (odd + even); // if n is even else return 24 * (odd);}// Driver codestatic public void Main (){ int n = 4; Console.WriteLine(sum_of_4_squares(n));}}// This code is contributed by ajit. |
Javascript
<script>// Javascript implementation of above approach// Number of ways of writing n// as a sum of 4 squaresfunction sum_of_4_squares(n){ // Sum of odd and even factor var i, odd = 0, even = 0; // Iterate from 1 to the number for(i = 1; i <= Math.sqrt(n); i++) { // If i is the factor of n if (n % i == 0) { // If factor is even if (i % 2 == 0) even += i; // If factor is odd else odd += i; // n/i is also a factor if ((n / i) != i) { // If factor is even if ((n / i) % 2 == 0) even += (n / i); // If factor is odd else odd += (n / i); } } } // If n is odd if (n % 2 == 1) return 8 * (odd + even); // If n is even else return 24 * (odd);}// Driver codevar n = 4;document.write(sum_of_4_squares(n));// This code is contributed by SoumikMondal</script> |
Output:
24
Time Complexity : O(sqrt(N))
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
