### samuels_882's blog

By samuels_882, history, 7 weeks ago, ,

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

 » 7 weeks ago, # | ← Rev. 4 →   0 A[i] * A[j] = A[i] + A[j]A[i] — A[i] * A[j] + A[j] = 0A[i] * (1 — A[j]) + A[j] = 0A[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 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; 
 » 7 weeks ago, # | ← 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)
 » 7 weeks ago, # | ← 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 2sso answer will be cnt1*(cnt1 -1)/2 + cnt2*(cnt2 -1)/2
 » 7 weeks ago, # |   +26 Please refrain from answering this question. This is from ongoin long challenge of codechef- https://www.codechef.com/DEC19B/problems/PLMU
 » 7 weeks ago, # |   +6 lol cheatin' eh? It's from codechef long challenge.
 » 7 weeks ago, # |   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.