CodeChef October Long Challenge 2019 [MSV] Chef and Maximum Star Value - Discussion . Approach. Code
This video very clearly explains the problem statement , logic to solve the problem and also the correct solution.
What is the problem statement?
We are given a sequence of integers and for each index, we calculate it’s star value. Star value is the number of indexes j less than i such that A[j]%A[i]==0.
How to approach the problem?
O(n^2) solution is very simple and explained in the first half of the video.
O(N. sqrt(n)) solution
1. Calculate factors of each number in O(sqrt(n)) time.
2. In another array treat these factors as indexes and increment their values as they arrive.
3. Keep a variable to hold the current max star value
4. Few corner cases are explained in the video.
5. Finally, print the max star value.
Do not forget to share the with your coder friends.
Learn coding with experts: http://bit.ly/2VFH8c9