Sum Of LCM

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
20 upvotes
Asked in companies
GrofersMr. CooperGoogle inc

Problem statement

You are given an integer ‘N’ , calculate and print the sum of :

LCM(1,N) + LCM(2,N) + .. + LCM(N,N)

where LCM(i,n) denotes the Least Common Multiple of the integers ‘i’ and ‘N’.

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains a single integer T representing the number of test cases.      

The first line of each test case contains a single integer ‘N’ representing the number of times we have to take LCM sum.
Output Format : 
For each test case, return the required sum in a new line
Note : 
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 50
1 <= N <= 10^4
Where ‘T’ is the number of test cases, and ‘N’ is the given integer

Time Limit:1sec
Sample Input:
2
5
2
Sample Output:
55
4
Explanation Of Sample Input 1
For test case 1 : 

LCM(1,5) + LCM(2,5) + LCM(3,5) + LCM(4,5) + LCM(5,5) = 5 + 10 + 15 + 20 + 5 = 55      

For test case 2 : 
LCM(1,2) + LCM(2,2) = 2 + 2 = 4
Sample Input 2:
2
1
3
Sample Output 2:
1
12
Hint

 can you write a code to find the LCM of two numbers ?

Approaches (2)
Brute force approach

 

Using the mathematical formula, A*B = LCM(A,B) * GCD(A,B) where ‘A’ and ‘B’ are the two integers, and GCD(A,B) denotes the Greatest common divisor of ‘A’ and ‘B’.

For example, suppose 

 

A = 20 and B = 30

Factors of A = {1,2,4,5,10,20}

Factors of B = {1,2,3,5,6,10,15,30}

 

The greatest common factor is 10, hence GCD(20,30) = 10.

 

So LCM(A,B) = A*B / GCD(A,B)

 

All we need to find is a GCD of two numbers.

 

We can find it in 2 different ways

  • Find all the factors of both numbers, and search for the greatest common, or
  • Use Euclidean algorithm to find GDC(A,B)

Euclidean algorithm for finding GCD(A,B) is as follows : 

 

  • GCD(A , B)     --->    GCD(B , A%B)


 

A = 30, B = 20

GCD(30,20) ---> GCD(20,30%20) ---> GCD(20,10)

GCD(20,10) ---> GCD(10,20%10)  ---> GCD(10,10)

GCD(10,10) ---> GCD(10,10%10) ---> GCD(10,0)

As soon as one integer becomes 0, we will stop and GCD = 10.

Time Complexity

O(N*logN) 

where ‘N’ is the number of times we have to find LCM.


 

We are finding GCD for each number, and for finding GCD the complexity is LogN because we repeatedly divide an integer until it becomes zero, maximum operation will be the number of digits in that integer, which are roughly logN.


 

Space Complexity

O(1) since no extra space has been used.


 

Code Solution
(100% EXP penalty)
Sum Of LCM
Full screen
Console