Today lets discuss about another problem named Mixtures.
The problem maps to the below problem:
You are given an array of n numbers and you are allowed to add any two adjacent numbers at a time, such that the result produced is sum of the two added elements mod 100, and the cost of doing the addition is product of the two added elements. You are required to give the combination such that cost is minimized.
Solution: If we think about the problem it looks like a math problem which says you are given a1a2….an-1an and you need to add them together such that addition result is ai+aj/100 and cost is ai*aj, and you are told to return the combination with minimum cost.
Can it be done in O(N)?
I don’t know. But lets first go naive. Lets first discuss in how many ways the mixing/addition can be done. After little bit of thinking the problem maps to permutation/combination problem.
You can choose your first element out of n elements in n ways, and after choosing first element the next element you want to mix it with can be chosen in 2 ways since the two added element should be adjacent. After the process you will be remained with n-1 elements, again going with similar logic the process can be done in 2*(n -1) steps and so on till the array remains with one element. So the entire process with take 2*n + 2*(n-1) + ….. + 2*1 steps => n*(n-1) steps.
Now if you see the limit of n in the problem, it says n can go till 100. That means any algorithm till O(N3) is okay for us.