PROBLEM LINK:
Author: Ankush Khanna
DIFFICULTY:
Easy
PREREQUISITES:
PROBLEM:
Given an integer K and a sequence A of N integers, find \min\limits_{i \in \{1 \dots N\}}\{\text{lcm}(K, A_{i})\}. If this answer exceeds 10^{18}, print -1 instead.
QUICK EXPLANATION:
It is quite obvious from the problem statement itself that it is asking for the minimum LCM of K with each of the N elements in A. It’s just that we need to handle possible integer overflows for the final sub-task carefully.
EXPLANATION:
It is mentioned that Krishna visits the coffee shop every K units of time, and we need to find a girl which he’ll meet the earliest given that that girl visits the coffee shop every X (X \in A) units of time. Now, their possible meeting times can be given by the equation \alpha \times K = \beta \times X where \alpha, \beta \in \mathbb{Z}.
We need to find minimum such time, which by definition is the LCM of X and K. Also, if this LCM exceeds 10^{18}, i.e., \text{lcm}(K, X) \gt 10^{18}, then we report it by printing -1.
The first sub-task is quite trivial if you’ve figured out this much. You can just find the LCM of K iteratively with each of the N integers in A and just find the minimum one. There will be no integer overflows even with 32 bit integers. Also, there won’t be any case where you’ll have to print -1.
Difference between the first and second sub-tasks is just that in the second sub-task 32 bit integers will overflow, so you’ll have to use 64 bit integers. Here also you won’t have to print -1 in any case.
The third and the final sub-task is the one where you might need to print -1 and compute values which even 64 bit integers won’t be able to hold. Here we’ll have to apply some smart tricks to avoid integer overflow using 64 bit integers.
[Note: A 64 bit signed integer can hold values up to \sim9.22 \times 10^{18} ]
Using the formula \text{lcm}(A_{i}, K) = \frac{A_{i} \times K}{\text{gcd}(A_{i}, K)}\space, we can avoid integer overflows by checking if \frac{A_{i}}{\text{gcd}(A_{i}, K)} \geq \Big \lceil \frac{10^{18} + 1}{K} \Big \rceil for each valid i (because, according to the problem, LCM should not exceed 10^{18}). If so, we avoid calculating LCM, else it will guarantee that there will be no integer overflow in the LCM. Also, there’s a cool integer arithmetic trick for computing ceil value for a fraction. For two integers a and b, \big \lceil \frac{a}{b} \big \rceil = \big \lfloor \frac{a + b - 1}{b} \big \rfloor, where floor is by default calculated in integer arithmetic, so we don’t need to explicitly apply it.
SOLUTION:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
const long INF = (long) 1e18 + 1L;
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
long k;
cin >> k;
long ans = INF;
for (int i = 0; i < n; i++) {
long x;
cin >> x;
long safe = x / __gcd(k, x);
if (safe >= (INF + k - 1L) / k) {
continue;
}
ans = min(ans, safe * k);
}
cout << (ans == INF ? -1L : ans) << '\n';
}
return 0;
}
ALTERNATE SOLUTIONS:
There are other ways of getting rid of integer overflows for the final sub-task. Some of them are mentioned below:
Using floating point calculations
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
const long INF = (long) 1e18 + 1L;
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
long k;
cin >> k;
long ans = INF;
for (int i = 0; i < n; i++) {
long x;
cin >> x;
x /= __gcd(x, k);
if (static_cast<double>(x) > 1e18 / k) {
continue;
}
ans = min(ans, x * k);
}
cout << (ans == INF ? -1L : ans) << '\n';
}
return 0;
}
Using 128 bit integer for calculations
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
const long INF = (long) 1e18 + 1L;
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
long k;
cin >> k;
long ans = INF;
for (int i = 0; i < n; i++) {
long x;
cin >> x;
__int128_t val = static_cast<__int128_t>(k) / __gcd(k, x) * x;
if (val > static_cast<__int128_t>(INF)) {
continue;
}
ans = min(ans, static_cast<long>(val));
}
cout << (ans == INF ? -1L : ans) << '\n';
}
return 0;
}
Using Logarithms
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
const long INF = (long) 1e18 + 1L;
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
long k;
cin >> k;
long ans = INF;
for (int i = 0; i < n; i++) {
long x;
cin >> x;
x /= __gcd(k, x);
if (log10(x) + log10(k) > 18.0) {
continue;
}
ans = min(ans, x * k);
}
cout << (ans == INF ? -1L : ans) << '\n';
}
return 0;
}
Using simple logarithm rules, we can get rid of overflows. Just basic mathematics.
We need to check if \frac{A_{i} \times K}{\text{gcd}(A_{i}, K)} \gt 10^{18} for each valid i. Taking logarithm (base 10) on both sides, we get:
(Applying logarithm does not disturb inequalities)
\log_{10}(P \times K) > \log_{10}(10^{18}) \space \space \space \space \space \space \space \space \space \space \space \space \Big( \text{where } P = \frac{A_{i}}{\text{gcd}(K, A_{i})} \Big)
\implies \space \space \log_{10}{P} + \log_{10}{K} \gt 18
We can simply apply this cool logarithm trick to check if the LCM is greater than 10^{18} and hence avoid any possible integer overflow.
COMPLEXITY:
Time complexity: As Euclidean Algorithm for calculating GCD of two numbers a and b works in O(\log{\max\{a, b\}}), and we do this for all of the N integers in A in each test, therefore, the total time complexity is O(N \log \max\{A_{1 \dots N}\}) per test.
Space Complexity: O(1) auxiliary space per test
Feel free to share your approach. If you have any queries, they are always welcome.