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
Programmingoneonone

HackerEarth Xsquare And Number List problem solution

YASH PAL, 31 July 2024
In this HackerEarth Xsquare And Number List problem solution Xsquare loves to play with numbers a lot. Today, he has a multi set S consisting of N integer elements. At first, he has listed all the subsets of his multi set S and later replaced all the subsets with the maximum element present in the respective subset.
Now, Xsquare wonders that given an integer K how many elements in the final list are greater than ( > ) , less than ( < ) or equals to ( == ) K.
To make this problem a bit more interesting, Xsquare decided to add Q queries to this problem. Each of the queries has one of the following type.
> K : Count the number of elements X in the final list such that X > K.
< K : Count the number of elements X in the final list such that X < K.
= K : Count the number of elements X in the final list such that X == K.
HackerEarth Xsquare And Number List problem solution

HackerEarth Xsquare And Number List problem solution.

#include <bits/stdc++.h>
using namespace std ;
#define LL long long int
#define ft first
#define sd second
#define PII pair<int,int>
#define MAXN 1000001
#define mp make_pair
#define f_in(st) freopen(st,"r",stdin)
#define f_out(st) freopen(st,"w",stdout)
#define sc(x) scanf("%d",&x)
#define scll(x) scanf("%lld",&x)
#define pr(x) printf("%dn",x)
#define pb push_back
#define MOD 1000000007
#define inf INT_MAX/2
#define ASST(X,L,R) assert(X >= L && X <= R)
int N,Q ;
vector<int> A ;

int power(int a,int b){
int res = 1 ;
while(b){
if(b%2){
res = (1LL * res * a) % MOD ;
}
b /= 2 ;
a = (1LL * a * a) % MOD ;
}
return res ;
}

int less_than_X(int X){
X -- ;
int c = upper_bound(A.begin(),A.end(),X)-A.begin() ;
return power(2,c) ;
}
int less_than_equals_to_X(int X){
int c = upper_bound(A.begin(),A.end(),X)-A.begin() ;
return power(2,c) ;
}

int main(){

sc(N) ;
sc(Q) ;
ASST(N,1,500000) ;
ASST(Q,1,500000) ;
A.resize(N) ;
for(int i=0;i<N;i++){
sc(A[i]) ;
ASST(A[i],1,1000000000) ;
}
sort(A.begin(),A.end()) ;
char ch ;
int X;
int total_subsets = power(2,N) ;
while(Q--){
cin >> ch ;
sc(X) ;
assert(ch == '>' || ch == '<' || ch == '=') ;
ASST(X,1,1000000000) ;
int ans = 0 ;
switch(ch){
case '<' : pr(less_than_X(X)) ;
break ;
case '>' : ans = less_than_equals_to_X(X) ;
ans = total_subsets - ans ;
if( ans < 0 )
ans += MOD ;
pr(ans) ;
break ;
case '=' : ans = less_than_equals_to_X(X) ;
ans -= less_than_X(X) ;
if( ans < 0 )
ans += MOD ;
pr(ans) ;
break ;
}
}
return 0 ;
}

Second solution

#include <bits/stdc++.h>
#define MAX 500005
#define lli long long
#define M 1000000007

using namespace std;

int A[500005];
lli pow2[500005];

void pre()
{
pow2[0] = 1;
for ( int i = 1; i <= 500001; i++ ) {
pow2[i] = pow2[i-1] + pow2[i-1];
if ( pow2[i] >= M ) pow2[i] -= M;
}
return;
}

int main()
{
pre();
int n,q,x;
char s[2];
scanf("%d%d", &n, &q);
assert(n<=500000);
assert(q<=500000);
for ( int i = 0; i < n; i++ ) {
scanf("%d", &A[i]);
assert(A[i] >= 1 && A[i]<=1000000000);
}
sort(A,A+n);
while ( q-- ) {
scanf("%s%d", &s, &x);
assert(x>=1&&x<=1000000000);
if ( s[0] == '=' ) {
int idx2 = upper_bound(A,A+n,x) - A;
idx2--;
int idx1 = lower_bound(A,A+n,x) - A;
if ( idx1 == n || A[idx1] > x ) {
printf("0n");
continue;
}
lli ans1 = pow2[idx1];
lli ans2 = pow2[idx2-idx1+1] - 1;
if ( ans2 < 0 ) ans2 += M;
printf("%lldn", (ans1*ans2)%M);
}
else if ( s[0] == '<' ) {
int idx = lower_bound(A, A+n, x) - A;
idx--;
lli ans1;
else ans1 = pow2[idx+1];
printf("%lldn", ans1);
}
else {
int idx = upper_bound(A,A+n,x) - A;
lli ans1 = pow2[idx];
lli ans2 = pow2[n-idx] - 1;
if ( ans2 < 0 ) ans2 += M;
printf("%lldn", (ans1*ans2)%M);
}
}
return 0;
}
coding problems solutions

Post navigation

Previous post
Next post

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