forked from nch3ng/leetcode-1
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathpatching_array.rb
More file actions
49 lines (46 loc) · 1.18 KB
/
Copy pathpatching_array.rb
File metadata and controls
49 lines (46 loc) · 1.18 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
# https://leetcode.com/problems/patching-array/
#
# Given a sorted positive integer array nums and an integer n, add/patch
# elements to the array such that any number in range [1, n] inclusive can be
# formed by the sum of some elements in the array. Return the minimum number
# of patches required.
#
# Example 1:
#
# nums = [1, 3], n = 6
# Return 1. Combinations of nums are [1], [3], [1,3], which form possible
# sums of: 1, 3, 4. Now if we add/patch 2 to nums, the combinations
# are: [1], [2], [3], [1,3], [2,3], [1,2,3]. Possible sums are 1, 2, 3, 4,
# 5, 6, which now covers the range [1, 6]. So we only need 1 patch.
#
# Example 2:
#
# nums = [1, 5, 10], n = 20
# Return 2. The two patches can be [2, 4].
#
# Example 3:
#
# nums = [1, 2, 2], n = 5
# Return 0.
#
# Credits:
#
# Special thanks to @dietpepsi for adding this problem and creating all
# test cases.
# @param {Integer[]} nums
# @param {Integer} n
# @return {Integer}
def min_patches(nums, n)
ubound, i = 1, 0
count = 0
while ubound <= n
if nums[i] && nums[i] <= ubound
ubound += nums[i]
i += 1
else
ubound += ubound
count += 1
end
end
count
end