Given an integer array A of size N. Find the sum of GCD (Greatest Common Divisor) of all elements with their frequency (In JAVA)

Question

Problem Statement Given an integer array A of size N. Find the sum of GCD (Greatest Common Divisor) of all elements with their frequency. Input First line contains an integers N. Next line contains N space separated integers denoting elements of array.

Constraints 1 <= N <= 1000 0 <= Ai<= 10^5 Output Print the sum of GCD of all elements with their frequency. Example Sample Input 1: 3 1 2 3

Output 3

Explanation: gcd(1, 1) + gcd(2, 1) + gcd(3, 1) = 1+1+1 = 3

Sample Input 2: 6 3 6 6 9 3 3

Output 14

Explanation gcd(3, 3) + gcd(6, 2) + gcd(6, 2) + gcd(9, 1) + gcd(3, 3) + gcd(3, 3)= 3+2+2+1+3+3= 14

Answer 1

import java.io.*; // for handling input/output
import java.util.*; // contains Collections framework
class Main {
  public static void main (String[] args) {
    Scanner s = new Scanner(System.in);
    int N = s.nextInt();
    int [] a= new int[N];
    HashMap<Integer,Integer> map = new HashMap<>();

    for (int i=0;i<N;i++) {
      a[i]=s.nextInt();
      map.put(a[i],map.getOrDefault(a[i],0)+1);
    }
    long sum=0;
    for (int i=0;i<N;i++) {
      sum += gcd(a[i],map.get(a[i]));
    }
    System.out.println(sum);
  }
    
  public static int gcd(int a, int b) {
    if (b == 0)
      return a;
    return gcd(b,a%b);
  }
}