Summation of floor of harmonic progression
Given an integer N, the task is to find the summation of the harmonic series .
Examples:
Input: N = 5
Output: 10
floor(3/1) + floor(3/2) + floor(3/3) = 3 + 1 + 1 = 5
Input: N = 20
Output: 66
Naive approach: Run a loop from 1 to N and find the summation of the floor values of N / i. Time complexity of this approach will be O(n).
Efficient approach: Use the following formula to calculate the summation of the series:
Now, the loop needs to be run from 1 to sqrt(N) and the time complexity gets reduced to O(sqrt(N))
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the summation of // the given harmonic series long long int getSum( int n) { // To store the summation long long int sum = 0; // Floor of sqrt(n) int k = sqrt (n); // Summation of floor(n / i) for ( int i = 1; i <= k; i++) { sum += floor (n / i); } // From the formula sum *= 2; sum -= pow (k, 2); return sum; } // Driver code int main() { int n = 5; cout << getSum(n); return 0; } |
Java
// Java implementation of the approach class GFG { // Function to return the summation of // the given harmonic series static long getSum( int n) { // To store the summation long sum = 0 ; // Floor of sqrt(n) int k = ( int )Math.sqrt(n); // Summation of floor(n / i) for ( int i = 1 ; i <= k; i++) { sum += Math.floor(n / i); } // From the formula sum *= 2 ; sum -= Math.pow(k, 2 ); return sum; } // Driver code public static void main (String[] args) { int n = 5 ; System.out.println(getSum(n)); } } // This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of the approach from math import floor, sqrt, ceil # Function to return the summation of # the given harmonic series def getSum(n): # To store the summation summ = 0 # Floor of sqrt(n) k = (n) * * (. 5 ) # Summation of floor(n / i) for i in range ( 1 , floor(k) + 1 ): summ + = floor(n / i) # From the formula summ * = 2 summ - = pow (floor(k), 2 ) return summ # Driver code n = 5 print (getSum(n)) # This code is contributed by Mohit Kumar |
C#
// C# implementation of the approach using System; class GFG { // Function to return the summation of // the given harmonic series static double getSum( int n) { // To store the summation double sum = 0; // Floor of sqrt(n) int k = ( int )Math.Sqrt(n); // Summation of floor(n / i) for ( int i = 1; i <= k; i++) { sum += Math.Floor(( double )n / i); } // From the formula sum *= 2; sum -= Math.Pow(k, 2); return sum; } // Driver code public static void Main (String[] args) { int n = 5; Console.WriteLine(getSum(n)); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // Javascript implementation of the approach // Function to return the summation of // the given harmonic series function getSum(n) { // To store the summation let sum = 0; // Floor of sqrt(n) let k = parseInt(Math.sqrt(n)); // Summation of floor(n / i) for (let i = 1; i <= k; i++) { sum += Math.floor(n / i); } // From the formula sum *= 2; sum -= Math.pow(k, 2); return sum; } // Driver code let n = 5; document.write(getSum(n)); </script> |
Output:
10
Time Complexity: O(sqrt(n)), since the for loop runs for sqrt(n) times.
Auxiliary Space: O(1), since no extra space has been taken.
Contact Us