#include <stdio.h>
#include <stdlib.h>
int sum_subarr(int arr[], int l, int r){
int sum = 0;
for(int i = l; i <= r; i++)
{
sum += arr[i];
}
return sum;
}
int heavy_coin(int arr[], int l, int r){
if(r == l)
{
return r;
}
int midl = l + (r - l)/3;
int midr = r - (r - l)/3;
int lw = sum_subarr(arr, l, midl);
int mw = sum_subarr(arr, midl + 1, midr);
if ( lw > mw )
{
return heavy_coin(arr, l, midl);
}
else if ( lw < mw )
{
return heavy_coin(arr, midl + 1, midr);
}
else
{
return heavy_coin(arr, midr + 1, r);
}
}
int main(int argc, char *argv[])
{
int arr[] = {1,1,1,1,2,1,1,1,1};
int l = 0;
int r = 8;
int res = -1;
res = heavy_coin(arr, l, r);
printf("Hevy coin is at index: %d\n", res);
return EXIT_SUCCESS;
}