bertram_gilfoyle
BAN USER
- 16
1of 1 vote
AnswersIn a garden, there are several apples trees planted in a grid format. Each point (i,j) in the grid has |i| + |j| apples.
Allie can buy a square plot centred at (0,0). Find the minimum perimeter of the plot (1 unit having length = 1) such that she can collect at
least X apples. All plants on the perimeter of the plot are also included.
Sample:
- bertram_gilfoyle in IndiaInput = 1 Output = 8 input = 11 Output = 8 Input = 13 Output = 16
| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm
- 0
Repchristinetcollazoc, Software Analyst
I am a pediatric nurse.I administer directly procedures and medicines to children according to prescribed I also continually assess ...
- 50
Repryandchinkle, Android Engineer at ABC TECH SUPPORT
I was born in Northridge USA, I like photography, I have wide photos collection of wildlife. I have many religious ...
- 0
RepEwaMariaa, Cloud Support Associate at Abs india pvt. ltd.
Hi, I am an Localization translator from New York,Travelling with company executives on foreign trips is the favorite part ...
Just came up with a simple idea of maintaining a sorted list.
- bertram_gilfoyle September 03, 2019So my algorithm would look like this.
(1) Initialize Sorted List
(2) Using binary search check the lower bound of the key to be inserted in the sorted list, if it is at x then put x in the span[i], (exception: if x == 0, then span[i] = -1)
So the sorted list would keep on growing, but the advantage is that it is simpler than maintaining a tree or a balanced BST. Moreover, it is always sorted and we can calculate the lower bound of an element to be inserted (also called lower bound insertion point) in logarithmic time.
If we maintain a dynamic array-like structure for the sorted list then insertion would be constant time.
Overall runtime should be under **nlogn** which is fairly satisfactory for this problem.
Please put your comments below.