For given any unsigned int n find the final value of ?(i*j) where (1<=i<=n) and (i <= j <= n).
Examples:
Input : n = 3 Output : 25 We get the sum as following. Note that first term i varies from 1 to 3 and second term values from value of first term to n. 1*1 + 1*2 + 1*3 + 2*2 + 2*3 + 3*3 = 25 Input : 5 Output : 140
Method 1 (Simple) We run two loops and compute the required sum.
C++
// Simple CPP program to find sum // of given series.#include <bits/stdc++.h>using namespace std;long long int findSum(int n){ long long int sum = 0; for (int i=1; i<=n; i++) for (int j=i; j<=n; j++) sum = sum + i*j; return sum;}int main(){ int n = 5; cout << findSum(n); return 0;} |
Java
// Simple Java program to find sum // of given series.class GFG { static int findSum(int n) { int sum = 0; for (int i=1; i<=n; i++) for (int j=i; j<=n; j++) sum = sum + i*j; return sum; } // Driver code public static void main(String[] args) { int n = 5; System.out.println(findSum(n)); }}// This code is contributed by Smitha Dinesh Semwal. |
Python3
# Simple Python3 program to # find sum of given series.def findSum(n) : sm = 0 for i in range(1, n + 1) : for j in range(i, n + 1) : sm = sm + i * j return sm # Driver Coden = 5print(findSum(n))# This code is contributed by Nikita Tiwari. |
C#
// Simple C# program to find sum // of given series.class GFG { static int findSum(int n) { int sum = 0; for (int i=1; i<=n; i++) for (int j=i; j<=n; j++) sum = sum + i*j; return sum; } // Driver code public static void Main() { int n = 5; System.Console.WriteLine(findSum(n)); }}// This code is contributed by mits. |
PHP
<?php// Simple PHP program to find sum // of given series.function findSum($n){ $sum = 0; for ($i = 1; $i <= $n; $i++) for ($j = $i; $j <= $n; $j++) $sum = $sum + $i * $j; return $sum;}// Driver Code$n = 5;echo findSum($n);// This code is contributed by mits?> |
Javascript
<script>// Simple JavaScript program to find sum // of given series. function findSum(n) { let sum = 0; for (let i=1; i<=n; i++) for (let j=i; j<=n; j++) sum = sum + i*j; return sum; }// Driver Code let n = 5; document.write(findSum(n));</script> |
Output:
140
Time Complexity: O(n^2).
Method 2 (Better)
We can observe following in the given problem.
1 is multiplied with all numbers from 1 to n.
2 is multiplied with all numbers from 2 to n.
………………………………………
………………………………………
i is multiplied with all numbers from i to n.
We compute sum of first n natural numbers which is our first term. For remaining terms, we multiply i with sum of numbers from i to n. We keep track of this sum by subtracting i from initial sum in every iteration.
C++
// Efficient CPP program to find sum // of given series.#include <bits/stdc++.h>using namespace std;long long int findSum(int n){ long long int multiTerms = n * (n + 1) / 2; // Sum of multiples of 1 is 1 * (1 + 2 + ..) long long int sum = multiTerms; // Adding sum of multiples of numbers other // than 1, starting from 2. for (int i=2; i<=n; i++) { // Subtract previous number // from current multiple. multiTerms = multiTerms - (i - 1); // For example, for 2, we get sum // as (2 + 3 + 4 + ....) * 2 sum = sum + multiTerms * i; } return sum;}// Driver codeint main(){ int n = 5; cout << findSum(n); return 0;} |
Java
// Efficient Java program to find sum // of given series.class GFG { static int findSum(int n) { int multiTerms = n * (n + 1) / 2; // Sum of multiples of 1 is 1 * (1 + 2 + ..) int sum = multiTerms; // Adding sum of multiples of numbers other // than 1, starting from 2. for (int i = 2; i <= n; i++) { // Subtract previous number // from current multiple. multiTerms = multiTerms - (i - 1); // For example, for 2, we get sum // as (2 + 3 + 4 + ....) * 2 sum = sum + multiTerms*i; } return sum; } // Driver code public static void main(String[] args) { int n = 5; System.out.println(findSum(n)); }}// This code is contributed by Smitha Dinesh Semwal. |
Python3
# Efficient Python3 program # to find sum of given series.def findSum(n) : multiTerms = n * (n + 1) // 2 # Sum of multiples of 1 is 1 * (1 + 2 + ..) sm = multiTerms # Adding sum of multiples of numbers # other than 1, starting from 2. for i in range(2, n+1) : # Subtract previous number # from current multiple. multiTerms = multiTerms - (i - 1) # For example, for 2, we get sum # as (2 + 3 + 4 + ....) * 2 sm = sm + multiTerms * i return sm # Driver coden = 5print(findSum(n))# This code is contributed by Nikita Tiwari. |
C#
// C# program to find sum // of given series.using System;class GFG { static int findSum(int n) { int multiTerms = n * (n + 1) / 2; // Sum of multiples of 1 is 1 * (1 + 2 + ..) int sum = multiTerms; // Adding sum of multiples of numbers other // than 1, starting from 2. for (int i = 2; i <= n; i++) { // Subtract previous number // from current multiple. multiTerms = multiTerms - (i - 1); // For example, for 2, we get sum // as (2 + 3 + 4 + ....) * 2 sum = sum + multiTerms*i; } return sum; } // Driver code public static void Main() { int n = 5; Console.WriteLine(findSum(n)); }}// This code is contributed by Mukul Singh. |
PHP
<?php// Efficient PHP program to find sum // of given series.function findSum($n){ $multiTerms = (int)($n * ($n + 1) / 2);// Sum of multiples of 1 is 1 * (1 + 2 + ..)$sum = $multiTerms;// Adding sum of multiples of numbers other// than 1, starting from 2.for ($i=2; $i<=$n; $i++){ // Subtract previous number // from current multiple. $multiTerms = $multiTerms - ($i - 1); // For example, for 2, we get sum // as (2 + 3 + 4 + ....) * 2 $sum = $sum + $multiTerms * $i;}return $sum;}// Driver code $n = 5; echo findSum($n);//This code is contributed by mits?> |
Javascript
<script> // Javascript program to find // sum of given series. function findSum(n) { let multiTerms = n * (n + 1) / 2; // Sum of multiples of 1 is 1 * (1 + 2 + ..) let sum = multiTerms; // Adding sum of multiples // of numbers other // than 1, starting from 2. for (let i = 2; i <= n; i++) { // Subtract previous number // from current multiple. multiTerms = multiTerms - (i - 1); // For example, for 2, we get sum // as (2 + 3 + 4 + ....) * 2 sum = sum + multiTerms*i; } return sum; } let n = 5; document.write(findSum(n)); </script> |
Output:
140
Time Complexity: O(n).
Method 3 (Efficient)
The whole calculation can be done in the O(1) time as there is a closed-form expression for the sum. Let i and j run from 1 through n. We want to compute S = sum(i*j) overall i and j such that i <= j otherwise we would have duplicates such as 2*3 + …+3*2; on the other hand, having i = j is OK which gives us 2*2 + … This is all by the problem specification. (Sorry if my notation is bizarre.)
Now, there are two kinds of terms in the sum S: those with i = j (squares, denoted S1) and those with i j always, but the value is the same, by symmetry: 2 * S2 = (sum i)^2 – sum (i^2) . Note that 2*S2 = S3 – S1 as the latter sum is just S1; the former sum (denoted S3) is new here, but there is a closed-form solution for it too. We can now eliminate the mixed term completely: S = S1 + S2 = (S1 + S3) / 2.
Since sum(i) = n*(n+1)/2, we get S3 = n*n*(n+1)*(n+1)/4 ; likewise for the sum of squares: S1 = n*(2*n+1)*(n+1)/6. The final expression simplifies to:
S = n*(n+1)*(n+2)*(3*n+1)/24 . (As an exercise, you may want to prove that the numerator is indeed divisible by 24.)
C++
// Efficient CPP program to find sum // of given series.#include <bits/stdc++.h>using namespace std;long long int findSum(int n){ return n*(n+1)*(n+2)*(3*n+1)/24;}// Driver codeint main(){ int n = 5; cout << findSum(n); return 0;} |
Java
// Efficient Java program to find sum // of given series.class GFG { static int findSum(int n) { return n * (n + 1) * (n + 2) * (3 * n + 1) / 24; } // Driver code public static void main(String[] args) { int n = 5; System.out.println(findSum(n)); }}// This code is contributed by Smitha Dinesh Semwal. |
Python3
# Efficient Python3 program to find # sum of given series.def findSum(n): return n * (n + 1) * (n + 2) * (3 * n + 1) / 24# Driver coden = 5print(int(findSum(n)))# This code is contributed by Smitha Dinesh Semwal. |
C#
// Efficient C# program // to find sum of given // series.using System;class GFG{static int findSum(int n){ return n * (n + 1) * (n + 2) * (3 * n + 1) / 24;}// Driver codestatic public void Main (){ int n = 5; Console.WriteLine(findSum(n));}}// This code is contributed// by ajit. |
PHP
<?php// Efficient PHP // program to find sum // of given series.function findSum($n){ return $n * ($n + 1) * ($n + 2) * (3 * $n + 1) / 24;}// Driver code$n = 5;echo findSum($n);// This code is contributed // by akt_mit?> |
Javascript
<script> // Efficient Javascript program // to find sum of given // series. function findSum(n) { return n * (n + 1) * (n + 2) * (3 * n + 1) / 24; } let n = 5; document.write(findSum(n));</script> |
Output:
140
Time Complexity: O(1).
Thanks to diprey1 for suggesting this efficient solution.
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!
