Skip to content
Programming101
Programming101

Learn everything about programming

  • Home
  • CS Subjects
    • IoT – Internet of Things
    • 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
Programming101
Programming101

Learn everything about programming

HackerEarth Number of Balloons problem solution

YASH PAL, 31 July 2024
In this HackerEarth Number of Balloons problem solution, You have arranged balloons in a linear order. Every balloon is colored and the ith balloon’s color is represented by Ci. Here, the color of balloons is depicted with numbers. 
The number k is not a suitable number, therefore you decide to use it for the less number of times. You do not contain any range of ballons in which a color repeats exactly k times. If the displayed balloons are numbered from b0,b1,b2,…,bn-1, then the range of balloons from l to r is bl,b1+1,bl+2,…br.
You are provided with some specific ranges and your task is to determine the number of colors that get repeated for exactly k times in each range that is provided.
HackerEarth Number of Balloons problem solution

HackerEarth Number of Balloons problem solution.

#include<bits/stdc++.h>
#include<fstream>

using namespace std;
const int maxn=1e5+10;
int a[maxn],n,seg[3][20][maxn],mk[maxn],b[maxn];
map<int,vector<int> > mark;

void pre(){
for(int i=1;i<=n;i++){
mark[a[i]].push_back(i);
}
}

struct segment{
int ans=0,num=0;
map<int,int> mk;
segment(int x1,int x2){
num=x2;
for(int i=1;i<=n;i++)
b[i]=0;
for(int i=1;i<=n;i++)
if(!mk[a[i]]){
mk[a[i]]=1;
for(int j=0;j<mark[a[i]].size();j++)
if(j>=x1)
b[mark[a[i]][j]]=mark[a[i]][j-x1];
else
b[mark[a[i]][j]]=-1;
}
make_seg(1,n,1);
}

void make_seg(int l,int r,int len)
{
if(l==r){
seg[num][len][l]=b[l];
return ;
}
int mid=(l+r)/2;
make_seg(l,mid,len+1);
make_seg(mid+1,r,len+1);
merge(seg[num][len+1]+l,seg[num][len+1]+mid+1,seg[num][len+1]+mid+1,seg[num][len+1]+r+1,seg[num][len]+l);
}

int bs(int l,int r,int k,int len)
{
if(l==r){
if(seg[num][len][l]>=k)
return 0;
return l;
}
int mid=(l+r+1)/2;
if(seg[num][len][mid]<k)
return bs(mid,r,k,len);
else
return bs(l,mid-1,k,len);
}

void ans_seg(int l,int r,int s,int f,int len)
{
if(f<l || r<s)
return;
if(s<=l && r<=f){
int x=bs(l,r,s,len);
if(x!=0)
ans+=x-l+1;
return;
}
int mid=(l+r)/2;
ans_seg(l,mid,s,f,len+1);
ans_seg(mid+1,r,s,f,len+1);
}

};

int main()
{
int k,q;
cin>>n>>k>>q;
for(int i=1;i<=n;i++)cin>>a[i];
pre();
segment a(k+1,0);
segment b(k,1);
segment c(k-1,2);
int ans=0;
while(q--){
int l,r;
cin>>l>>r;
l=(l+ans)%n;
r=(r+ans)%n;
l++;
r++;
if(r<l)
swap(l,r);
a.ans_seg(1,n,l,r,1);
b.ans_seg(1,n,l,r,1);
c.ans_seg(1,n,l,r,1);
ans=(b.ans-c.ans)-(a.ans-b.ans);
cout<<ans<<endl;
a.ans=0;b.ans=0;c.ans=0;
}
}

Second solution

#include<bits/stdc++.h>
using namespace std;
int n;

namespace segment{
const int maxn = 1e7; // TODO
int eof = 1;
int L[maxn], R[maxn], seg[maxn];

int add(int v, int x, int root, int st = 0, int en = n){
assert(eof<maxn);

seg[eof] = seg[root] + x;
L[eof] = L[root];
R[eof] = R[root];
root = eof++;

if(en - st < 2)
return root;
int mid = (st + en) >> 1;
if(v < mid)
L[root] = add(v, x, L[root], st, mid);
else
R[root] = add(v, x, R[root], mid, en);
return root;
}

int get(int l, int r, int root, int st = 0, int en = n){
if(l <= st && en <= r)
return seg[root];
if(r <= st || en <= l)
return 0;
int mid = (st + en) >> 1;
return get(l, r, L[root], st, mid) +
get (l, r, R[root], mid, en);
}
}

const int maxn = 1e5 + 10;
int k, q, ar[maxn];
int l[maxn], r[maxn];

void init(){
cin >> n >> k >> q;
vector<int> vc;
for(int i = 0; i < n; i++)
cin >> ar[i], vc.push_back(ar[i]);
sort(vc.begin(), vc.end());
vc.resize(unique(vc.begin(), vc.end()) - vc.begin());
for(int i = 0; i < n; i++)
ar[i] = lower_bound(vc.begin(), vc.end(), ar[i]) - vc.begin();
for(int i = 0; i < q; i++)
cin >> l[i] >> r[i];
}

vector<int> vc[maxn];
int root[maxn];

inline void add(const int &v,const int &x,int &node){
if(vc[v].size() >= k)
node = segment::add(vc[v][vc[v].size() - k], x, node);
if(vc[v].size() > k)
node = segment::add(vc[v][vc[v].size() - k - 1], -x, node);
}

void build(){
int node = 0;
for(int i = 0; i < n; i++){
add(ar[i], -1, node);
vc[ar[i]].push_back(i);
add(ar[i], +1, node);
root[i] = node;
}
}

int main(){
init();
build();
int ans = 0;
for(int i = 0; i < q; i++){
l[i] = (l[i] + ans) % n;
r[i] = (r[i] + ans) % n;
if(l[i] > r[i])
swap(l[i], r[i]);
ans = segment::get(l[i], r[i] + 1, root[r[i]]);
cout << ans << 'n';
}
}
coding problems solutions

Post navigation

Previous post
Next post
  • HackerRank Separate the Numbers solution
  • How AI Is Revolutionizing Personalized Learning in Schools
  • GTA 5 is the Game of the Year for 2024 and 2025
  • Hackerrank Day 5 loops 30 days of code solution
  • Hackerrank Day 6 Lets Review 30 days of code solution
How to download udemy paid courses for free

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
©2025 Programming101 | WordPress Theme by SuperbThemes