# Daily Coding Challenge #30

This is a series of Daily Coding Challenge. Each day I show a few solutions written in C++. The questions are from coding practice/contest sites such as HackerRank, LeetCode, Codeforces, Atcoder and etc.

``````/*
LeetCode - Burst Balloons

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note:

You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100
Example:

Input: [3,1,5,8]
Output: 167
Explanation: nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->    --> []
coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167
*/

class Solution {
public:
int maxCoins(vector<int>& nums) {
int n = (int)nums.size();
vector<vector<int>> dp(n+1, vector<int>(n+1,-1));
vector<int> nums1(n+2,1);
for(int i=0;i<n;i++){
// 1,nums,nums,..,nums[n-1],1
nums1[i+1]=nums[i];
}
return f(nums1,dp,1,n);
}
private:
int f(vector<int>& nums, vector<vector<int>>& dp, int left, int right){
if(left>right) return 0;
if(dp[left][right]!=-1) return dp[left][right];
for(int k=left;k<=right; k++){
dp[left][right] = max(
dp[left][right],
// left part: from starting point to the burst point - 1
f(nums,dp,left,k-1) +
// middle part: e.g. k=1: 1*nums*1 bc balloons from [left,k-1] and from [k+1,end] are bursted
nums[left-1]*nums[k]*nums[right+1] +
// right part: from the burst point + 1 to the end
f(nums,dp,k+1,right)
);
}
return dp[left][right];
}
};
``````

``````/*
LeetCode - Plus One

Given a non-empty array of digits representing a non-negative integer, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.
Example 2:

Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.
*/

class Solution {
public:
vector<int> plusOne(vector<int>& d) {
int n=(int)d.size();
int c=1;
for(int i=n-1;i>=0;i--){
if(d[i]!=9){
// add 1 to value at the current index
d[i]+=1;
return d;
}

if(i==0&&d[i]==9) {
// reach the end
// [9,9,9] -> [1,0,0,0]
d[i]=0;
d.insert(d.begin(),1);
} else {
// make it zero
d[i]=0;
}
}
return d;
}
};
``````

``````/*
LeetCode - Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Example 1:

Input: [1,3,5,6], 5
Output: 2
Example 2:

Input: [1,3,5,6], 2
Output: 1
Example 3:

Input: [1,3,5,6], 7
Output: 4
Example 4:

Input: [1,3,5,6], 0
Output: 0

*/

class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
// use lower_bound to find out the first element which has a value not less than target
// -nums.begin() to convert it back to int
return lower_bound(nums.begin(),nums.end(),target)-nums.begin();
}
};
``````

The source code is available in corresponding repo below. Star and watch for timely updates!

## wingkwong / atcoder

### Discussion  Anup Aglawe

Nice set of questions.
I was wondering that in the balloons questions, ( or in general ) how do we figure out that greedy doesn't work?
Haven't put much effort though, but my first thoughts were to burst smallest weight balloon and so on.  