Reach A Number


  • 1

    Click here to see the full article post


  • 0
    L

    Got the wrong problem description attached


  • 0

    Beautiful question and next explanation. Thanks!


  • 0
    A

    Awesome explanation !!


  • 0
    P

    Nice problem! @awice What is the primary concept behind this approach? i.e Why does it work? Sorry if this seems like a silly question.


  • 0
    K

    @patrick71 I quite agree with you. Though the algorithm is accepted, there is lack of proof of correctness. For example, "if delta = S - target is even, then we can always find a subset of {1, 2, ..., k} equal to delta / 2 and switch the signs, so the answer is k." Why you can find the subset?


  • 0

    @kww I will add a proof, I thought it was clear enough to omit that detail but I guess not.


  • 0

    @patrick71 The concept was finding a minimum bound for the answer. I found some k for which the answer had to be at least k, and played around from there.


  • 0
    D

    import math

    def satisfy(x, n):
    h = (n + 1) * n / 2
    l = -1 * h
    return x >= l and x <= h and (x - l) % 2 == 0

    class Solution(object):
    def reachNumber(self, target):
    """
    :type target: int
    :rtype: int
    """
    target = abs(target)
    if target <= 1: return target
    b = int(math.sqrt(target * 2 + 1))
    if satisfy(target, b): return b
    if satisfy(target, b + 1): return b + 1
    if satisfy(target, b + 2): return b + 2
    return b + 3

    O(1) time and memory. One can observe the pattern of the numbers reachable by n steps. They range from - n * (n + 1) / 2 to n * (n + 1) / 2 with spacing of 2.


  • 0
    C

    O(1) solution should be added..


  • 0

    I'm not following the proofs for when the delta is even:

    "The proof is simple: either T <= k and we choose it, or we choose k in our subset and try to solve the same instance of the problem for T -= k and the set {1, 2, ..., k-1}."

    What is considered the "instance of the problem"?

    T = delta/2 = { 1, 2, ..., k} ; delta = S - target

    Can you give me an example of the proof?

    Also how does 1+2+⋯+k=k(k+1)21+2+⋯+k=k(k+1)2 = √( target) for runtime.

    Thanks!


  • 0

    @dare_wreck54-yahoo-com said in Reach A Number:

    I'm not following the proofs for when the delta is even:
    "The proof is simple: either T <= k and we choose it, or we choose k in our subset and try to solve the same instance of the problem for T -= k and the set {1, 2, ..., k-1}."
    What is considered the "instance of the problem"?

    It means that if for some reason T is greater than k, then we could simply subtract k so that we have a new delta that is within the set {1, 2, ..., k-1}. Then we would continue solving for this ("instance" or particular inputs of the) problem in the exact same way, with the updated constraints: T = T-k, and the set {1, 2, ..., k-1}.

    T = delta/2 = { 1, 2, ..., k} ; delta = S - target
    Can you give me an example of the proof?

    We are looking for an even "delta" within the set {1, 2, ..., k } because in order to resolve the difference of delta, we need to move "backward" and then "forward" again along the number line in order to eliminate delta. We can't move in fractions of a step, only whole integer steps. (Dividing an odd number would result in half a step, which isn't allowed.) Also, since we are trying to minimize the total # of steps, we look to choose from the set of steps we have already taken-- and we may have to take more steps until we get an even delta.

    So for example, in the case of target = 4, we have S = {1,2,3}. 1+2+3=6 and target is 4, so 6-4 = 2 = delta. Delta is even, so we can take Delta/2 steps backwards in order to eliminate Delta from the result. Delta/2 = 1, so we can do -1 + 2 + 3 = 4.

    From the short proof above, if Delta is even, then Delta/2 will be in the set {1,2,3,...,k} so it's easy to just choose it and make it negative. And if it's not in the set for some reason, we could subtract k so we have a delta contained within the set.

    Also how does 1+2+⋯+k=k(k+1)21+2+⋯+k=k(k+1)2 = √( target) for runtime.
    Thanks!

    As you probably know we see the pattern "1+2+....+N" (sum of natural numbers) very often in algorithm and space complexity analysis and so we know it's equal to N(N+1)/2. It follows:

    1. Target <= k(k+1)/2
    2. k(k+1)/2 is roughly on the order of k^2 (good enough for complexity analysis)
    3. We are iterating k times
    4. Target <= k^2
    5. √( Target) <= k
    6. So our upper bound is O(k) = O(√( Target))

    I do have one question for @awice : How do we know that k+2 is guaranteed to result in even delta, and that we don't need to go again to k+3, k+4, etc?


  • 0

    @chrislzm said in Reach A Number:

    I do have one question for @awice : How do we know that k+2 is guaranteed to result in even delta, and that we don't need to go again to k+3, k+4, etc?

    Just figured out the answer to my own question:

    If delta is odd, we add a number to it (which may be even or odd), with two possible results:

    1. Add odd number: Then the result will be an even number. Done.

    2. Add even number : Then the result will be another odd number. Then we need to add one more number, which will be odd since we just added an even number. Two odd numbers = even number, so there is guaranteed to be a solution at k+2, if there wasn't at k+1 or k.


  • 0
    W

    Nice solution! Just one comment on your proof.
    delta = S - target implies delta in range [0, k) according to the definition of k.
    So if delta is even, delta/2 must also be less that k and just choose that number to flip sign.
    Hope this helps make the proof simpler.


  • 0

  • 0
    Y

    @n2xiong not sure that taking sqrt is better than the loop.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.