PROBLEM LINK:
Author: Aniket Marlapalle Tester: Devamanyu Hazarika Editorialist: Devamanyu Hazarika
DIFFICULTY:
EASY
PROBLEM:
The problem defines a game and asks to find the maximum sum that can be obtained.
EXPLANATION:
It can be inferred from the rules that if played in an optimised manner, the player will always try to choose an index and pick all its multiples amongst the array indices (This is valid because all the numbers in the array are positive numbers).
Thus the player willl greedily choose an index and add the sum of all multiples of that index and store the sum. The player checks this will all indices and finally prints the largest sum. It is important to note that the player can’t select the first index as a starting point (Had this been allowed, the answer would have simply been the total sum of all elements in the array).
Thus strating from index 2, check sum of elements lying in this multiple indices and print the maximum sum.
To figure out the Time Complexity, it can be noted that if started from 2, about N/2 jumps need to be made. Then from 3, N/3 jumps and so on. This comes out as a the following series - N/2 + N/3 + N/4 … + 1 which can be proven to be in order of O(NlogN ) where N is the total number of elements in the array.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.