Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given list with positive and negative integers.We have to make each element greater than or equal to zero.There are two types of moves first increase all elements by 1 requires P unit of money, second increase a particular element by 1 requires 1 unit of money.

Find the minimum unit of money to make all elements greater than or equal to zero.

Integers limit $(-10)^9$ to $10^9$

List length - $10^5$

share|improve this question

1 Answer 1

up vote 3 down vote accepted

Why not just find the most negative element and increase all elements by $1$ enough times to get to zero? This is the minimum number of steps, though there may be other equally short paths.

Added: now that we are given that increasing all elements costs $P$, we are better off increasing all as long as there are more than $P$ that are negative. When exactly $P$ are negative, it is a breakeven, and when less are negative it is cheaper to increase them individually. So the new algorithm is: 1)find the $P^{\text{th}}$ most negative element. 2)increase all until it is zero 3)increase all the remaining negative ones individually until they reach zero.

share|improve this answer
    
But the OP wanted to minimize the cost of getting all the numbers to be nonnegative. With the list $\langle\,-7, -2, -1\,\rangle$, increasing all would cost $7P$, but increasing each individually would cost $7+2+1$ so if $P\le 10/7$ your technique would be cheapest, but if $P>10/7$ the second would be cheaper. It gets even more complicated.... –  Rick Decker Sep 11 '13 at 21:05
    
@RickDecker: That wasn't part of the question when I answered it. I'll update. –  Ross Millikan Sep 11 '13 at 21:09
    
i am sorry for updating the question after your answer Ross –  Vidyut Vyom Sep 12 '13 at 3:06

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.