Problem Statement
You are given a
A range is a finite set of consecutive integers. Formally, for any two positive integers a ≤ b the range [a,b] is defined to be the set of all integers that lie between a and b, inclusive. For example, [3,3] = {3} and [4,7] = {4,5,6,7}.
You want to represent the set given in arr as a union of some ranges. Return the minimum number of ranges you need.
Definition
- Class:
- RangeEncoding
- Method:
- minRanges
- Parameters:
- int[]
- Returns:
- int
- Method signature:
- int minRanges(int[] arr)
- (be sure your method is public)
Constraints
- arr will have between 1 and 50 elements, inclusive.
- Each element of arr will be between 1 and 50.
- The elements in arr will be in strictly increasing order.
Examples
{1,2,3,4,5,6,7,8,9,10}
Returns: 1
We can represent this set as a single range [1,10].
{1,6,10,20,32,49}
Returns: 6
In this case we have to use 6 different ranges, each containing just a single number.
{2,4,5,6,8,9,10,11,12,15}
Returns: 4
This set of integers can be represented as the union of four ranges: [2,2], [4,6], [8,12], and [15,15].
{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47}
Returns: 14
{10,11,12,13,14,15,20,21,22,23,25,27,28,29,30,31,32,33}
Returns: 4
{33}
Returns: 1
{23}
Returns: 1
{17,33}
Returns: 2
{1,2,5,6,9,10,11,12,13,17,19,21,22,26,27,30,31,33,35,38,39,41,43,44,46,47,48}
Returns: 14
{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,38,40,41,42,44,45,46,47,48,49}
Returns: 4
{3,6,8,11,13,14,17,19,23,26,28,29,30,32,35,37,39,40,44,45,46}
Returns: 15
{1,2,7,8,9,10,12,15,17,19,21,22,25,26,30,35,40,41,42,43,45,46,48}
Returns: 13
{1,2,3,4,5,6,7,8,9,11,12,14,15,17,18,19,20,21,22,23,24,25,26,27,29,30,31,32,33,34,36,37,39,40,41,43,44,45,47,49}
Returns: 10
{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}
Returns: 1
{1,3,4,5,8,11,14,16,17,18,20,24,26,29,30,35,40,42,47}
Returns: 14
{2,4,6,9,11,12,13,15,18,21,24,28,30,31,34,36,40,45,47,49}
Returns: 17
{1,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49}
Returns: 25
{1,4,8,10,12,14,15,18,19,22,23,24,25,26,27,28,30,31,32,35,36,38,40,42,46,48}
Returns: 15
{10,15,26,35,38,45}
Returns: 6
{3,10,16,23,30,39,43}
Returns: 7
{2,4,7,9,10,12,13,16,17,19,20,22,24,26,28,30,32,33,36,37,40,41,43,45,46,48}
Returns: 18
{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}
Returns: 1
{1,2,3,4,5,6,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,41,42,43,44,45,46,47,48,49}
Returns: 3
{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}
Returns: 1
{1,2,3,4,5,6,7,8,9,10,11,12,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,36,37,38,39,40,41,42,43,44,45,46,47,48,49}
Returns: 3
{1,3,4,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,25,26,27,28,30,31,32,34,35,36,37,38,39,40,41,42,43,44,45,47,48,49}
Returns: 7
{1,3,5,6,7,8,10,11,12,13,14,16,17,18,20,22,24,25,26,27,28,29,30,31,32,33,34,35,36,38,39,41,42,43,44,46,47,48}
Returns: 11
{1,2,3,4,5,6,7,8,9,10,12,14,15,16,18,19,21,22,23,24,25,26,29,31,32,33,34,35,36,37,38,39,41,42,43,45,47,48}
Returns: 10
{1,2,3,4,5,6,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}
Returns: 2
{2,3,4,5,6,7,8,9,11,12,13,14,15,16,17,19,20,21,22,24,25,27,28,30,31,32,33,34,35,37,38,39,40,41,42,44,47,49}
Returns: 10
{1,3,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49}
Returns: 4
{1, 2, 4 }
Returns: 2
{1 }
Returns: 1
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }
Returns: 1
{1, 2, 3, 4 }
Returns: 1
{33 }
Returns: 1
{50 }
Returns: 1