#include <bits/stdc++.h>
using namespace std;
void solve() {
int n; cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
if (n == 1) {
cout << 1 << "\n";
return;
}
sort(a.begin(), a.end());
vector<int> v;
for (int i = 1; i < n; i++) {
v.push_back(a[i] - a[i - 1]);
}
int gcd = 0;
for (int i = 0; i < v.size(); i++) {
gcd = __gcd(gcd, v[i]);
}
int ex = -1;
for (int i = n - 2; i >= 0; i--) {
if (a[i + 1] - gcd != a[i]) {
ex = a[i + 1] - gcd;
break;
}
}
if (ex == -1) {
ex = a[0] - gcd;
}
long long ans = 0;
for (int i = 0; i < n; i++) {
ans += (a[n - 1] - a[i]) / gcd;
}
ans += (a[n - 1] - ex) / gcd;
cout << ans << "\n";
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0);
int t = 1; cin >> t;
while (t--) solve();
return 0;
}
I think my code is optimal if my logic is correct. My code failed on the 170th test case in which the expected answer was 6 and my output comes as 8. Please provide a test case on which my above code fails.