CLLCM EDITORIAL

PROBLEM LINK
Practice
Contest
Author: Aman Kumar Singh
Tester: Avijit Agarwal, Sarthak Manna
Editorailist: Souradeep Paul

DIFFICULTY
Cakewalk

PREREQUISITES
Basic Math

PROBLEM
Given N numbers, find if there exists an odd integer x such that x is divisible by all N numbers. If yes, then print “YES”, otherwise “NO”.

EXPLANATION
It’s obvious that if x is an odd integer then all N numbers should be odd. If at least one number is even then no such x will exist as no odd number is divisible by an even number. So if all numbers are odd then the answer will be “YES”, otherwise “NO”.
The time complexity is \mathcal{O}(N).

SOLUTIONS
C++ solution can be found here
Java solution can be found here
Python solution can be found here

2 Likes

I calculated the LCM of all the given N integers and if the LCM is even then there exists no odd multiple of the given numbers. Else it does. Can anyone please explain why this approach led me to wrong answer?

It will overflow @aonmoii.

8 Likes

hey please can u help me??
our task is to find a odd no. which is multiple of all n number inserted
so first i sorted the array and then check largest element is even or odd if it is even print no if it is odd then divide this no. with all no. present in array(x%a[i])…if all no. is multiple of x then print yes other wise no… why i m getting error in this logic plz teellll meeeee @souradeep1999

4
3 5 7 15

see this case, according to your logic answer will be no, as 15 is not divisible by 7, but there is a number 105 which is divisible by both 7 and 15.

what if i take gcd of all no given!!
for ex if: 6 12 18 are the numbers than 3 divides all so why ans is no???

Read the question again, it’s asking for a number which is multiple of all the number, not the number which divides all the number

You need to find (check if exist) an odd number x which is divisible by all array elements not all array elements divided by x. Hope it is clear to you now.

1 Like

" So if all numbers are odd then the answer will be “ YES ”, otherwise “ NO ” "
What if all the numbers are odd prime ?? Then any number can’t be divisible by all the other numbers…
Test Case:
3
3 5 7

The odd no. should be divisible by them.
Read Problem carefully.

But in question they said that the number X should be present in N numbers which chef have ?
In your example 105 is not in the number list ?
Please explain .

i too tried the same approach

I wrote about the logic. Hope it’ll help you. :slight_smile:

What’s wrong with my code.?? I used the logic if there is even num present print NO else print YES

#include< iostream >
using namespace std;
int main()
{
    int t;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        int n,f=0;
        cin>>n;
        int arr[1000];

        for(int j=0;j<n;j++)
        cin>>arr[j];

        for(int j=0;j<n;j++)
        {
        if(arr[j]%2==0)
        {
            cout<<"NO"<<endl;
            f=1;
            break;
        }
        }
        if(f==0)
        cout<<"YES";
    }

    return 0;
}

See your output is not matching the way they wanted.

if(f==0)
{
    cout<<"YES\n";
}

try this once.

I too used the same technique. didn’t get the glitch

still didn’t worked

I’ve added C++14 program. Please check that & if any problem is still persists drop an email (falgunisarkar526@gmail.com). :mask:

one of the number is 105 .
because 3 * 5 * 7 = 105.
odd * odd = odd

I guess for a few big prime numbers in range 1-1000 the LCM would end up being the multiplication of those numbers and eventually overflow the 64 bit integer type which I naively thought was enough for the problem :sweat_smile: Lesson learned.