def gcd(self, a, b):
if a % b == 0:
return self.gcd(b, a%b)
def canMeasureWater(self, x, y, z):
if z==0 or z == x+y:
if z > x + y :
if x == 0:
return z == y
if y == 0:
return z == x
if x == y:
return z == x
y_in = y if y > x else x
x_in = x if y > x else y
r = y_in % x_in
if r == 0:
return z % x_in == 0
return z % self.gcd(r, x_in) == 0
How about proving it by mathematical induction?
We want to show, if gas(1) + gas(2) + ... + gas(n) >= cost(1) + cost(2) + ...+ cost(n) then there is a path that goes though all stations.
Base case: n = 2, obviously it's correct.
Now, suppose for n = k, the proposition holds. Then for n = k + 1, its difference from n = k case is just adding gas(k+1) on the left hand side, and cost(k+1) on the right hand side. We know for n = k there is the path, so for n = k + 1 there is a path too. Thus proof is done.
Really nice proof!
To make the post easier to understand:
f(X) = 10^(lgX + 1) means that f(X) is the number of digits in number X, e.g. f(1) = 1, f(9) = 1, f(10) = 2
The post also didn't strictly distinguish between "string concatenation" and "multiplication", e.g.
"then XY = f(Y)X + Y" means:
concat(X,Y) = f(Y) * X + Y
The main idea of second proof is:
When you have a sorted sequence A, B, C, D, ..., then A must be the first part of the largest number. This can be proved by contradiction:
If A is not the first part of the largest number, then the largest number would be something like X....XAX....X (X represents other numbers). You can obtain a number no smaller than itself by swapping A with the number preceding it. You can continue this process until A becomes the first part of the number, and this number is larger than "the largest number", leading to a contradiction. (Note that the last swap that make A the first part of the number guarantees to increase the number, because the assumption "A is not the first part of the largest number")
Use the height of rectangles to represent the number of candies that the kids get. We will get a lot of peaks.
Every peak is independent. So we can divide the candy distribution into independent peaks.
We can prove that the construction of a single peak is optimal, we can prove the whole candy distribution is optimal.
It’s easy to prove every single peak is optimal.
Some people say their solutions are O(n2 log n) or even O(n2), but...
Consider cases where nums is the n numbers from 1 to n.
=> There are Θ(n4) different quadruplets (nC4, to be exact, so about n4 / 24).
=> There are Θ(n) possible sums (from 1+2+3+4 to (n-3)+(n-2)+(n-1)+n, so about 4n sums).
=> At least one sum must have Ω(n3) different quadruplets.
=> For that sum, we must generate those Ω(n3) quadruplets.
=> For these cases we have to do Ω(n3) work.
=> O(n2 log n) or even O(n2) are impossible.
First of all, let's assume that the optimal choice of the container
with the most water is ( ai, aj ) ( i < j ). Then I just need to prove
that there will definitely exist one situation where the left pointer
is at ai while the right pointer is at aj.
Then I will prove that a1, a2, ...and ai-1 are all smaller than aj.
This proof is simple, because if ak >= aj and 1 <= k <= i-1, then the
optimal choice would be ( ak, aj ), not ( ai, aj ).
Symmetrically, aj+1, aj+2, ...and an are all smaller than ai.
Finally, during the movement of the pointers, either ai or aj will be
reached at first, so let's assume ai is reached before aj. Then
because aj+1, aj+2, ...and an are all smaller than ai, so the right
pointer will continue moving ( because the value it points to is
smaller ) until it reaches aj. Now the left pointer is at ai and the
right pointer is at aj.
And if aj is reached before ai, the proof is also obvious.
Apparently, any (ak,am) such that 1<= k <= i-1, and j+1 <= m <=n, is not optimal,
any (ak,am) such that i< k < m <j, is not optimal.
When 1 <= k <= i-1 and i<= m <=j, there is f, j < f <= n, such that af > ak, and we have that (ak, af) is not optimal
hence (ak,am) < (ak, af) < (ai,aj).
Although I'm not sure about if there exists a n^2log n solution, the prove is not right logically. Yes, choosing 4 out of n has n^3 possibilities. However, keep in mind we have an extra constraint condition: sum to a target.