Quote:But when i am declaring array of size `1 000 000 000` compiler is saying std::bad_alloc
Your problem is that you did not analyze the problem, you are jumping strait to the second most simple minded solution which replaced the brute force solution by another brute force solution, in another way.
Think about it, if n= 1 000 000 000, the largest smaller value you will ever used is 500 000 000. Not a single value between those 2 values will ever be used to solve the problem.
Simply cascading the n/2 reduction will give you 30 values in worst case.
You have to find a way to avoid declaring the 1 000 000 000 values in an array or anything.