Skip to content
Programmingoneonone
Programmingoneonone

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
Programmingoneonone

LEARN EVERYTHING ABOUT PROGRAMMING

HackerEarth Simple Sum problem solution

YASH PAL, 31 July 2024
In this HackerEarth Simple Sum problem solution, You have been given an array of N integers A1,A2..AN. You have to find simple sum for this array. Simple Sum is defined as Sigma(i=1,i=N) Sigma(j=i,j=N) max(Ai,Ai+1,…,Aj) * (Ai | Aj). | denotes the bitwise OR operator.
HackerEarth Simple Sum problem solution

Topics we are covering

Toggle
  • HackerEarth Simple Sum problem solution.
    • Second solution

HackerEarth Simple Sum problem solution.

#include <bits/stdc++.h>
using namespace std;
#define ll long long unsigned
#define pb push_back
#define fr freopen("in.txt","r",stdin)
#define rep(i,n) for(int i=0;i<n;i++)
#define frep(i,n) for(int i=1;i<=n;i++)
#define maxval 100011
#define maxn 300011
#define pi pair<int,int>
#define f first
#define s second
#define MAXBITS 15
ll A[100011];
int dp[100011][20];
ll cnt[100011][20];
ll ans = 0;
int query(int i,int j) {
int len = j-i+1;
len = log2(len);
int p = dp[i][len];
int q = dp[j-(1<<len)+1][len];
if(A[p]>A[q]) return p;
return q;
}
void calc(int i,int j) {
if(i==j) {
ans+=A[i]*A[i];
return;
}
if(i>j) return;
int m = query(i,j);
if(m-i<=j-m) {
for(int k=i;k<=m;k++) {
rep(p,MAXBITS) {
if(A[k]&(1<<p)) {
ans+=A[m]*(1LL<<p)*(ll)(j-m+1);
} else{
ans+=A[m]*(1LL<<p)*(ll)(cnt[j][p]-cnt[m-1][p]);
}
}
}
} else{
for(int k=m;k<=j;k++) {
rep(p,MAXBITS) {
if(A[k]&(1<<p)) {
ans+=A[m]*(1LL<<p)*(ll)(m-i+1);
} else{
ans+=A[m]*(1LL<<p)*(ll)(cnt[m][p]-cnt[i-1][p]);
}
}
}
}
//ans = 0;
calc(i,m-1);
calc(m+1,j);
}
int main() {
freopen("in10.txt","r",stdin);
freopen("out10.txt","w",stdout);

int N;
cin >> N;
frep(i,N) {
cin >> A[i];
dp[i][0] = i;
rep(j,MAXBITS) {
cnt[i][j] = cnt[i-1][j];
if(A[i]&(1<<j)) {
cnt[i][j]++;
}
}
}
int p,q;
for(int s=1;s<20;s++) {
frep(i,N-(1<<s)+1) {
p = dp[i][s-1];
q = dp[i+(1<<(s-1))][s-1];
if(A[p]>A[q]) dp[i][s] = p;
else dp[i][s] = q;
}
}
calc(1,N);
cout << ans;
}

Second solution

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <algorithm>
using namespace std;

const int MAXN = 100000;
const int MAXM = 10000;
const int MAXBITS = 16;

int a[MAXN], cnt[MAXBITS][MAXN + 1];

struct MaxInfo
{
int value, i;
MaxInfo() {}
MaxInfo(int value, int i) : value(value), i(i) {}
};

MaxInfo st[20][MAXN];

inline bool operator < (const MaxInfo& a, const MaxInfo &b)
{
return a.value < b.value;
}

MaxInfo getMax(int l, int r)
{
int len = r - l + 1;
int x = (int)log2(len);
return max(st[x][l], st[x][r - (1 << x) + 1]);
}

long long divideAndConquer(int l, int r)
{
if (l > r) {
return 0;
}
if (l == r) {
return (long long) a[l] * a[l];
}
int mid = l + r >> 1;

MaxInfo maxValue = getMax(l, r);
long long ret = divideAndConquer(l, maxValue.i - 1) + divideAndConquer(maxValue.i + 1, r);
if (maxValue.i < mid) {
for (int i = l; i <= maxValue.i; ++ i) {
for (int bit = 0; bit < MAXBITS; ++ bit) {
if (a[i] >> bit & 1) {
ret += (long long)maxValue.value * (r - maxValue.i + 1) * (1LL << bit);
} else {
ret += (long long)maxValue.value * (cnt[bit][r + 1] - cnt[bit][maxValue.i]) * (1LL << bit);
}
}
}
} else {
for (int j = maxValue.i; j <= r; ++ j) {
for (int bit = 0; bit < MAXBITS; ++ bit) {
if (a[j] >> bit & 1) {
ret += (long long)maxValue.value * (maxValue.i - l + 1) * (1LL << bit);
} else {
ret += (long long)maxValue.value * (cnt[bit][maxValue.i + 1] - cnt[bit][l]) * (1LL << bit);
}
}
}
}
return ret;
}

int main()
{
int n;
assert(scanf("%d", &n) == 1 && 1 <= n && n <= MAXN);
for (int i = 0; i < n; ++ i) {
assert(scanf("%d", &a[i]) == 1);
// fprintf(stderr, "%dn", a[i]);
assert(1 <= a[i] && a[i] <= MAXM);
st[0][i] = MaxInfo(a[i], i);
for (int bit = 0; bit < MAXBITS; ++ bit) {
cnt[bit][i + 1] = cnt[bit][i] + (a[i] >> bit & 1);
}
}
for (int i = 0, len = 1; len < n; ++ i, len *= 2) {
for (int j = 0; j + len * 2 <= n; ++ j) {
st[i + 1][j] = max(st[i][j], st[i][j + len]);
}
}
printf("%lldn", divideAndConquer(0, n - 1));
return 0;
}
coding problems solutions

Post navigation

Previous post
Next post
  • Automating Image Format Conversion with Python: A Complete Guide
  • 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
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
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes