Day 3 Challenge

Posted on 21 April,2018 at 9:00pm IST

Birthday Choclate Challenge

Be with the series of challenges in flow, we are increasing the level of understanding. If you missed previous challenges you can refer here . Focus on the logic part now.

In this challenge,Manish has a chocolate bar that he wants to share it with his friend Nitesh. Each of the squares of chocolate has an integer value on it. He decides to share a contiguous segment of the bar selected such that the length of the segment matches Nitesh birth month and the sum of the integers on the squares is equal to his birth day. You must determine how many ways he can divide the chocolate.

Consider the chocolate bar as an array of squares, s = [1,2,1,3,2] He wants to find segments summing to Nitesh birth day, d = 3 with a length equalling his birth month,m = 2 . In this case, there are two segments meeting his criteria: [1,2] & [2,1].

Example 1 :-

Input :- 
4 
1 2 1 3
3 2

First line :- number of slices in  choclate bar user wants to create.
Second line :- Enters  integer values with limit specified on first line.
Third line :-  In the given example, 
3 :- birth day  
2 :- birth month

Output :-
2 (total number of possible ways Manish can slice the chocolate bar to distribute with his friend Nitesh)

How 2 is output ?

1 2 1 3 :- These are Chocolate slices 
As specified in third input line,
Manish have to give 2 slices from given choclate whose total will be 3

First two slices 1 + 2 = 3
Second and third slice total 2 + 1 = 3
Third and fourth slice total 1 + 3 = 4 . 
So,
There are two ways Manish can distribute 2 slices whose total is 3

Example 2:-

Input :-
4
1 1 1 1
4 2 

1 1 1 1 :- choclate slices
As specified in third input line of Example 2,
Manish have to give 2 slices to Nitesh such that consecutive slices total should be 4 .
Consecutive means Side by side in short.

First Slice + Second Slice total 1 + 1 = 2
But, we want total 4 as specified in third line of input.

Second Slice + Third Slice = 1 + 1 = 2
But, we want total 4 as specified in third line of input.


None of 2 slices in choclate bar can give you total 4.
So there are 0 ways to distribute the slices of chocolate.

Output :- 0

Example 3 :-

4
1 4 2 1
4 1

1 4 2 1 :- Choclate slices
As specified in line 3 of Example 3,
Manish has to distribute 1 slice whose total should be 4

In given choclate , second slice will give total 4
So there is 1 way to distribute choclate.

Output :- 1

This program is written in C Language

#include <stdio.h>
#include <stdlib.h>

int solve(int n, int* s, int d, int m){

int result = 0;
int startIndex = 0;
int add = 0;

for(int i = 0; i< n ; i++)
{
    startIndex = i;
for (int j = 0; j < m ; j++)
{
    add +=  s[j + startIndex];
} 
  if(add == d)
      {
      result++;
      }
    add = 0; 
}
return result;
}

int main(){
    int n; 
    scanf("%d", &n);
    int *s = malloc(sizeof(int) * n);
    for(int s_i = 0; s_i < n; s_i++){
       scanf("%d",&s[s_i]);
    }
    int d; 
    int m; 
    scanf("%d %d", &d, &m);
    int result = solve(n, s, d, m);
    printf("%d\n", result);
    return 0;
}

If any doubts you can comment below this article to discuss. Keep Learning. Day 4 challenge will be available on 22 April 2018.