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 Xor Rectangle problem solution

YASH PAL, 31 July 2024
In this HackerEarth Xor Rectangle problem solution, You have an array of N integers S1, S2, … SN. Consider a N x N matrix such that Aij = Si XOR SJ.
You have been given Q queries. Each query consists of four integers x1, y1, x2, y2 which denotes a submatrix with (x1, y1) as their top-left corner and (x2, y2) as their bottom-right corner such that x1 <= x2 and y1 <= y2. For each query, you have to print the summation of all integers lying in queried submatrix.
HackerEarth Xor Rectangle problem solution

HackerEarth Xor Rectangle problem solution.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
int s[1000011][32];
int p[1000011];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
for(int i=1;i<=N;i++) {
cin >> p[i];
for(int j=0;j<20;j++) {
if(p[i]&(1<<j)) {
s[i][j]++;
}
s[i][j]+=s[i-1][j];
}
}
ll o1,o2,z1,z2;
int Q,x1,y1,x2,y2;
cin >> Q;
while(Q--) {
cin >> x1 >> y1 >> x2 >> y2;
ll ans = 0;
rep(j,20) {
o1 = s[x2][j]-s[x1-1][j];
z1 = x2-x1+1 - o1;
o2 = s[y2][j]-s[y1-1][j];
z2 = y2-y1+1 - o2;
ans+=(o1*z2+o2*z1)*(1LL<<j);
}
cout << ans << "n";
}
}

Second solution

#pragma GCC optimize("O3")
#define _CRT_SECURE_NO_WARNINGS
#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime>

#include <memory.h>
#include <assert.h>

#define y0 sdkfaslhagaklsldk

#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define norm asdfasdgasdgsd
#define have adsgagshdshfhds
#define ends asdgahhfdsfshdshfd

#define eps 1e-11
#define M_PI 3.141592653589793
#define bs 1000000007
#define bsize 512

#define ldouble long double

using namespace std;

long long INF = 1e9;
const int N = 1200031;

int tests,n;
int ar[N],s[N][22];

int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);

cin>>n;

for (int i=1;i<=n;i++)
{
cin>>ar[i];
for (int j=0;j<20;j++)
{
s[i][j]=s[i-1][j];
if (ar[i]&(1<<j))
s[i][j]+=1;
}
}

cin>>tests;
for (;tests;--tests)
{
int a,b,c,d;
cin>>a>>c>>b>>d;

long long ans=0;
for (int bit=0;bit<20;bit++)
{
int cnt1=s[b][bit]-s[a-1][bit];
int cnt2=(b-a+1)-cnt1;
int cnt3=s[d][bit]-s[c-1][bit];
int cnt4=(d-c+1)-cnt3;
ans+=(1ll<<bit)*cnt1*cnt4+(1ll<<bit)*cnt2*cnt3;
}
cout<<ans<<"n";
}

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