Patching Array


  • 0

    Intuition


    Click here to see the full article post


  • 0

    Can anyone help to explain more about this statement "suppose the k patches found by greedy algorithm is X_1 < X_2 <... ≤ X_k ≤ n. If there is another set of patches Y_1 ≤ Y_2 ≤...≤ Y_{k'} ≤n, with k'<k, then we have Y_1 <= X_1, otherwise X_1 is not covered."
    More specifically, how to deduce inequality of “Y_1 <= X_1” ? Given n , k' patches, we could only know X_k <=n and Y_k' <=n and k'<k, but I can't see where we could get “Y_1 <= X_1”.
    Thanks!


  • 0

    Can anyone help to explain more about this statement "suppose the k patches found by greedy algorithm is X_1 < X_2 <... ≤ X_k ≤ n. If there is another set of patches Y_1 ≤ Y_2 ≤...≤ Y_{k'} ≤n, with k'<k, then we have Y_1 <= X_1, otherwise X_1 is not covered."
    More specifically, how to deduce inequality of “Y_1 <= X_1” ? Given n , k' patches, we could only know X_k <=n and Y_k' <=n and k'<k, but I can't see where we could get “Y_1 <= X_1”.
    Thanks!


  • 0
    R

    I think one more logic would be excellent:
    that any number could be formed by sum of powers of 2. This implies if we just check if the nums array contains powers of 2, or are derivable from the given numbers. It would be linear time.


Log in to reply
 

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