GCD Sum

Hard
0/120
Average time to solve is 35m
profile
Contributed by
9 upvotes
Asked in companies
AdobeDunzoQuikr

Problem statement

Consider all numbers from 1 to ‘N’, your task is to find the sum of gcd of all pairs (i, j) such that 1 <= i < j <= N.

For example for N = 3, all pairs are { (1, 2), (1, 3), (2, 3) }.

Note :

Gcd of two numbers (X, Y) is defined as the largest integer that divides both ‘X’ and ‘Y’.
Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line contains an integer 'T' which denotes the number of test cases to be run. The 'T' test cases follow.

The first line of each test case contains an integer ‘N’ representing the given integer.

Output Format :

For each test case, print an integer representing the sum of gcd of all pairs of numbers from 1 to ‘N’.

The output of each test case will be printed in a separate line.

Note :

You do not need to input or print anything, and it has already been taken care of. Just implement the given function.

Constraints :

1 <= 'T' <= 5
1 <= 'N' <= 5000

Time Limit: 1sec

Sample Input 1 :

2
3
5

Sample Output 1 :

3
11

Explanation Of Sample Input 1 :

Test case 1:
gcd(1, 2) + gcd(1, 3) +  gcd(2, 3) = 1 + 1 + 1 = 3.

Test case 2:
gcd(1, 2) + gcd(1, 3) +  gcd(1, 4) + gcd(1, 5) +
gcd(2, 3) + gcd(2, 4) + gcd(2, 5) +
gcd(3, 4) + gcd(3, 5) +
gcd(4, 5)  = 11.

Sample Input 2 :

1
1

Sample Output 2 :

0

Explanation Of Sample Input 2 :

Test case 1:
As there is no possible Paris, so the gcd sum is 0.
Hint

Try to extract all the pairs and find out their gcd.

Approaches (2)
Brute Approach

For a given ‘N’, we can iterate over all possible pairs and find the resulting sum by adding them.

 

Algorithm:

 

  • Let the given integer be ‘N’.
  • Declare a variable ‘answer’ to store the gcd sum of all pairs.
  • Run a loop from ‘i’ = 1 to ‘N’.
    • Run a loop from ‘j’ = i + 1 to ‘N’
      • Increase ‘answer’ by gcd of ‘i’ and ‘j’, i.e. do ‘answer’ += gcd(i, j).
  • Return ‘answer’
Time Complexity

O((N ^ 2) * log(N)) where ‘N’ is the given integer.

 

As there are total (N * (N - 1) / 2) pairs and we are iterating over each pair that takes O(N ^ 2) time, also for each pair we are calculating gcd which takes O(log(N)) time in the worst case. Hence the overall time complexity is O(N ^ 2) * O (log(N)) = O((N ^ 2) * log(N)).

Space Complexity

O(1)

 

As we are not using any extra space.

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