Quote:
Algorithm to calculate the maximum product of any n-1 elements in the array in O(n) time complexity for only positive integers
This is your job to find/create algorithms that solve problems, homeworks is made for practicing.
Your task is to find an efficient algorithm.
Quote:
I have tried solving using Brute force method. The complexity comes out to be o(n^2)
Brute force is the most inefficient algorithm, but at least you did a solution.
But the whole thing is about making you using your brain, and explorer the problem from different aspects until you find something useful.
- First study/master the subject "multiplication", I hope you have mastered it a few years ago.
- think of different ways to ask the question.
Which integer do I have to remove from the list to get maximum product?
- Take a sheet of paper and a pencil and start with a small sample. Solve by hand.
Which integer should I remove to get maximum product? 1 2 3 4 5
Why removing this integer is the solution?
Do you need to calculate all 5 five products to find the answer?
What if list is 1 2 3 4 ... 96 97 98 99.
by this point, you should have found that the solution is so simple that you wonder why you didn't find alone.
- Learn one or more analyze methods, E.W. Djikstra/N. Wirth
Stepwize Refinement/top-Down method is a good start.
Structured Programming.pdf[
^]
https://en.wikipedia.org/wiki/Top-down_and_bottom-up_design[
^]
https://en.wikipedia.org/wiki/Structured_programming[
^]
https://en.wikipedia.org/wiki/Edsger_W._Dijkstra[
^]
https://www.cs.utexas.edu/users/EWD/ewd03xx/EWD316.PDF[
^]