I am getting WA for the problem DOMINOES. But I can't seem to figure anything wrong in my approach. My approach is as follows :
- Sort the dominoes from left to right on 'x'.
- For every Domino, calculate the last domino to the left which will falls if i push this domino to the left(max_left[i])
- For every Domino, calculate the first domino to its left such that when it falls to the right also makes this domino fall to the right(min_right[i])
- Recurrence Relation :
dp[i][L] = max_left[i] == 0 ? 1 : (1 + min(dp[max_left[i] — 1][L], dp[max_left[i] — 1][R]))
dp[i][R] = 1 + min(dp[i-1][L], dp[i-1][R]);
dp[i][R] = min_right[i] == 0 ? 1 : min(dp[i][R], dp[min_right[i]][R]);
answer is min(dp[n-1][L], dp[n-1][R]);

A Prime Array is an array which doesn't contain a pair of numbers whose product is a square of an integer.

For eg [1,2,3] is a Prime Array but [1,2,4] is not.

Explanation : 1*4 gives 4 which is square of 2.

Given an array of integers determine the minimum number of operations to convert the array to a Prime array.

NOTE: An operation consists of either increasing or decreasing any element of the array by 1 but the element should always be positive.

Constraints: Length of array <=100

1 <=Each integer in array <=1000000

Eg. Array => [1,1,2]

Minimum operations to convert [1,1,2] to [1,2,3] is 2.