Given an integer N and the sum of its divisors. The task is to find the sum of the inverse of the divisors of N.
Examples:
Input: N = 6, Sum = 12
Output: 2.00
Divisors of N are {1, 2, 3, 6}
Sum of inverse of divisors is equal to (1/1 + 1/2 + 1/3 + 1/6) = 2.0
Input: N = 9, Sum = 13
Output: 1.44
Naive Approach: Calculate all the divisors of the given integer N. Then calculate the sum of the inverse of the calculated divisors. This approach would give TLE when the value of N is large.
Time Complexity: O(sqrt(N))
Efficient Approach: Let the number N has K divisors say d1, d2, …, dK. It is given that d1 + d2 + … + dK = Sum
The task is to calculate (1 / d1) + (1 / d2) + … + (1 / dK).
Multiply and divide the above equation by N. The equation becomes [(N / d1) + (N / d2) + … + (N / dK)] / N
Now it is easy to see that N / di would represent another divisor of N for all 1 ? i ? K. The numerator is equal to the sum of the divisors. Hence, sum of inverse of the divisors is equal to Sum / N.
Below is the implementation of the above approach:
C++
// C++ implementation of above approach#include <bits/stdc++.h>using namespace std;// Function to return the// sum of inverse of divisorsdouble SumofInverseDivisors(int N, int Sum){ // Calculating the answer double ans = (double)(Sum)*1.0 / (double)(N); // Return the answer return ans;}// Driver codeint main(){ int N = 9; int Sum = 13; // Function call cout << setprecision(2) << fixed << SumofInverseDivisors(N, Sum); return 0;} |
Java
// Java implementation of above approachimport java.math.*;import java.io.*;class GFG { // Function to return the// sum of inverse of divisorsstatic double SumofInverseDivisors(int N, int Sum){ // Calculating the answer double ans = (double)(Sum)*1.0 / (double)(N); // Return the answer return ans;}// Driver codepublic static void main (String[] args) { int N = 9; int Sum = 13; // Function call System.out.println (SumofInverseDivisors(N, Sum));}}// This code is contributed by jit_t. |
Python
# Python implementation of above approach# Function to return the# sum of inverse of divisorsdef SumofInverseDivisors( N, Sum): # Calculating the answer ans = float(Sum)*1.0 /float(N); # Return the answer return round(ans,2);# Driver codeif __name__ == "__main__" : N = 9; Sum = 13; print(SumofInverseDivisors(N, Sum))# This code is contributed by CrazyPro |
C#
// C# implementation of above approachusing System;class GFG{ // Function to return the// sum of inverse of divisorsstatic double SumofInverseDivisors(int N, int Sum){ // Calculating the answer double ans = (double)(Sum)*1.0 / (double)(N); // Return the answer return ans;}// Driver codestatic public void Main (){ int N = 9; int Sum = 13; // Function call Console.Write(SumofInverseDivisors(N, Sum));}}// This code is contributed by ajit |
Javascript
<script>// JavaScript implementation of above approach// Function to return the// sum of inverse of divisorsfunction SumofInverseDivisors(N, Sum){ // Calculating the answer let ans = (Sum)*1.0 / (N); // Return the answer return ans;}// Driver code let N = 9; let Sum = 13; // Function call document.write(SumofInverseDivisors(N, Sum).toFixed(2));// This code is contributed by Surbhi Tyagi.</script> |
1.44
Time Complexity: O(1)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
