Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • Internet of Things (IoT)
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
  • Work with US
Programmingoneonone
Programmingoneonone

HackerEarth Count pairs problem solution

YASH PAL, 31 July 2024
In this HackerEarth Count pairs problem solution, You are given an array A consisting of N non-negative integers. You are also given 2 integers p(a prime number) and k. You are required to count number of pairs (i,j) where, 1 <= i < j <= N and satisfying: 
     (Ai*Ai + Aj*Aj + Ai*Aj) mod p = k                                                 
where a mod p = b means that b is the remainder when a is divided by p. In particular, 0 <= b < p.
You are given T test cases.
HackerEarth Count pairs problem solution

HackerEarth Count pairs problem solution.

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while(t--){
int n, k, p;
cin >> n >> k >> p;
vector<int> arr(n);
int i;
for(i = 0; i < n; i++)
{
cin >> arr[i];
arr[i] = arr[i]%p;
}
sort(arr.begin(), arr.end());
int ans = 0;
vector<pair<int, int>> vec;
for(i = 0; i < n ; i++){
int j = i, cnt = 0;
while(j < n && arr[j] == arr[i])
cnt++, j++;
int x = arr[i];
if((3*x*x%p) == k)
ans += cnt*(cnt - 1)/2;
int y = (((x*x%p)*x%p - k*x%p)%p + p)%p;
vec.push_back({y, cnt});
i = j - 1;
}
sort(vec.begin(), vec.end());
for(i = 0; i < vec.size() ; i++){
int j = i, lin = 0, sqr = 0;
while(j < vec.size() && vec[i].first == vec[j].first)
lin += vec[j].second, sqr += vec[j].second*vec[j].second, j++;
ans += (lin*lin - sqr)/2;
i = j - 1;
}
cout << ans << 'n';
}
}
coding problems solutions

Post navigation

Previous post
Next post

Related website

The Computer Science

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes