Sum of alternating sign Squares of first N natural numbers
Given a number N, the task is to find the sum of alternating sign squares of first N natural numbers, i.e.,
12 – 22 + 32 – 42 + 52 – 62 + ….
Examples:
Input: N = 2 Output: 5 Explanation: Required sum = 12 - 22 = -1 Input: N = 8 Output: 36 Explanation: Required sum = 12 - 22 + 32 - 42 + 52 - 62 + 72 - 82 = 36
Naive approach: O(N)
The Naive or Brute force approach to solve this problem states to find the square of each number from 1 to N and add them with alternating sign in order to get the required sum.
- For each number in 1 to N, find its square
- Add these squares with alternating sign
- This would give the required sum.
Below is the implementation of the above approach:
C++
// C++ program to find Sum of alternating// sign Squares of first N natural numbers#include <iostream>using namespace std;// Function to calculate// the alternating sign sumint summation(int n){ // Variable to store the sum int sum = 0; // Loop to iterate each number // from 1 to N for (int i = 1; i <= n; i++) { // The alternating sign is put // by checking if the number // is even or odd if (i % 2 == 1) // Add the square with the sign sum += (i * i); else // Add the square with the sign sum -= (i * i); } return sum;}// Driver codeint main(){ int N = 2; cout << summation(N); return 0;} |
Java
// Java program to find Sum of alternating// sign Squares of first N natural numbersclass GFG{ // Function to calculate // the alternating sign sum static int summation(int n) { // Variable to store the sum int sum = 0; // Loop to iterate each number // from 1 to N for (int i = 1; i <= n; i++) { // The alternating sign is put // by checking if the number // is even or odd if (i % 2 == 1) // Add the square with the sign sum += (i * i); else // Add the square with the sign sum -= (i * i); } return sum; } // Driver code public static void main (String[] args) { int N = 2; System.out.println(summation(N)); }}// This code is contributed by AnkitRai01 |
Python3
# Python3 program to find Sum of alternating # sign Squares of first N natural numbers # Function to calculate # the alternating sign sum def summation(n) : # Variable to store the sum sum = 0; # Loop to iterate each number # from 1 to N for i in range(1, n + 1) : # The alternating sign is put # by checking if the number # is even or odd if (i % 2 == 1) : # Add the square with the sign sum += (i * i); else : # Add the square with the sign sum -= (i * i); return sum; # Driver code if __name__ == "__main__" : N = 2; print(summation(N)); # This code is contributed by AnkitRai01 |
C#
// C# program to find Sum of alternating// sign Squares of first N natural numbersusing System;class GFG{ // Function to calculate // the alternating sign sum static int summation(int n) { // Variable to store the sum int sum = 0; // Loop to iterate each number // from 1 to N for (int i = 1; i <= n; i++) { // The alternating sign is put // by checking if the number // is even or odd if (i % 2 == 1) // Add the square with the sign sum += (i * i); else // Add the square with the sign sum -= (i * i); } return sum; } // Driver code public static void Main() { int N = 2; Console.WriteLine(summation(N)); }}// This code is contributed by AnkitRai01 |
Javascript
<script>// JavaScript program to find Sum of alternating // sign Squares of first N natural numbers // Function to calculate // the alternating sign sum function summation(n) { // Variable to store the sum let sum = 0; // Loop to iterate each number // from 1 to N for (let i = 1; i <= n; i++) { // The alternating sign is put // by checking if the number // is even or odd if (i % 2 == 1) // Add the square with the sign sum += (i * i); else // Add the square with the sign sum -= (i * i); } return sum; } // Driver code let N = 2; document.write(summation(N)); // This code is contributed by Surbhi Tyagi</script> |
Output:
-3
Efficient Approach: O(1)
There exists a formula for finding the sum of squares of first n numbers with alternating signs:
![\[\LARGE 1^{2}-2^{2}+3^{2}-4^{2}+... = (-1)^{n+1} \text{ } \frac{n(n+1)}{2}\]](https://cdn.zambiatek.com/static/gallery/images/logo.png "Rendered by QuickLaTeX.com"){kind=logo}
How does this work?
We can prove this formula using induction. We can easily see that the formula is true for n = 1 and n = 2 as sums are 1 and -3 respectively. Let it be true for n = k-1. So sum of k-1 numbers is (-1)k(k - 1) * k / 2 In the following steps, we show that it is true for k assuming that it is true for k-1. Sum of k numbers =(-1)k (Sum of k-1 numbers + k2) =(-1)k+1 ((k - 1) * k / 2 + k2) =(-1)k+1 (k * (k + 1) / 2), which is true.
Hence inorder to find the sum of alternating sign squares of first N natural numbers, simply compute the formula and print the result.
C++
// C++ program to find Sum of alternating// sign Squares of first N natural numbers#include <iostream>using namespace std;// Function to calculate// the alternating sign sumint summation(int n){ // Variable to store the absolute sum int abs_sum = n * (n + 1) / 2; // Variable to store the sign int sign = n + 1 % 2 == 0 ? 1 : -1; // Variable to store the resultant sum int result_sum = sign * abs_sum; return result_sum;}// Driver codeint main(){ int N = 2; cout << summation(N); return 0;} |
Java
// Java program to find Sum of alternating// sign Squares of first N natural numbersclass GFG { // Function to calculate // the alternating sign sum static int summation(int n) { // Variable to store the absolute sum int abs_sum = n * (n + 1) / 2; // Variable to store the sign int sign = n + 1 % 2 == 0 ? 1 : -1; // Variable to store the resultant sum int result_sum = sign * abs_sum; return result_sum; } // Driver code public static void main (String[] args) { int N = 2; System.out.println(summation(N)); }}// This code is contributed by AnkitRai01 |
Python3
# Python3 program to find Sum of alternating # sign Squares of first N natural numbers # Function to calculate # the alternating sign sum def summation(n) : # Variable to store the absolute sum abs_sum = n * (n + 1) // 2; # Variable to store the sign sign = 1 if ((n + 1) % 2 == 0 ) else -1; # Variable to store the resultant sum result_sum = sign * abs_sum; return result_sum; # Driver code if __name__ == "__main__" : N = 2; print(summation(N)); # This code is contributed by AnkitRai01 |
C#
// C# program to find Sum of alternating// sign Squares of first N natural numbersusing System;public class GFG { // Function to calculate // the alternating sign sum static int summation(int n) { // Variable to store the absolute sum int abs_sum = (int)(n * (n + 1) / 2); // Variable to store the sign int sign = n + 1 % 2 == 0 ? 1 : -1; // Variable to store the resultant sum int result_sum = sign * abs_sum; return result_sum; } // Driver code public static void Main() { int N = 2; Console.WriteLine(summation(N)); }}// This code is contributed by AnkitRai01 |
Javascript
<script>// Javascript program to find Sum of alternating// sign Squares of first N natural numbers// Function to calculate// the alternating sign sumfunction summation(n){ // Variable to store the absolute sum var abs_sum = n * (n + 1) / 2; // Variable to store the sign var sign = n + 1 % 2 == 0 ? 1 : -1; // Variable to store the resultant sum var result_sum = sign * abs_sum; return result_sum;}// Driver codevar N = 2;document.write(summation(N));// This code is contributed by rutvik_56.</script> |
Output:
-3
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 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
