Why is my code giving wrong answer? Please help!

Revision en1, by ShadowsCread, 2023-12-20 04:24:09

1902C - Insert and Equalize

#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.

Tags help, c++, debug, hacking

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English ShadowsCread 2023-12-20 04:24:09 1190 Initial revision (published)