Answer to Question #300581 in Java | JSP | JSF for Akash Srivastava

Question

back

GCD - Post Class - GCD of LCM! (Contest)by Akash Srivastava

Run

Save and Run Hidden Test Cases

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.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) {
        int[] array = {2, 42, 15, 18, 234, 9, 65, 2, 6};
        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);
        }

    }
}