Did this in O(n). Still getting TLE in 1 testcase

#1

https://hack.codingblocks.com/contests/c/452/721
https://ide.codingblocks.com/#/s/13832

#2

Why are you running loop for whole n?You don’t really need this.
Think more about it.

#3

Why to make an array of n?You are not going to reach each number between 1 to n as you are jumping from n to n/2,n/3,n/4.So better use a map for dp logic.
https://ide.codingblocks.com/#/s/13843
Go through this once and then ask if needed.
One more thing ,watch this video for better understanding of time constraints -


1 second is required for n =10^8.

#4

Hey ! you are running loop from 1 to n which is not optimised and you have also created an array of size n (n<=1e9)which is not possible (you are supposed to create an array of max size 10^7-10^8,thats why you are getting TLE verdict.
You can use map concept and no need to run the loop for all i lleass than equal to n, you can just call recursion on its subpart. Okay see this -->> I have modified ur code here. https://ide.codingblocks.com/#/s/13858

#5

Thenks Yogesh-Sheoran-18138

#6

Thenks O17LPOLC0033 !!!