Answer to Question #302394 in Java | JSP | JSF for Akash srivastava

Question

GCD of LCM! (Contest)

standard input/output: 2s/128000 kB

You are given an array A consisting of N number and an empty set S. For each pair of numbers A[i] and A[j] in the array (i < j), you need to find their LCM and insert the LCM into the set S.

You need to report the GCD of the elements in set S.

Input

The first line of the input contains an integer N.

The second line of the input contains N space separated integers A[1], A[2],. , A[N].

Constraints

2 <= N <= 100000

1 <= A[i] <= 200000

Output

Output a single integer, the GCD of LCM set S.

Answer 1

import java.util.Scanner;
import java.util.HashSet;
import java.util.Set;

public class Main {
    public static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

    public static int lcm(int a, int b) {
        return (a * b) / gcd(a, b);
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[] array = new int[in.nextInt()];
        for (int i = 0; i < array.length; i++) {
            array[i] = in.nextInt();
        }
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < array.length; i++) {
            for (int j = i + 1; j < array.length; j++) {
                set.add(lcm(array[i], array[j]));
            }
        }
        if (set.size() == 1) {
            for (Integer value : set) {
                System.out.println(value);
            }
        } else {
            Integer[] values = new Integer[set.size()];
            set.toArray(values);
            int gcd = gcd(values[0], values[1]);
            for (int i = 2; i < values.length; i++) {
                gcd = gcd(gcd, values[i]);
            }
            System.out.println(gcd);
        }

    }

}