HackerEarth Magic Sum problem solution

YASH PAL, 31 July 202417 February 2026

In this HackerEarth Magic Sum problem solution We have a FULL binary tree i.e. each node except leaves has two children.

The magic sum between any two leaf nodes (both possibly same) is the number obtained after adding values of all the nodes (including starting and ending nodes) in a unique path from first leaf to the later one.

Your task is to find the maximum magic sum in the binary tree.

HackerEarth Magic Sum problem solution

HackerEarth Magic Sum problem solution.

#include<vector>
#include<stdio.h>
#include<assert.h>
#include<limits.h>
#include<string.h>
#include<algorithm>
#define read(x) scanf("%d",&x)
using namespace std;

vector<int> list[515];
int sum, visited[515], ans;

int dfs(int i, int a[], int st=0)
{
    visited[i]=1;
    if(list[i].size()==1) ans=max(ans,a[i]);
    if(list[i].size()==1 && !st)  return a[i];
    int sum=INT_MIN;
    for(int j=0; j<list[i].size(); j++)
    {
        int v = list[i][j];
        if(!visited[v]) sum=max(sum, dfs(v, a));
    }
    return a[i]+sum;
}

int main()
{
  //clock_t startTime = clock();
  //freopen("in_2.txt","r",stdin);
  //freopen("out_2.txt","w",stdout);
    int T, N;
    read(T);
    while(T--)
    {
        read(N);
        int a[N];
    assert(N>=1 && N<=511);
    if(N==1) { scanf("%d",&a[0]); printf("%dn",a[0]); continue; }
        for(int i=0; i<N; i++) list[i].clear();
        for(int i=0; i<N; i++) read(a[i]);
        for(int i=0; i<N/2; i++)
        {
            list[i].push_back(2*i+1);
            list[2*i+1].push_back(i);
            list[i].push_back(2*i+2);
            list[2*i+2].push_back(i);
        }
        ans=INT_MIN;
        for(int i=N/2; i<N; i++)
        {
            memset(visited, 0, sizeof(visited));
            ans=max(ans, dfs(i,a,1));
        }
        printf("%dn",ans);
    }
    //clock_t endTime = clock();
    //fprintf(stderr, "nTime: %.5f secondsn", double(endTime - startTime) / CLOCKS_PER_SEC);
    return 0;
}

Second solution

#include<bits/stdc++.h>
using namespace std;
#define assn(n,a,b) assert(n>=a && n<=b)
int arr[100009][3]={};
void foo(int cur, int n)
{
    if(cur>n/2){arr[cur][1]=arr[cur][2]=0;return;}
    foo(cur*2,n);
    foo(cur*2 +1,n);
    arr[cur][1]=max(arr[cur*2][1],arr[cur*2][2])+arr[cur*2][0];
    arr[cur][2]=max(arr[cur*2+1][1],arr[cur*2+1][2])+arr[cur*2+1][0];
}
int main()
{
    int t;
    cin >> t;
    assn(t,1,500);
    while(t--)
    {
  int n,i,ans=-INT_MAX;
  cin >> n;
  assn(n,0,511);
  assert((n&(n+1))==0);
  for(i=1; i<=n; i++)
      cin >> arr[i][0];
  foo(1,n);
  for(i=1; i<=n; i++)
      ans=max(ans,arr[i][0]+arr[i][1]+arr[i][2]);
  cout << ans << endl;
    }
    return 0;
}

coding problems solutions HackerEarth HackerEarth

Leave a Reply