Optimal Strategy for a Game

Consider a row of n coins of values v1 . . . vn, where n is even. We play a game against an opponent
by alternating turns. In each turn, a player selects either the first or last coin from the row, removes it
from the row permanently, and receives the value of the coin. Determine the maximum possible
amount of money we can definitely win if we move first.
Note: The opponent is as clever as the user.

Let us understand the problem with few examples:

1. 5, 3, 7, 10 : The user collects maximum value as 15(10 + 5)

2. 8, 15, 3, 7 : The user collects maximum value as 22(7 + 15)

Does choosing the best at each move gives an optimal solution? No.
In the second example, this is how the game can be finished:

1. .......User chooses 8.
.......Opponent chooses 15.
.......User chooses 7.
.......Opponent chooses 3.
Total value collected by user is 15(8 + 7)

2. .......User chooses 7.
.......Opponent chooses 8.
.......User chooses 15.
.......Opponent chooses 3.
Total value collected by user is 22(7 + 15)

So if the user follows the second game state, the maximum value can be collected although the first
move is not the best.

Approach: As both the players are equally strong, both will try to reduce the possibility of winning of
each other. Now let's see how the opponent can achieve this.

There are two choices:

• The user chooses the 'ith' coin with value 'Vi': The opponent either chooses (i+1)th coin or
jth coin. The opponent intends to choose the coin which leaves the user with minimum
value.
i.e. The user can collect the value Vi + min(F(i+2, j), F(i+1, j-1) ) where [i+2,j] is the range of
array indices available to the user if the opponent chooses Vi+1 and [i+1,j-1] is the range of
array indexes available if opponent chooses the jth coin.
 • The user chooses the 'jth' coin with value 'Vj': The opponent either chooses 'ith' coin or '(j-
1)th' coin. The opponent intends to choose the coin which leaves the user with minimum
value, i.e. the user can collect the value Vj + min(F(i+1, j-1), F(i, j-2) ) where [i,j-2] is the
range of array indices available for the user if the opponent picks jth coin and [i+1,j-1] is
the range of indices available to the user if the opponent picks up the ith coin.

Following is the recursive solution that is based on the above two choices. We take a maximum of
two choices.

F(i, j) represents the maximum value the user

can collect from i'th coin to j'th coin.

F(i, j) = Max(Vi + min(F(i+2, j), F(i+1, j-1) ),

Vj + min(F(i+1, j-1), F(i, j-2) ))

As user wants to maximise the number of coins.

Base Cases

F(i, j) = Vi If j == i

F(i, j) = max(Vi, Vj) If j == i + 1

The recursive top down solution in is shown below

C++Java

// C++ code to implement the approach

#include <bits/stdc++.h>

using namespace std;

vector<int> arr;

map<vector<int>, int> memo;

int n = arr.size();

// recursive top down memoized solution

int solve(int i, int j)

if ((i > j) || (i >= n) || (j < 0))

return 0;

vector<int> k{ i, j };

if (memo[k] != 0)

return memo[k];

// if the user chooses ith coin, the opponent can choose

// from i+1th or jth coin. if he chooses i+1th coin,

// user is left with [i+2,j] range. if opp chooses jth

 // coin, then user is left with [i+1,j-1] range to

// choose from. Also opponent tries to choose in such a

// way that the user has minimum value left.

int option1

= arr[i]

+ min(solve(i + 2, j), solve(i + 1, j - 1));

// if user chooses jth coin, opponent can choose ith

// coin or j-1th coin. if opp chooses ith coin,user can

// choose in range [i+1,j-1]. if opp chooses j-1th coin,

// user can choose in range [i,j-2].

int option2

= arr[j]

+ min(solve(i + 1, j - 1), solve(i, j - 2));

// since the user wants to get maximum money

memo[k] = max(option1, option2);

return memo[k];

int optimalStrategyOfGame()

memo.clear();

return solve(0, n - 1);

// Driver code

int main()

arr.push_back(8);
 arr.push_back(15);

arr.push_back(3);

arr.push_back(7);

n = arr.size();

cout << optimalStrategyOfGame() << endl;

arr.clear();

arr.push_back(2);

arr.push_back(2);

arr.push_back(2);

arr.push_back(2);

n = arr.size();

cout << optimalStrategyOfGame() << endl;

arr.clear();

arr.push_back(20);

arr.push_back(30);

arr.push_back(2);

arr.push_back(2);

arr.push_back(2);

arr.push_back(10);

n = arr.size();

cout << optimalStrategyOfGame() << endl;

// This code is contributed by phasing17

The bottom up approach is shown below.

C++Java

// C++ program to find out

// maximum value from a given

// sequence of coins
#include <bits/stdc++.h>

using namespace std;

// Returns optimal value possible

// that a player can collect from

// an array of coins of size n.

// Note than n must be even

int optimalStrategyOfGame(int* arr, int n)

// Create a table to store

// solutions of subproblems

int table[n][n];

// Fill table using above

// recursive formula. Note

// that the table is filled

// in diagonal fashion (similar

// to http:// goo.gl/PQqoS),

// from diagonal elements to

// table[0][n-1] which is the result.

for (int gap = 0; gap < n; ++gap) {

for (int i = 0, j = gap; j < n; ++i, ++j) {

// Here x is value of F(i+2, j),

// y is F(i+1, j-1) and

// z is F(i, j-2) in above recursive

// formula

int x = ((i + 2) <= j) ? table[i + 2][j] : 0;

int y = ((i + 1) <= (j - 1))

? table[i + 1][j - 1]

: 0;

int z = (i <= (j - 2)) ? table[i][j - 2] : 0;

 table[i][j] = max(arr[i] + min(x, y),

arr[j] + min(y, z));

return table[0][n - 1];

// Driver program to test above function

int main()

int arr1[] = { 8, 15, 3, 7 };

int n = sizeof(arr1) / sizeof(arr1[0]);

printf("%d\n", optimalStrategyOfGame(arr1, n));

int arr2[] = { 2, 2, 2, 2 };

n = sizeof(arr2) / sizeof(arr2[0]);

printf("%d\n", optimalStrategyOfGame(arr2, n));

int arr3[] = { 20, 30, 2, 2, 2, 10 };

n = sizeof(arr3) / sizeof(arr3[0]);

printf("%d\n", optimalStrategyOfGame(arr3, n));

return 0;

Output

22

42
Complexity Analysis:

• Time Complexity: O(n2).

Use of a nested for loop brings the time complexity to n2.

• Auxiliary Space: O(n2).

As a 2-D table is used for storing states.

Mark as Read

Report An IssueIf you are facing any i

Egg Dropping Puzzle

The following is a description of the instance of this famous puzzle involving n=2 eggs and a building
with k=36 floors.
Suppose that we wish to know which stories in a 36-storey building are safe to drop eggs from, and
which will cause the eggs to break on landing. We make a few assumptions:
.....An egg that survives a fall can be used again.
.....A broken egg must be discarded.
.....The effect of a fall is the same for all eggs.
.....If an egg breaks when dropped, then it would break if dropped from a higher floor.
.....If an egg survives a fall then it would survive a shorter fall.
.....It is not ruled out that the first-floor windows break eggs, nor is it ruled out that the 36th-floor do
not cause an egg to break.
If only one egg is available and we wish to be sure of obtaining the right result, the experiment can
be carried out in only one way. Drop the egg from the first-floor window; if it survives, drop it from
the second-floor window. Continue upward until it breaks. In the worst case, this method may
require 36 droppings. Suppose 2 eggs are available. What is the least number of egg-droppings that
is guaranteed to work in all cases?
The problem is not actually to find the critical floor, but merely to decide floors from which eggs
should be dropped so that the total number of trials are minimized.

Method 1: Recursion.
In this post, we will discuss a solution to a general problem with 'n' eggs and 'k' floors. The solution is
to try dropping an egg from every floor(from 1 to k) and recursively calculate the minimum number
of droppings needed in the worst case. The floor which gives the minimum value in the worst case is
going to be part of the solution.
In the following solutions, we return the minimum number of trials in the worst case; these solutions
can be easily modified to print floor numbers of every trial also.
Meaning of a worst-case scenario: Worst case scenario gives the user the surety of the threshold
floor. For example- If we have '1' egg and 'k' floors, we will start dropping the egg from the first floor
till the egg breaks suppose on the 'kth' floor so the number of tries to give us surety is 'k'.
1) Optimal Substructure:
When we drop an egg from a floor x, there can be two cases (1) The egg breaks (2) The egg doesn't
break.

1. If the egg breaks after dropping from 'xth' floor, then we only need to check for floors lower
than 'x' with remaining eggs as some floor should exist lower than 'x' in which egg would not
break; so the problem reduces to x-1 floors and n-1 eggs.

2. If the egg doesn't break after dropping from the 'xth' floor, then we only need to check for
floors higher than 'x'; so the problem reduces to 'k-x' floors and n eggs.

Since we need to minimize the number of trials in worst case, we take the maximum of two cases.
We consider the max of above two cases for every floor and choose the floor which yields minimum
number of trials.

k ==> Number of floors

n ==> Number of Eggs
eggDrop(n, k) ==> Minimum number of trials needed to find the critical
floor in worst case.
eggDrop(n, k) = 1 + min{max(eggDrop(n - 1, x - 1), eggDrop(n, k - x)), where x is in {1, 2, ..., k}}
Concept of worst case:
For example :
Let there be '2' eggs and '2' floors then-:
If we try throwing from '1st' floor:
Number of tries in worst case= 1+max(0, 1)
0=>If the egg breaks from first floor then it is threshold floor (best case possibility).
1=>If the egg does not break from first floor we will now have '2' eggs and 1 floor to test which will
give answer as
'1'.(worst case possibility)
We take the worst case possibility in account, so 1+max(0, 1)=2
If we try throwing from '2nd' floor:
Number of tries in worst case= 1+max(1, 0)
1=>If the egg breaks from second floor then we will have 1 egg and 1 floor to find threshold
floor.(Worst Case)
0=>If egg does not break from second floor then it is threshold floor.(Best Case)
We take worst case possibility for surety, so 1+max(1, 0)=2.
The final answer is min(1st, 2nd, 3rd....., kth floor)
So answer here is '2'.

Below is the implementation of the above approach:

C++Java

#include <bits/stdc++.h>

using namespace std;

// A utility function to get

// maximum of two integers

int max(int a, int b)

return (a > b) ? a : b;

}
// Function to get minimum

// number of trials needed in worst

// case with n eggs and k floors

int eggDrop(int n, int k)

// If there are no floors,

// then no trials needed.

// OR if there is one floor,

// one trial needed.

if (k == 1 || k == 0)

return k;

// We need k trials for one

// egg and k floors

if (n == 1)

return k;

int min = INT_MAX, x, res;

// Consider all droppings from

// 1st floor to kth floor and

// return the minimum of these

// values plus 1.

for (x = 1; x <= k; x++) {

res = max(

eggDrop(n - 1, x - 1),

eggDrop(n, k - x));

if (res < min)

min = res;

}
 return min + 1;

// Driver program to test

// to printDups

int main()

int n = 2, k = 10;

cout << "Minimum number of trials "

"in worst case with "

<< n << " eggs and " << k

<< " floors is "

<< eggDrop(n, k) << endl;

return 0;

Output

Minimum number of trials in worst case with 2 eggs and 10 floors is 4

It should be noted that the above function computes the same subproblems again and again. See the
following partial recursion tree, E(2, 2) is being evaluated twice. There will many repeated
subproblems when you draw the complete recursion tree even for small values of n and k.

E(2, 4)
|
-------------------------------------
| | | |
| | | |
x=1/ x=2/ x=3/ x=4/
/ / .... ....
/ /
E(1, 0) E(2, 3) E(1, 1) E(2, 2)
/ /... /
x=1/ .....
/
E(1, 0) E(2, 2)
/
......
Partial recursion tree for 2 eggs and 4 floors.

Complexity Analysis:

• Time Complexity: As there is a case of overlapping sub-problems the time complexity is

exponential.

• Auxiliary Space :O(1). As there was no use of any data structure for storing values.

Since same subproblems are called again, this problem has Overlapping Subproblems property. So
Egg Dropping Puzzle has both properties (see this and this) of a dynamic programming problem. Like
other typical Dynamic Programming(DP) problems, recomputations of same subproblems can be
avoided by constructing a temporary array eggFloor[][] in bottom up manner.

Method 2: Dynamic Programming.

In this approach, we work on the same idea as described above neglecting the case of calculating
the answers to sub-problems again and again.. The approach will be to make a table which will store
the results of sub-problems so that to solve a sub-problem, it would only require a look-up from the
table which will take constant time, which earlier took exponential time.
Formally for filling DP[i][j] state where 'i' is the number of eggs and 'j' is the number of floors:

• We have to traverse for each floor 'x' from '1' to 'j' and find minimum of:

(1 + max( DP[i-1][j-1], DP[i][j-x] )).

This simulation will make things clear:

i => Number of eggs

j => Number of floors
Look up find maximum
Lets fill the table for the following case:
Floors = '4'
Eggs = '2'
1234
1 2 3 4 => 1
1 2 2 3 => 2
For 'egg-1' each case is the base case so the
number of attempts is equal to floor number.
For 'egg-2' it will take '1' attempt for 1st
floor which is base case.
For floor-2 =>
Taking 1st floor 1 + max(0, DP[1][1])
Taking 2nd floor 1 + max(DP[1][1], 0)
DP[2][2] = min(1 + max(0, DP[1][1]), 1 + max(DP[1][1], 0))
For floor-3 =>
Taking 1st floor 1 + max(0, DP[2][2])
Taking 2nd floor 1 + max(DP[1][1], DP[2][1])
Taking 3rd floor 1 + max(0, DP[2][2])
DP[2][3]= min('all three floors') = 2
For floor-4 =>
Taking 1st floor 1 + max(0, DP[2][3])
Taking 2nd floor 1 + max(DP[1][1], DP[2][2])
Taking 3rd floor 1 + max(DP[1][2], DP[2][1])
Taking 4th floor 1 + max(0, DP[2][3])
DP[2][4]= min('all four floors') = 3

C++Java

// A Dynamic Programming based for

// the Egg Dropping Puzzle

#include <bits/stdc++.h>

using namespace std;

// A utility function to get

// maximum of two integers

int max(int a, int b)

return (a > b) ? a : b;

/* Function to get minimum

number of trials needed in worst

case with n eggs and k floors */

int eggDrop(int n, int k)

/* A 2D table where entry

eggFloor[i][j] will represent

minimum number of trials needed for

i eggs and j floors. */

int eggFloor[n + 1][k + 1];

int res;

int i, j, x;

// We need one trial for one floor and 0

// trials for 0 floors

for (i = 1; i <= n; i++) {

eggFloor[i][1] = 1;

eggFloor[i][0] = 0;

// We always need j trials for one egg

// and j floors.

for (j = 1; j <= k; j++)

eggFloor[1][j] = j;

// Fill rest of the entries in table using

// optimal substructure property

for (i = 2; i <= n; i++) {

for (j = 2; j <= k; j++) {

eggFloor[i][j] = INT_MAX;

for (x = 1; x <= j; x++) {

res = 1 + max(

eggFloor[i - 1][x - 1],

eggFloor[i][j - x]);

if (res < eggFloor[i][j])

eggFloor[i][j] = res;

// eggFloor[n][k] holds the result

 return eggFloor[n][k];

/* Driver program to test to printDups*/

int main()

int n = 2, k = 36;

cout << "\nMinimum number of trials "

"in worst case with " << n<< " eggs and "<< k<<

" floors is "<< eggDrop(n, k);

return 0;

// this code is contributed by shivanisinghss2110

Output

Minimum number of trials in worst case with 2 eggs and 36 floors is 8

Complexity Analysis:

• Time Complexity: O(n*k^2).

Where 'n' is the number of eggs and 'k' is the number of floors, as we use a nested for loop
'k^2' times for each egg

• Auxiliary Space: O(n*k).

As a 2-D array of size 'n*k' is used for storing elements.

Method 3: Dynamic Programming using memoization.

C++Java

#include <bits/stdc++.h>

using namespace std;

#define MAX 1000

vector<vector<int>> memo(MAX, vector<int> (MAX, -1));

int solveEggDrop(int n, int k) {

 if(memo[n][k] != -1) { return memo[n][k];}

if (k == 1 || k == 0)

return k;

if (n == 1)

return k;

int min = INT_MAX, x, res;

for (x = 1; x <= k; x++) {

res = max(

solveEggDrop(n - 1, x - 1),

solveEggDrop(n, k - x));

if (res < min)

min = res;

memo[n][k] = min+1;

return min + 1;

int main() {

int n = 2, k = 36;

cout<<solveEggDrop(n, k);

return 0;

// contributed by Shivam Agrawal(shivamagrawal3)

Output

Mark as Read

Report An IssueIf you are facing any i

Count BSTs with n keys

Given N, Find the total number of unique BSTs that can be made using values from 1 to N.
Examples:

Input: n = 3

Output: 5

For n = 3, preorder traversal of Unique BSTs are:

1. 1 2 3

2. 1 3 2

3. 2 1 3

4. 3 1 2

5. 3 2 1

Input: 4

Output: 14

In this post we will discuss a solution based on Dynamic Programming. For all possible values of i,
consider i as root, then [1....i-1] numbers will fall in the left subtree and [i+1....n] numbers will fall in
the right subtree.

Now, let's say count(n) denotes number of structurally different BST that can be made using numbers
from 1 to n. Then count(n) can be calculated as:-

count(n)=summation of (count(i-1)*count(n-i)).

Below is the implementation for above approach:

C++Java

// C++ code to find number of unique BSTs

// Dynamic Programming solution

#include <bits/stdc++.h>

using namespace std;

// Function to find number of unique BST

int numberOfBST(int n)

{
 // DP to store the number of unique BST with key i

int dp[n + 1];

fill_n(dp, n + 1, 0);

// Base case

dp[0] = 1;

dp[1] = 1;

// fill the dp table in bottom-up approach.

for (int i = 2; i <= n; i++) {

for (int j = 1; j <= i; j++) {

// n-i in right * i-1 in left

dp[i] = dp[i] + (dp[i - j] * dp[j - 1]);

return dp[n];

// Driver Code

int main()

int n = 3;

cout << "Number of structurally Unique BST with " <<

n << " keys are : " << numberOfBST(n) << "\n";

return 0;

// This code is contributed by Aditya kumar (adityakumar129)

Output:

Number of structurally Unique BST with 3 keys are : 5

Time Complexity: O(n2)

Space Complexity: O(n)

Mark as Read

Report An IssueIf you are facing any i

Maximum sum with no two consecutive

Given an array arr[] of positive numbers, The task is to find the maximum sum of a subsequence such
that no 2 numbers in the sequence should be adjacent in the array.

Examples:

Input: arr[] = {5, 5, 10, 100, 10, 5}

Output: 110
Explanation: Pick the subsequence {5, 100, 5}.
The sum is 110 and no two elements are adjacent. This is the highest possible sum.

Input: arr[] = {3, 2, 7, 10}

Output: 13
Explanation: The subsequence is {3, 10}. This gives sum = 13.
This is the highest possible sum of a subsequence following the given criteria

Input: arr[] = {3, 2, 5, 10, 7}

Output: 15
Explanation: Pick the subsequence {3, 5, 7}. The sum is 15.

Naive Approach: Below is the idea to solve the problem:

Each element has two choices: either it can be the part of the subsequence with the highest sum or it
cannot be part of the subsequence. So to solve the problem, build all the subsequences of the array
and find the subsequence with the maximum sum such that no two adjacent elements are present in
the subsequence.

Time Complexity: O(2N)

Auxiliary Space: O(N)

Maximum sum such that no two elements are adjacent using Dynamic Programming:

• As seen above, each element has two choices. If one element is picked then its neighbours
cannot be picked. Otherwise, its neighbours may be picked or may not be.

• So the maximum sum till ith index has two possibilities: the subsequence includes arr[i] or it
does not include arr[i].

• If arr[i] is included then the maximum sum depends on the maximum subsequence sum till (i-
1)th element excluding arr[i-1].

• Otherwise, the maximum sum is the same as the maximum subsequence sum till (i-
1) where arr[i-1] may be included or excluded.

So build a 2D dp[N][2] array where dp[i][0] stores maximum subsequence sum till ith index
with arr[i] excluded and dp[i][1] stores the sum when arr[i] is included.
The values will be obtained by the following relations: dp[i][1] = dp[i-1][0] + arr[i] and dp[i][0] =
max(dp[i-1][0], dp[i-1][1])

Follow the steps mentioned below to implement the above idea:

 • If the size of the array is 1, then the answer is arr[0].

• Initialize the values of dp[0][0] = 0 and dp[0][1] = arr[0].

• Iterate from i = 1 to N-1:

o Fill the dp array as per the relation shown above.

• Return the maximum between dp[N-1][1] and dp[N-1][0] as that will be the answer.

Below is the implementation of the above approach.

C++Java

// C++ code to implement the approach

#include <bits/stdc++.h>

using namespace std;

// Function to find the maximum sum

int findMaxSum(vector<int> arr, int N)

// Declare dp array

int dp[N][2];

if (N == 1) {

return arr[0];

// Initialize the values in dp array

dp[0][0] = 0;

dp[0][1] = arr[0];

// Loop to find the maximum possible sum

for (int i = 1; i < N; i++) {

dp[i][1] = dp[i - 1][0] + arr[i];

dp[i][0] = max(dp[i - 1][1],

dp[i - 1][0]);

}
 // Return the maximum sum

return max(dp[N - 1][0], dp[N - 1][1]);

// Driver Code

int main()

// Creating the array

vector<int> arr = { 5, 5, 10, 100, 10, 5 };

int N = arr.size();

// Function call

cout << findMaxSum(arr, N) << endl;

return 0;

Output:

110

Time Complexity: O(N)

Auxiliary Space: O(N)

Space Optimized Approach: The above approach can be optimized to be done in constant space
based on the following observation:

As seen from the previous dynamic programming approach, the value of current states
(for ith element) depends upon only two states of the previous element. So instead of creating a 2D
array, we can use only two variables to store the two states of the previous element.

• Say excl stores the value of the maximum subsequence sum till i-1 when arr[i-1] is excluded
and

• incl stores the value of the maximum subsequence sum till i-1 when arr[i-1] is included.

• The value of excl for the current state( say excl_new) will be max(excl ,incl). And the value
of incl will be updated to excl + arr[i].

Illustration:

Consider arr[] = {5, 5, 10, 100, 10, 5}

Initially at i = 0: incl = 5, excl = 0

For i = 1: arr[i] = 5
=> excl_new = 5
=> incl = (excl + arr[i]) = 5
=> excl = excl_new = 5

For i = 2: arr[i] = 10
=> excl_new = max(excl, incl) = 5
=> incl = (excl + arr[i]) = 15
=> excl = excl_new = 5

For i = 3: arr[i] = 100

=> excl_new = max(excl, incl) = 15
=> incl = (excl + arr[i]) = 105
=> excl = excl_new = 15

For i = 4: arr[i] = 10
=> excl_new = max(excl, incl) = 105
=> incl = (excl + arr[i]) = 25
=> excl = excl_new = 105

For i = 5: arr[i] = 5
=> excl_new = max(excl, incl) = 105
=> incl = (excl + arr[i]) = 110
=> excl = excl_new = 105

So, answer is max(incl, excl) = 110

Follow the steps mentioned below to implement the above approach:

• Initialize incl and excl with arr[0] and 0 respectively.

• Iterate from i = 1 to N-1:

o Update the values of incl and excl as mentioned above.

• Return the maximum of incl and excl after the iteration is over as the answer.

Below is the implementation of the above approach.

C++Java

// C++ code to implement the above approach

#include <bits/stdc++.h>

using namespace std;

// Function to return max sum such that

// no two elements are adjacent

int FindMaxSum(vector<int> arr, int n)

int incl = arr[0];

int excl = 0;

int excl_new;

int i;

for (i = 1; i < n; i++) {

// Current max excluding i

excl_new = max(incl, excl);

// Current max including i

incl = excl + arr[i];

excl = excl_new;

// Return max of incl and excl

return max(incl, excl);

// Driver code

int main()

vector<int> arr = { 5, 5, 10, 100, 10, 5 };

int N = arr.size();

// Function call

cout << FindMaxSum(arr, N);

return 0;

// This approach is contributed by Debanjan

Output

110

Time Complexity: O(N)

Auxiliary Space: O(1).

Mark as Read

Report An IssueIf you are facing any i

Subset Sum Problem

Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set
with sum equal to given sum.

Example:

Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 9

Output: True
There is a subset (4, 5) with sum 9.

Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 30

Output: False
There is no subset that add up to 30.

Approach using Recursion.

Approach: For the recursive approach we will consider two cases.

1. Consider the last element and now the required sum = target sum - value of 'last'
element and number of elements = total elements - 1

2. Leave the 'last' element and now the required sum = target sum and number of elements =
total elements - 1

Following is the recursive formula for isSubsetSum() problem.

isSubsetSum(set, n, sum) = isSubsetSum(set, n-1, sum) || isSubsetSum(set, n-1, sum-set[n-1])

Base Cases:
isSubsetSum(set, n, sum) = false, if sum > 0 and n == 0
isSubsetSum(set, n, sum) = true, if sum == 0

Let's take a look at the simulation of above approach-:

set[]={3, 4, 5, 2}
sum=9
(x, y)= 'x' is the left number of elements,
'y' is the required sum

(4, 9)
{True}
/ \
(3, 6) (3, 9)

/ \ / \
(2, 2) (2, 6) (2, 5) (2, 9)
{True}
/ \
(1, -3) (1, 2)
{False} {True}
 / \
(0, 0) (0, 2)
{True} {False}

Python

def countSubsetSum(arr,n,sum):

if n==0:

if sum==0:

return 1

else:

return 0

return countSubsetSum(arr,n-1,sum) + countSubsetSum(arr,n-1,sum-arr[n-1])

arr = [1,2,3,5,6,7]

n=6

sum = 8

print(countSubsetSum(arr,n,sum))

Output:

3
Complexity Analysis: The above solution may try all subsets of given set in worst case. Therefore
time complexity of the above solution is exponential. The problem is in-fact NP-Complete (There is no
known polynomial time solution for this problem).

Mark as Read

Report An IssueIf you are facing any i

Matrix Chain Multiplication

Given the dimension of a sequence of matrices in an array arr[], where the dimension of
the ith matrix is (arr[i-1] * arr[i]), the task is to find the most efficient way to multiply these matrices
together such that the total number of element multiplications is minimum.

Examples:

Input: arr[] = {40, 20, 30, 10, 30}

Output: 26000
Explanation:There are 4 matrices of dimensions 40x20, 20x30, 30x10, 10x30.
Let the input 4 matrices be A, B, C and D.
The minimum number of multiplications are obtained by
putting parenthesis in following way (A(BC))D.
The minimumm is 20*30*10 + 40*20*10 + 40*10*30

Input: arr[] = {1, 2, 3, 4, 3}

Output: 30
Explanation: There are 4 matrices of dimensions 1x2, 2x3, 3x4, 4x3.
Let the input 4 matrices be A, B, C and D.
The minimum number of multiplications are obtained by
putting parenthesis in following way ((AB)C)D.
The minimum number is 1*2*3 + 1*3*4 + 1*4*3 = 30

Input: arr[] = {10, 20, 30}

Output: 6000
Explanation: There are only two matrices of dimensions 10x20 and 20x30.
So there is only one way to multiply the matrices, cost of which is 10*20*30

Matrix Chain Multiplication using Recursion:

We can solve the problem using recursion based on the following facts and observations:

Two matrices of size m*n and n*p when multiplied, they generate a matrix of size m*p and the
number of multiplications performed are m*n*p.

Now, for a given chain of N matrices, the first partition can be done in N-1 ways. For example,
sequence of matrices A, B, C and D can be grouped as (A)(BCD), (AB)(CD) or (ABC)(D) in these 3
ways.

So a range [i, j] can be broken into two groups like {[i, i+1], [i+1, j]}, {[i, i+2], [i+2, j]}, . . . , {[i, j-1], [j-
1, j]}.

• Each of the groups can be further partitioned into smaller groups and we can find the total
required multiplications by solving for each of the groups.

• The minimum number of multiplications among all the first partitions is the required answer.

Follow the steps mentioned below to implement the approach:

• Create a recursive function that takes i and j as parameters that determines the range of a
group.
 o Iterate from k = i to j to partition the given range into two groups.

o Call the recursive function for these groups.

o Return the minimum value among all the partitions as the required minimum
number of multiplications to multiply all the matrices of this group.

• The minimum value returned for the range 0 to N-1 is the required answer.

Below is the implementation of the above approach.

C++Java

// C++ code to implement the

// matrix chain multiplication using recursion

#include <bits/stdc++.h>

using namespace std;

// Matrix Ai has dimension p[i-1] x p[i]

// for i = 1 . . . n

int MatrixChainOrder(int p[], int i, int j)

if (i == j)

return 0;

int k;

int mini = INT_MAX;

int count;

// Place parenthesis at different places

// between first and last matrix,

// recursively calculate count of multiplications

// for each parenthesis placement

// and return the minimum count

for (k = i; k < j; k++)

count = MatrixChainOrder(p, i, k)
 + MatrixChainOrder(p, k + 1, j)

+ p[i - 1] * p[k] * p[j];

mini = min(count, mini);

// Return minimum count

return mini;

// Driver Code

int main()

int arr[] = { 1, 2, 3, 4, 3 };

int N = sizeof(arr) / sizeof(arr[0]);

// Function call

cout << "Minimum number of multiplications is "

<< MatrixChainOrder(arr, 1, N - 1);

return 0;

// This code is contributed by Shivi_Aggarwal

Output

Minimum number of multiplications is 30

The time complexity of the solution is exponential

Auxiliary Space: O(1)

Dynamic Programming Solution for Matrix Chain Multiplication using Memoization:

Below is the recursion tree for the 2nd example of the above recursive approach:
If observed carefully you can find the following two properties:

1) Optimal Substructure: In the above case, we are breaking the bigger groups into smaller
subgroups and solving them to finally find the minimum number of multiplications. Therefore, it can
be said that the problem has optimal substructure property.

2) Overlapping Subproblems: We can see in the recursion tree that the same subproblems are called
again and again and this problem has the Overlapping Subproblems property.

So Matrix Chain Multiplication problem has both properties of a dynamic programming problem. So
recomputations of same subproblems can be avoided by constructing a temporary array dp[][] in a
bottom up manner.

Follow the below steps to solve the problem:

• Build a matrix dp[][] of size N*N for memoization purposes.

• Use the same recursive call as done in the above approach:

o When we find a range (i, j) for which the value is already calculated, return the
minimum value for that range (i.e., dp[i][j]).

o Otherwise, perform the recursive calls as mentioned earlier.

• The value stored at dp[0][N-1] is the required answer.

Below is the implementation of the above approach

C++Java

// C++ program using memoization

#include <bits/stdc++.h>

using namespace std;

int dp[100][100];
// Function for matrix chain multiplication

int matrixChainMemoised(int* p, int i, int j)

if (i == j)

return 0;

if (dp[i][j] != -1)

return dp[i][j];

dp[i][j] = INT_MAX;

for (int k = i; k < j; k++)

dp[i][j] = min(

dp[i][j], matrixChainMemoised(p, i, k)

+ matrixChainMemoised(p, k + 1, j)

+ p[i - 1] * p[k] * p[j]);

return dp[i][j];

int MatrixChainOrder(int* p, int n)

int i = 1, j = n - 1;

return matrixChainMemoised(p, i, j);

// Driver Code

int main()

{
 int arr[] = { 1, 2, 3, 4 };

int n = sizeof(arr) / sizeof(arr[0]);

memset(dp, -1, sizeof dp);

cout << "Minimum number of multiplications is "

<< MatrixChainOrder(arr, n);

// This code is contributed by Sumit_Yadav

Output

Minimum number of multiplications is 18

Time Complexity: O(N3 )

Auxiliary Space: O(N2) ignoring recursion stack space

Dynamic Programming Solution for Matrix Chain Multiplication using Tabulation (Iterative
Approach):

In iterative approach, we initially need to find the number of multiplications required to multiply two
adjacent matrices. We can use these values to find the minimum multiplication required for matrices
in a range of length 3 and further use those values for ranges with higher lengths.

Build on the answer in this manner till the range becomes [0, N-1].

Follow the steps mentioned below to implement the idea:

• Iterate from l = 2 to N-1 which denotes the length of the range:

o Iterate from i = 0 to N-1:

▪ Find the right end of the range (j) having l matrices.

▪ Iterate from k = i+1 to j which denotes the point of partition.

▪ Multiply the matrices in range (i, k) and (k, j).

▪ This will create two matrices with dimensions arr[i-

1]*arr[k] and arr[k]*arr[j].

▪ The number of multiplications to be performed to multiply these

two matrices (say X) are arr[i-1]*arr[k]*arr[j].

▪ The total number of multiplications is dp[i][k]+ dp[k+1][j] + X.

• The value stored at dp[1][N-1] is the required answer.

Below is the implementation of the above approach.

C++Java

// See the Cormen book for details of the

// following algorithm

#include <bits/stdc++.h>

using namespace std;

// Matrix Ai has dimension p[i-1] x p[i]

// for i = 1..n

int MatrixChainOrder(int p[], int n)

/* For simplicity of the program, one

extra row and one extra column are

allocated in m[][]. 0th row and 0th

column of m[][] are not used */

int m[n][n];

int i, j, k, L, q;

/* m[i, j] = Minimum number of scalar

multiplications needed to compute the

matrix A[i]A[i+1]...A[j] = A[i..j] where

dimension of A[i] is p[i-1] x p[i] */

// cost is zero when multiplying

// one matrix.

for (i = 1; i < n; i++)

m[i][i] = 0;

// L is chain length.

for (L = 2; L < n; L++)

 {

for (i = 1; i < n - L + 1; i++)

j = i + L - 1;

m[i][j] = INT_MAX;

for (k = i; k <= j - 1; k++)

// q = cost/scalar multiplications

q = m[i][k] + m[k + 1][j]

+ p[i - 1] * p[k] * p[j];

if (q < m[i][j])

m[i][j] = q;

return m[1][n - 1];

// Driver Code

int main()

int arr[] = { 1, 2, 3, 4 };

int size = sizeof(arr) / sizeof(arr[0]);

cout << "Minimum number of multiplications is "

<< MatrixChainOrder(arr, size);

getchar();

return 0;

}
// This code is contributed

// by Akanksha Rai

Output

Minimum number of multiplications is 18

Time Complexity: O(N3 )

Auxiliary Space: O(N2)

Mark as Read

Report An IssueIf you are facing any i

Palindrome Partitioning

Given a string, a partitioning of the string is a palindrome partitioning if every substring of the
partition is a palindrome. For example, "aba|b|bbabb|a|b|aba" is a palindrome partitioning of
"ababbbabbababa". Determine the fewest cuts needed for a palindrome partitioning of a given
string. For example, minimum of 3 cuts are needed for "ababbbabbababa". The three cuts are
"a|babbbab|b|ababa". If a string is a palindrome, then minimum 0 cuts are needed. If a string of
length n containing all different characters, then minimum n-1 cuts are needed.

Examples :

Input : str = "geek"

Output : 2
We need to make minimum 2 cuts, i.e., "g ee k"
Input : str = "aaaa"
Output : 0
The string is already a palindrome.
Input : str = "abcde"
Output : 4
Input : str = "abbac"
Output : 1

This problem is a variation of Matrix Chain Multiplication problem. If the string is a palindrome, then
we simply return 0. Else, like the Matrix Chain Multiplication problem, we try making cuts at all
possible places, recursively calculate the cost for each cut and return the minimum value.
Let the given string be str and minPalPartion() be the function that returns the fewest cuts needed
for palindrome partitioning. following is the optimal substructure property.

Using Recursion

// i is the starting index and j is the ending index. i must be passed as 0 and j as n-1

minPalPartion(str, i, j) = 0 if i == j. // When string is of length 1.

minPalPartion(str, i, j) = 0 if str[i..j] is palindrome.

// If none of the above conditions is true, then minPalPartion(str, i, j) can be

// calculated recursively using the following formula.

minPalPartion(str, i, j) = Min { minPalPartion(str, i, k) + 1 +

minPalPartion(str, k+1, j) }
 where k varies from i to j-1

C++Java

// C++ Code for Palindrome Partitioning

// Problem

#include <bits/stdc++.h>

using namespace std;

bool isPalindrome(string String, int i, int j)

while(i < j)

if(String[i] != String[j])

return false;

i++;

j--;

return true;

int minPalPartion(string String, int i, int j)

if( i >= j || isPalindrome(String, i, j) )

return 0;

int ans = INT_MAX, count;

for(int k = i; k < j; k++)

count = minPalPartion(String, i, k) +

minPalPartion(String, k + 1, j) + 1;

ans = min(ans, count);

return ans;
}

// Driver code

int main() {

string str = "ababbbabbababa";

cout << "Min cuts needed for " <<

"Palindrome Partitioning is " <<

minPalPartion(str, 0, str.length() - 1) << endl;

return 0;

// This code is contributed by rag2127

Output:

Min cuts needed for Palindrome Partitioning is 3

Time Complexity: O(2n)

Auxiliary Space: O(n)

Using Dynamic Programming :
Following is Dynamic Programming solution. It stores the solutions to subproblems in two arrays P[][]
and C[][], and reuses the calculated values.

C++Java

// Dynamic Programming Solution for

// Palindrome Partitioning Problem

#include <bits/stdc++.h>

using namespace std;

// Returns the minimum number of cuts

// needed to partition a string

// such that every part is a palindrome

int minPalPartion(string str)

// Get the length of the string

int n = str.length();

/* Create two arrays to build the solution

 in bottom up manner

C[i][j] = Minimum number of cuts needed for

palindrome partitioning

of substring str[i..j]

P[i][j] = true if substring str[i..j] is

palindrome, else false

Note that C[i][j] is 0 if P[i][j] is true */

int C[n][n];

bool P[n][n];

// Every substring of length 1 is a palindrome

for (int i = 0; i < n; i++) {

P[i][i] = true;

C[i][i] = 0;

/* L is substring length. Build the

solution in bottom up manner by

considering all substrings of

length starting from 2 to n.

The loop structure is same as Matrix

Chain Multiplication problem

( See https:// www.geeksforgeeks.org/matrix-chain-multiplication-dp-8/ )*/

for (int L = 2; L <= n; L++) {

// For substring of length L, set

// different possible starting indexes

for (int i = 0; i < n - L + 1; i++) {

int j = i + L - 1; // Set ending index

// If L is 2, then we just need to

 // compare two characters. Else

// need to check two corner characters

// and value of P[i+1][j-1]

if (L == 2)

P[i][j] = (str[i] == str[j]);

else

P[i][j] = (str[i] == str[j]) && P[i + 1][j - 1];

// IF str[i..j] is palindrome, then C[i][j] is 0

if (P[i][j] == true)

C[i][j] = 0;

else {

// Make a cut at every possible

// location starting from i to j,

// and get the minimum cost cut.

C[i][j] = INT_MAX;

for (int k = i; k <= j - 1; k++)

C[i][j] = min(C[i][j], C[i][k] + C[k + 1][j] + 1);

// Return the min cut value for

// complete string. i.e., str[0..n-1]

return C[0][n - 1];

// Driver code

int main()

{
 string str = "ababbbabbababa";

cout << "Min cuts needed for Palindrome"

" Partitioning is "

<< minPalPartion(str);

return 0;

// This code is contributed by rathbhupendra

Output:

Min cuts needed for Palindrome Partitioning is 3

Time Complexity: O(n3)

Auxiliary Space: O(n2)

We can optimize the above code a bit further. Instead of calculating C[i] separately in O(n^2), we can
do it with the P[i] itself. Below is the highly optimized code of this problem:

C++Java

#include <bits/stdc++.h>

using namespace std;

int minCut(string a)

int cut[a.length()];

bool palindrome[a.length()][a.length()];

memset(palindrome, false, sizeof(palindrome));

for (int i = 0; i < a.length(); i++)

int minCut = i;

for (int j = 0; j <= i; j++)

if (a[i] == a[j] && (i - j < 2 || palindrome[j + 1][i - 1]))

palindrome[j][i] = true;
 minCut = min(minCut, j == 0 ? 0 : (cut[j - 1] + 1));

cut[i] = minCut;

return cut[a.length() - 1];

// Driver code

int main()

cout << minCut("aab") << endl;

cout << minCut("aabababaxx") << endl;

return 0;

// This code is contributed by divyesh072019.

Time Complexity: O(n2)

Auxiliary Space: O(n2)

An optimization to above approach

In the above approach, we can calculate the minimum cut while finding all palindromic substring. If
we find all palindromic substring 1st and then we calculate minimum cut, time complexity will reduce
to O(n2).
Thanks for Vivek for suggesting this optimization.

C++Java

// Dynamic Programming Solution for Palindrome Partitioning Problem

#include <iostream>

#include <bits/stdc++.h>

#include <string.h>

using namespace std;

// A utility function to get minimum of two integers

int min(int a, int b) { return (a < b) ? a : b; }

// Returns the minimum number of cuts needed to partition a string

// such that every part is a palindrome

int minPalPartion(char* str)

// Get the length of the string

int n = strlen(str);

/* Create two arrays to build the solution in bottom-up manner

C[i] = Minimum number of cuts needed for a palindrome partitioning

of substring str[0..i]

P[i][j] = true if substring str[i..j] is palindrome, else false

Note that C[i] is 0 if P[0][i] is true */

int C[n];

bool P[n][n];

int i, j, k, L; // different looping variables

// Every substring of length 1 is a palindrome

for (i = 0; i < n; i++) {

P[i][i] = true;

/* L is substring length. Build the solution in bottom up manner by

considering all substrings of length starting from 2 to n. */

for (L = 2; L <= n; L++) {

// For substring of length L, set different possible starting indexes

for (i = 0; i < n - L + 1; i++) {

j = i + L - 1; // Set ending index

 // If L is 2, then we just need to compare two characters. Else

// need to check two corner characters and value of P[i+1][j-1]

if (L == 2)

P[i][j] = (str[i] == str[j]);

else

P[i][j] = (str[i] == str[j]) && P[i + 1][j - 1];

for (i = 0; i < n; i++) {

if (P[0][i] == true)

C[i] = 0;

else {

C[i] = INT_MAX;

for (j = 0; j < i; j++) {

if (P[j + 1][i] == true && 1 + C[j] < C[i])

C[i] = 1 + C[j];

// Return the min cut value for complete string. i.e., str[0..n-1]

return C[n - 1];

// Driver program to test above function

int main()

char str[] = "ababbbabbababa";

cout <<"Min cuts needed for Palindrome Partitioning is " << minPalPartion(str);
 return 0;

// This code is contributed by shivanisinghss2110

Output:

Min cuts needed for Palindrome Partitioning is 3

Time Complexity: O(n2)

Auxiliary Space: O(n2)

Using Memorization to solve this problem.

The basic idea is to cache the intermittent results calculated in recursive functions. We can put these
results into a hashmap/unordered_map.
To calculate the keys for the Hashmap we will use the starting and end index of the string as the key
i.e. ["start_index".append("end_index")] would be the key for the Hashmap.

Below is the implementation of above approach :

C++Java

// Using memoizatoin to solve the partition problem.

#include <bits/stdc++.h>

using namespace std;

// Function to check if input string is palindrome or not

bool ispalindrome(string input, int start, int end)

// Using two pointer technique to check palindrome

while (start < end) {

if (input[start] != input[end])

return false;

start++;

end--;

return true;

// Function to find keys for the Hashmap

string convert(int a, int b)

return to_string(a) + "" + to_string(b);

// Returns the minimum number of cuts needed to partition a string

// such that every part is a palindrome

int minpalparti_memo(string input, int i, int j, unordered_map<string, int>& memo)

if (i > j)

return 0;

// Key for the Input String

string ij = convert(i, j);

// If the no of partitions for string "ij" is already calculated

// then return the calculated value using the Hashmap

if (memo.find(ij) != memo.end()) {

return memo[ij];

// Every String of length 1 is a palindrome

if (i == j) {

memo[ij] = 0;

return 0;

if (ispalindrome(input, i, j)) {

memo[ij] = 0;

return 0;

int minimum = INT_MAX;

// Make a cut at every possible location starting from i to j

for (int k = i; k < j; k++) {

 int left_min = INT_MAX;

int right_min = INT_MAX;

string left = convert(i, k);

string right = convert(k + 1, j);

// If left cut is found already

if (memo.find(left) != memo.end()) {

left_min = memo[left];

// If right cut is found already

if (memo.find(right) != memo.end()) {

right_min = memo[right];

// Recursively calculating for left and right strings

if (left_min == INT_MAX)

left_min = minpalparti_memo(input, i, k, memo);

if (right_min == INT_MAX)

right_min = minpalparti_memo(input, k + 1, j, memo);

// Taking minimum of all k possible cuts

minimum = min(minimum, left_min + 1 + right_min);

memo[ij] = minimum;

// Return the min cut value for complete string.

return memo[ij];

int main()

string input = "ababbbabbababa";

 unordered_map<string, int> memo;

cout << minpalparti_memo(input, 0, input.length() - 1, memo) << endl;

return 0;

Time Complexity: O(n3)

Auxiliary Space: O(n2)

Mark as Read

Report An IssueIf you are facing any i

Allocate Minimum Pages

Given a number of pages in N different books and M students. The books are arranged in ascending
order of the number of pages. Every student is assigned to read some consecutive books. The task is
to assign books in such a way that the maximum number of pages assigned to a student is minimum.

Example :

Input : pages[] = {12, 34, 67, 90} , m = 2

Output : 113

Explanation: There are 2 number of students. Books can be distributed in following fashion :
1) [12] and [34, 67, 90]
Max number of pages is allocated to student ‘2’ with 34 + 67 + 90 = 191 pages
2) [12, 34] and [67, 90] Max number of pages is allocated to student ‘2’ with 67 + 90 = 157 pages
3) [12, 34, 67] and [90] Max number of pages is allocated to student ‘1’ with 12 + 34 + 67 = 113 pages
Of the 3 cases, Option 3 has the minimum pages = 113.

Naive Approach:

C++Java

#include <bits/stdc++.h>

using namespace std;

int sum(int arr[],int b, int e){

int s=0;

for(int i=b;i<=e;i++)

s+=arr[i];

return s;

int minPages(int arr[],int n, int k){

if(k==1)

return sum(arr,0,n-1);

if(n==1)

return arr[0];

int res=INT_MAX;
 for(int i=1;i<n;i++){

res=min(res,max(minPages(arr,i,k-1),sum(arr,i,n-1)));

return res;

int main()

int arr[]={10,20,10,30};

int n=sizeof(arr)/sizeof(arr[0]);

int k=2;

cout<<minPages(arr,n,k);

Output:

40

Approach: A Binary Search method for solving the book allocation problem:

Case 1: When no valid answer exists.

If the number of students is greater than the number of books (i.e, M > N), In this case at least 1
student will be left to which no book has been assigned.

Case 2: When a valid answer exists.

The maximum possible answer could be when there is only one student. So, all the book will be
assigned to him and the result would be the sum of pages of all the books.

The minimum possible answer could be when number of student is equal to the number of book (i.e,
M == N) , In this case all the students will get at most one book. So, the result would be the maximum
number of pages among them (i.e, minimum(pages[])).

Hence, we can apply binary search in this given range and each time we can consider the mid value
as the maximum limit of pages one can get. And check for the limit if answer is valid then update the
limit accordingly.

Below is the implementation of the above idea:

• Initialise the start to minimum(pages[]) and end = sum of pages[],

• Do while start <= end

 o Calculate the mid and check if mid number of pages can assign any student by
satisfying the given condition such that all students will get at least one book. Follow
the steps to check for validity.

▪ Initialise the studentsRequired = 1 and curr_sum = 0 for sum of consecutive

pages of book

▪ Iterate over all books or say pages[]

▪ Add the pages to curr_sum and check curr_sum > curr_min then
increment the count of studentRequired by 1.

▪ Check if the studentRequired > M, return false.

▪ Return true.

o If mid is valid then, update the result and move the end = mid – 1

o Otherwise, move the start = mid + 1

• Finally, return the result.

Below is the implementation of the above approach:

C++Java

// C++ program for optimal allocation of pages

#include <bits/stdc++.h>

using namespace std;

// Utility function to check if current minimum value

// is feasible or not.

bool isPossible(int arr[], int n, int m, int curr_min)

int studentsRequired = 1;

int curr_sum = 0;

// iterate over all books

for (int i = 0; i < n; i++) {

// check if current number of pages are greater

// than curr_min that means we will get the result

// after mid no. of pages

if (arr[i] > curr_min)

 return false;

// count how many students are required

// to distribute curr_min pages

if (curr_sum + arr[i] > curr_min) {

// increment student count

studentsRequired++;

// update curr_sum

curr_sum = arr[i];

// if students required becomes greater

// than given no. of students,return false

if (studentsRequired > m)

return false;

// else update curr_sum

else

curr_sum += arr[i];

return true;

// function to find minimum pages

int findPages(int arr[], int n, int m)

long long sum = 0;

// return -1 if no. of books is less than

// no. of students
if (n < m)

return -1;

// Count total number of pages

for (int i = 0; i < n; i++)

sum += arr[i];

// initialize start as 0 pages and end as

// total pages

int start = 0, end = sum;

int result = INT_MAX;

// traverse until start <= end

while (start <= end) {

// check if it is possible to distribute

// books by using mid as current minimum

int mid = (start + end) / 2;

if (isPossible(arr, n, m, mid)) {

// update result to current distribution

// as it's the best we have found till now.

result = mid;

// as we are finding minimum and books

// are sorted so reduce end = mid -1

// that means

end = mid - 1;

else

// if not possible means pages should be

// increased so update start = mid + 1

 start = mid + 1;

// at-last return minimum no. of pages

return result;

// Drivers code

int main()

// Number of pages in books

int arr[] = { 12, 34, 67, 90 };

int n = sizeof arr / sizeof arr[0];

int m = 2; // No. of students

cout << "Minimum number of pages = "

<< findPages(arr, n, m) << endl;

return 0;

Output

Minimum number of pages = 113

Time Complexity: O(N*log(N)), Where N is the total number of pages in the book.
Auxiliary Space: O(1)

Mark as Read

Report An IssueIf you are facing any i