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 Distinct Integers in Range solution

YASH PAL, 31 July 2024
In this HackerEarth Distinct Integer in Range problem solution You are given two arrays A and B each of length N. Now you is given Q queries. In each query, you are given two pairs of ranges i.e. a range [a,b] in array A and range [c,d] in the array B. For each query, you need to count distinct elements in the array which is formed by combining elements of both the ranges in the query.
HackerEarth Distinct Integers in Range problem solution

HackerEarth Distinct Integers in Range problem solution.

#include<bits/stdc++.h>
#define LL long long int
#define M 1000000007
#define endl "n"
#define eps 0.00000001
LL pow(LL a,LL b,LL m){LL x=1,y=a;while(b > 0){if(b%2 == 1){x=(x*y);if(x>m) x%=m;}y = (y*y);if(y>m) y%=m;b /= 2;}return x%m;}
LL gcd(LL a,LL b){if(b==0) return a; else return gcd(b,a%b);}
LL gen(LL start,LL end){LL diff = end-start;LL temp = rand()%start;return temp+diff;}
using namespace std;
int a[100001];
int b[100001];
bitset<5001>tree1[400001] , tree2[400001];
void build(int node,int i,int j){
if(i > j)
return;
if(i == j){
tree1[node].set(a[i]);
tree2[node].set(b[i]);
return;
}
int mid = (i + j) / 2;
build(2 * node , i , mid);
build(2 * node + 1 , mid + 1 , j);
tree1[node] = tree1[2 * node] | tree1[2 * node + 1];
tree2[node] = tree2[2 * node] | tree2[2 * node + 1];
}

bitset<5001>query1(int node,int i,int j,int l,int r){
if(i > j || i > r || j < l)
return 0;
if(i >= l && j <= r)
return tree1[node];
int mid = (i + j) / 2;
return query1(2 * node , i , mid , l , r) | query1(2 * node + 1 , mid + 1 , j , l , r);
}

bitset<5001>query2(int node,int i,int j,int l,int r){
if(i > j || i > r || j < l)
return 0;
if(i >= l && j <= r)
return tree2[node];
int mid = (i + j) / 2;
return query2(2 * node , i , mid , l , r) | query2(2 * node + 1 , mid + 1 , j , l , r);
}

int main()
{
ios_base::sync_with_stdio(0);
int n;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
for(int i = 1; i <= n; i++){
cin >> b[i];
}
build(1 , 1 , n);
int q;
cin >> q;
while(q--){
int a , b , c , d;
cin >> a >> b >> c >> d;
cout << (query1(1 , 1 , n , a , b) | query2(1 , 1 , n , c , d)).count() << endl;
}
}

Second solution

#include <bits/stdc++.h>

using namespace std;

const int N = 1E5 + 5;
const int M = 5E3 + 5;
int a[N];
int b[N];
bitset<M> rst;
bitset<M> segt_a[4 * N];
bitset<M> segt_b[4 * N];

void build_a(int node, int start, int end) {
if(start == end) {
segt_a[node].set(a[start]);
return;
}
int mid = (start + end) >> 1;
build_a(node << 1, start, mid);
build_a((node << 1) + 1, mid + 1, end);
segt_a[node] = segt_a[node << 1] | segt_a[(node << 1) + 1];
return;
}

void build_b(int node, int start, int end) {
if(start == end) {
segt_b[node].set(b[start]);
return;
}
int mid = (start + end) >> 1;
build_b(node << 1, start, mid);
build_b((node << 1) + 1, mid + 1, end);
segt_b[node] = segt_b[node << 1] | segt_b[(node << 1) + 1];
return;
}

bitset<M> query_a(int node, int start, int end, int L, int R) {
if(start > R || end < L)
return rst;
if(start >= L && end <= R)
return segt_a[node];
int mid = (start + end) >> 1;
return query_a(node << 1, start, mid, L, R) | query_a((node << 1) + 1, mid + 1, end, L, R);
}

bitset<M> query_b(int node, int start, int end, int L, int R) {
if(start > R || end < L)
return rst;
if(start >= L && end <= R)
return segt_b[node];
int mid = (start + end) >> 1;
return query_b(node << 1, start, mid, L, R) | query_b((node << 1) + 1, mid + 1, end, L, R);
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
for(int i = 1; i <= n; i ++)
cin >> a[i];
for(int i = 1; i <= n; i ++)
cin >> b[i];
build_a(1, 1, n);
build_b(1, 1, n);
int q;
cin >> q;
int L1, R1, L2, R2;
while(q --) {
cin >> L1 >> R1 >> L2 >> R2;
int ans = (query_a(1, 1, n, L1, R1) | query_b(1, 1, n, L2, R2)).count();
cout << ans << 'n';
}
return 0;
}
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