Posts

Classic Dynamic Programming XI

-
Image
This is actually more of a memoization problem rather than a dynamic programming one. Basically just store in a "cache" the solution for any computed N. Check if it is already in the cache, if so, return it. Otherwise calculate the solution and store in the cache for later use. Code is down below, cheers, ACC. Minimum Cost to Split into Ones - LeetCode You are given an integer  n . In one operation, you may split an integer  x  into two positive integers  a  and  b  such that  a + b = x . The cost of this operation is  a * b . Return an integer denoting the  minimum  total cost required to split the integer  n  into  n  ones.   Example 1: Input:   n = 3 Output:   3 Explanation: One optimal set of operations is: x a b a + b a * b Cost 3 1 2 3 2 2 2 1 1 2 1 1 Thus, the minimum total cost is  2 + 1 = 3 . Example 2: Input:   n = 4 Output:   6 Explanation: One optimal set of operations is...
Post a Comment
Read more

Prefix Sum XI

-
Image
Prefix Sum together with Suffix Product. No need to use Big Integer for this problem (which would slow down the solution considerably), you can just use long and whenever the suffix product gets greater than the max prefix sum, you know that from that point onwards you won't have a possible solution, hence just keep setting the suffix product to -1. Also, the fact that zero isn't allowed as a potential array element simplifies the solution a bit. Code is down below, cheers, ACC. Find the Smallest Balanced Index - LeetCode You are given an integer array  nums . An index  i  is  balanced  if the sum of elements  strictly  to the left of  i  equals the product of elements  strictly  to the right of  i . If there are no elements to the left, the sum is considered as 0. Similarly, if there are no elements to the right, the product is considered as 1. Return an integer denoting the  smallest  balanced index. If no balanced ...
Post a Comment
Read more