Блог пользователя samuels_882

Автор samuels_882, история, 4 года назад, По-английски

Given an array A of size n.count the number of pairs such that A[i]*A[j]==A[i]+A[j]. Since the constraint of A[i] is upto 10^9 and N is upto 40,000 , I cannot run the naive technique of running a double loop. Any other way to solve it in one loop?

  • Проголосовать: нравится
  • -17
  • Проголосовать: не нравится

»
4 года назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

A[i] * A[j] = A[i] + A[j]
A[i] — A[i] * A[j] + A[j] = 0
A[i] * (1 — A[j]) + A[j] = 0
A[i] = A[j] / (1 — A[j])
if numbers are integers u need just to count pairs of (2, 2), (0, 0) else just use map like:

    int n;
    cin >> n;
    map<double, int> cnt;
    for (int i = 0; i < n; ++i) {
        double x;
        cin >> x;
        cnt[x]++;
    }
    int ans = 0;
    for (auto &i : cnt) {
        if (i.f == 1)
            continue;
        ans += cnt[i.f / (1 - i.f)] * i.s;
    }
    cout << ans << endl;
»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

the only valid pairs values are (0, 0) and (2, 2), so just count the number of twos and zeros, the result ist binom(zeros, 2)+binom(twos, 2)

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

A[i]*A[j]-A[i]=A[j]

A[i] = A[j]/(A[j]-1)

if A[j] % (A[j]-1) = 0 then we can find A[i] such that given condition satisfy & there are only two such interger 0 & 2.

let say, cnt1 = total 0s & cnt2 = total 2s

so answer will be cnt1*(cnt1 -1)/2 + cnt2*(cnt2 -1)/2

»
4 года назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

Please refrain from answering this question. This is from ongoin long challenge of codechef- https://www.codechef.com/DEC19B/problems/PLMU

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

lol cheatin' eh? It's from codechef long challenge.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I request the community to answer questions only if links are provided or atleast if it is posted from a genuine account. It feels really bad seeing the questions and solutions posted like this.