Find the LCM of unique elements of an array

Given an integer array arr[] (0 < arr[i] < 10⁶) of size N, the task is to find the LCM of unique elements of the array. If there is no unique element print 0.

The unique elements of an array are the elements that appear exactly once in the array.

Examples :

Input : arr[ ] = { 1, 2, 1, 3, 3, 4 }
Output : 4
Explanation : Unique elements are 2 and 4.

LCM of 2 and 4 is 4.
Input : arr[ ] = { 1, 1, 2, 2, 3, 3 }
Output : 0
Input : arr[ ] = { 1, 1, 2 }
Output : 2

Naive Approach :

The simple idea is to traverse the array and check for each element that is unique. Add that element into another array and at last find LCM of all elements of the created array and print the result.

Time Complexity : O(N^2 * log a), where a is the largest number of the array

Auxiliary Space : O(N)

Efficient Approach :

The idea is to use Hashing. Follow the steps below:

Traverse the array arr[] and store the frequency of each element in a Map.
Now traverse the map and check if the count of any element is unique.
Find LCM of all those unique elements.
Print the result.

Implementation :

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;

// Function of find GCD
long long int findGCD(long long int a, long long int b)
{
    if (b == 0)
        return a;
    return findGCD(b, a % b);
}

// Function of find LCM
long long int findLCM(long long int a, long long int b)
{
    return (a * b) / findGCD(a, b);
}

// Function to find LCM of every number
// in the array whose frequency is 1
long long int uniqueElement(int arr[], int N)
{

    // Freq map will store the frequency
    // of each number of the array
    unordered_map<int, int> freq;

    // Store the frequency of each
    // element of the array
    for (int i = 0; i < N; i++) {
        freq[arr[i]]++;
    }

    long long int lcm = 0;
    int flag = 0;

    // Traverse the freq map
    for (auto i : freq) {
        if (i.second == 1) {
            if (flag == 0) {
                flag = 1;
                lcm = i.first;
            }
            else {
                lcm = findLCM(lcm, i.first);
            }
        }
    }

    return lcm;
}

// Driver Code
int main()
{
    int arr[] = { 1, 2, 1, 3, 3, 4 };

    // Size of array
    int N = sizeof(arr) / sizeof(arr[0]);

    // Function call
    cout << uniqueElement(arr, N);

    return 0;
}

Output :

Time Complexity : O(N * log a), where a is the largest number of the array