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 Triangular Ranges problem solution

YASH PAL, 31 July 2024
In this HackerEarth Triangular Ranges problem solution, Kuku recently learnt about triangular numbers. If you are not familiar with the triangular numbers follow this link first http://en.wikipedia.org/wiki/Triangular_number. Ani thinks Kuku has not learnt it properly and start asking questions. But, As we all know kuku is one of the most intelligent on this planet. He answered each and every question correctly. This annoyed Ani and he geared up his question’s level and started asking even harder questions. Kuku can’t answer such big questions manually. So , He decided to write a computer program which can answer Ani’s questions .
Kuku is good at mathematics but not at programming ( Dont Doubt His Intelligence ) . So,he hired you ( A World Class Programmer ) to write a computer program which can answer Ani’s Questions with in time.
In Each question, Ani has given a range [L,R] and asked kuku to calculate numbers of such triplets [A,B,K] which follows
A + B = K
where A, B are any two triangular numbers and K must be in an integers that belongs to given range [L,R] both inclusive.
HackerEarth Triangular Ranges problem solution

HackerEarth Triangular Ranges problem solution.

#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<climits>
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define ll long long
#define VI vector<int>
#define PII pair<int,int>
#define VII vector<PII >
#define ft first
#define sd second
#define rz(v,n) v.resize(n)
#define VL vector<ll>
#define VLL vector<pair<ll,ll> >
#define PLL pair< ll,ll >
#define all(v) v.begin(),v.end()
#define IT iterator
// Input/Output
#define print(v) printf("%dn",v)
#define printll(v) printf("%lldn",v)
#define scan(v) scanf("%d",&v)
#define scanll(v) scanf("%lld",&v)
// loops
#define FOR(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) for(i=0;i<n;i++)
//extra
#define ms(v,val) memset(v,val,sizeof(v))
#define fill(v,val) fill(all(v),val)
#define f_in(st) freopen(st,"r",stdin)
#define f_out(st) freopen(st,"w",stdout)
#define PIE 3.14159265358979323846264338327950
#define MOD 1000000007
#ifdef ONLINE_JUDGE
inline void inp( int &n )
{
n=0;
int ch=getchar_unlocked();int sign=1;
while( ch < '0' || ch > '9' ){if(ch=='-')sign=-1; ch=getchar_unlocked();}

while( ch >= '0' && ch <= '9' )
n = (n<<3)+(n<<1) + ch-'0', ch=getchar_unlocked();
n=n*sign;
}
#else
inline void inp(int &n){
cin>>n;
}
#endif
ll UpperLimit=1000000000000LL;
#define MAX 1414215
ll A[MAX],size;
inline ll pre_process(){
size=1;
while(((size*(size+1))/2)<=UpperLimit){
A[size]=(size*(size+1))/2;
size++;
}
--size;
cout<<size<<endl;
}
// UpperBound
inline int mylower_bound(int L,int R,ll val){
int left=L;
int right=R;
if(A[right]<val) return 0;
if(A[left]>=val) return (R-L+1);
while(L<=R){
int mid=(L+R)/2;
if(A[mid]>=val&&(mid==left||A[mid-1]<val))
return (right-mid+1);
if(A[mid]>=val) R=mid-1;
else L=mid+1;
}
}
// LowerBound
inline int myupper_bound(int L,int R,ll val){
int left=L;
int right=R,mid;
if(A[left]>val) return (R-L+1);
if(A[right]<=val) return 0;
while(L<=R){
mid=(L+R)/2;
if(A[mid]>val&&(mid==left||A[mid-1]<=val))
return (right-mid+1);
else if(A[mid]>val) R=mid-1;
else L=mid+1;
}
}
inline ll cal(ll L,ll R){
ll count=0;
for(int i=1;i<=size&&A[i]<R;i++){
count+=(mylower_bound(i,size,L-A[i])-myupper_bound(i,size,R-A[i]));
}
return count;
}

int main(){
pre_process();
int t;
inp(t);
assert(t<=5);
while(t--){
ll L,R;
scanll(L);scanll(R);
assert(L<=R&&L<=UpperLimit&&R<=UpperLimit);
printll(cal(L,R));
}
return 0;
}

Second solution

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cassert>
using namespace std;
int Size=0;
long long int tri_num[2000005];
void pre_cal()
{
long long int i;
for(i=1;;i++){
tri_num[i-1]=(i*(i+1))/2;
if(tri_num[i-1]>1000000000000LL)
break;
}
Size=i;
}
int UpperBound(int i,long long val)
{
int lb=i,ub=Size-1,mid;
while(lb<ub)
{
mid=(lb+ub)/2;
if(tri_num[mid]>val)
ub=mid;
else
lb=mid+1;
}
return ub;
}
int LowerBound(int i,long long val)
{
int lb=i,ub=Size-1,mid;
while(lb<ub)
{
mid=(lb+ub)/2;
if(tri_num[mid]<val)
lb=mid+1;
else
ub=mid;
}
return lb;
}
int main()
{
pre_cal();
int test,i;
cin>>test;
while(test--)
{
long long int L,R,Count=0;
cin>>L>>R;
assert(L<=R && L>=1 && L<=1000000000000LL && R>=1 && R<=1000000000000LL );
for(i=0;i<Size && tri_num[i]<R;i++)
Count=Count+(UpperBound(i,R-tri_num[i])-LowerBound(i,L-tri_num[i]));
cout<<Count<<endl;

}
return 0;
}
coding problems

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