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
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?
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
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.
" 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
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 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 Lesson learned.