HACHO - EDITORIAL

editorial
, ,
1

PROBLEM LINK

Practice

PROBLEM STATEMENT

Little Harry is very sad that he is not able to meet his friends during the quarantine. So, to make Harry happy his uncle Sirius gives him chocolates for the next N number of days. Harry finishes eating the chocolates he has received on a particular day, on the same day itself. But uncle Sirius is also concerned that Harry might eat too many chocolates, so he has asked for your help.
  • Here’s how you can help: You are given the number of chocolates Harry receives each day for N number of days starting from the very first day. Now you are given Q queries, in each query Uncle Sirius asks you the number of days Harry has taken to eat M chocolates in total.
  • (Please note that each query contains a different number of M.)

SOLUTION

There are many ways to approach this problem. In CPP , this can be viewed as a binary search problem, where we assign the first element of the array which is the result of precomputing the total sum upto i days, the low variable and the last element of this array to the high variable and in each iteration compare the value to be found to the element in 'mid' position. As a result of this comparison, adjust the high and low variable accordingly to iterate over the new range. However, this problem can be very much simplified by using the lower_bound() function of STL

the Binary search implementation is given below:

SOLUTION CODE

#include<bits/stdc++.h>
using namespace std;

typedef long long int lint;

int main()
{
  ios_base::sync_with_stdio(false);

  int m,n;
  cin>>n>>m;
  lint a[n],s[n];
  for(int i=0;i<n;i++)
  {
    cin>>a[i];
  }
  s[0]=a[0];
  for(int i=1;i<n;i++)
    {
      s[i]= a[i]+s[i-1];
    }
  int q;
  for(int i=0;i<m;i++)
  {
    cin>>q;
    int lo=0;
    int hi=n-1;
    int ans=0;
    while(lo<=hi)
    {
      int mid= (lo+hi)/2;
      if(s[mid]>=q)
      {
        ans=mid;
        hi=mid-1;
      }
      else
        lo=mid+1;
    }
    cout<< ans+1<<endl;
  }
}