You are given an inclusive range [lower, upper] and a sorted unique integer array nums, where all elements are in the inclusive range.
A number x is considered missing if x is in the range [lower, upper] and x is not in nums.
Return the smallest sorted list of ranges that cover every missing number exactly. That is, no element of nums is in any of the ranges, and each missing number is in one of the ranges.
Each range [a,b] in the list should be output as:
"a->b " if a != b"a " if a == bExample 1:
Input: nums = [0,1,3,50,75], lower = 0, upper = 99 Output: [ "2 ", "4->49 ", "51->74 ", "76->99 "] Explanation: The ranges are: [2,2] --> "2 " [4,49] --> "4->49 " [51,74] --> "51->74 " [76,99] --> "76->99 "
Example 2:
Input: nums = [-1], lower = -1, upper = -1 Output: [] Explanation: There are no missing ranges since there are no missing numbers.
Constraints:
-109 <= lower <= upper <= 1090 <= nums.length <= 100lower <= nums[i] <= uppernums are unique.program main
implicit none
integer, parameter :: n = 5
integer, parameter :: lower = 0
integer, parameter :: upper = 99
integer, dimension(n) :: nums = (/ 0, 1, 3, 50, 75 /)
integer :: i
call solve(nums, lower, upper)
contains
subroutine solve(nums, lower, upper)
implicit none
integer, intent(in) :: nums(:), lower, upper
character(len=100) :: buffer
integer :: i, j, k
do i = 1, size(nums)
write (buffer, "(I0)") nums(i)
print "(A)", trim(buffer)
end do
end subroutine solve
end program main0 1 3 50 75
program missing_ranges
implicit none
integer, parameter :: lower = 0, upper = 99
integer, parameter :: nums(5) = [0, 1, 3, 50, 75]
integer :: i, j, k
character(len=20) :: range
do i = 1, size(nums) - 1
if (nums(i) + 1 /= nums(i + 1)) then
write (range, "(i0, '->', i0)") nums(i) + 1, nums(i + 1) - 1
else
write (range, "(i0)") nums(i) + 1
end if
write (*, "(a)") trim(range)
end do
end program missing_ranges
1 2->2 4->49 51->74
from typing import List
def find_missing_ranges(nums: List[int], lower: int, upper: int) -> List[str]:
result = []
prev = lower - 1
for i, num in enumerate(nums + [upper + 1]):
if num - prev >= 2:
result.append(f"{prev + 1}" + ("" if num - prev == 2 else "->") + f"{num - 1}")
prev = num
return result
The algorithm iterates over the nums array and keeps track of the previous number (initialized to lower - 1) keeping in mind that nums is a sorted unique array of elements in the range [lower, upper]. For each number, it checks the difference between the current number and the previous number. If the difference is greater or equal to 2, it adds a range to the result vector. Also, it checks whether the range length is equal to 2, in which case it will only print the starting value of the range, without the "->". At the end of the loop, it returns the list of ranges covering the missing numbers in the input range.
#include <vector>
#include <string>
std::vector<std::string> findMissingRanges(std::vector<int>& nums, int lower, int upper) {
std::vector<std::string> result;
long prev = (long)lower - 1;
for (int i = 0; i <= nums.size(); ++i) {
long cur = (i == nums.size()) ? (long)upper + 1 : nums[i];
if (cur - prev >= 2) {
result.push_back(std::to_string(prev + 1) + (cur - prev == 2 ? "" : "->") + std::to_string(cur - 1));
}
prev = cur;
}
return result;
}
The algorithm iterates over the nums array and keeps track of the previous number (initialized to lower - 1) keeping in mind that nums is a sorted unique array of elements in the range [lower, upper]. For each number, it checks the difference between the current number and the previous number. If the difference is greater or equal to 2, it adds a range to the result vector. Also, it checks whether the range length is equal to 2, in which case it will only print the starting value of the range, without the "->". At the end of the loop, it returns the list of ranges covering the missing numbers in the input range.