Given a sorted (in increasing order) array of positive numbers, can you find the smallest positive integer that cannot be represented as a sum of elements from the array?
Libraries:
library(tidyverse) # Includes purrr package
library(gtools)
library(reticulate)Sorted (in increasing order) array of positive numbers vector:
vector <- c(1, 3, 6, 10, 11, 15)Combinations in R using the gtools::combinations package and function:
combinations(n = length(vector), # Amount of elements
r = 3, # Selections
v = vector, # Array
set = FALSE) ## [,1] [,2] [,3]
## [1,] 1 3 6
## [2,] 1 3 10
## [3,] 1 3 11
## [4,] 1 3 15
## [5,] 1 6 10
## [6,] 1 6 11
## [7,] 1 6 15
## [8,] 1 10 11
## [9,] 1 10 15
## [10,] 1 11 15
## [11,] 3 6 10
## [12,] 3 6 11
## [13,] 3 6 15
## [14,] 3 10 11
## [15,] 3 10 15
## [16,] 3 11 15
## [17,] 6 10 11
## [18,] 6 10 15
## [19,] 6 11 15
## [20,] 10 11 15Function that figure out the sum of all combinations, selecting n elements from a vector of positive integers:
sum_combinations <- function(vector, n) {
sums <- combinations(n = length(vector),
r = n,
v = vector,
set = FALSE) %>%
addmargins(2) %>% # Sum rows
data.frame() %>%
select(Sum)
return(sums)
}Applying the created function to obtain all possible numbers that can be represented as a sum of elements from the array:
represented_integers <- map_dfr(.x = 1:length(vector),
.f = ~ sum_combinations(vector,
n = .x)) %>%
arrange(Sum) %>%
distinct() %>% # Delete repeated elements
pull(Sum)
# Integers that can be represented as a sum of elements from the vector
represented_integers## [1] 1 3 4 6 7 9 10 11 12 13 14 15 16 17 18 19 20 21 22 24 25 26 27 28 29
## [26] 30 31 32 33 34 35 36 37 39 40 42 43 45 46To obtain the minimum integer that can’t be represented:
# Integers that not appears in the sequence from 1 to maximum of represented numbers.
minimum_table <- data.frame(all_numbers = seq(1, max(represented_integers))) %>%
filter(!(all_numbers %in% represented_integers)) %>%
slice_min(order_by = all_numbers)
# Conditional selection of minimum integer if the number is between the range of represented integers or not.
if(dim(minimum_table)[1] == 0) {
minimum_int <- max(represented_integers) + 1
} else {
minimum_int <- minimum_table[1, 1]
}The smallest positive integer that cannot be represented as a sum of elements from the array [1, 3, 6, 10, 11, 15] is 2.
Minimum unrepresented integer function:
min_unrepresented_int <- function(vector) {
# 1.
sum_combinations <- function(n) {
sums <- combinations(n = length(vector),
r = n,
v = vector,
set = FALSE) %>%
addmargins(2) %>% # Sum columns
data.frame() %>%
select(Sum)
return(sums)
}
# 2.
represented_integers <- map_dfr(.x = 1:length(vector),
.f = ~ sum_combinations(n = .x)) %>%
arrange(Sum) %>%
distinct() %>% # Delete repeated elements
pull(Sum)
# 3.
minimum_table <- data.frame(all_numbers = seq(1, max(represented_integers), 1)) %>%
filter(!(all_numbers %in% represented_integers)) %>%
slice_min(order_by = all_numbers)
# 4.
if(dim(minimum_table)[1] == 0) {
minimum_int <- max(represented_integers) + 1
} else {
minimum_int <- minimum_table[1, 1]
}
# 5.
return(minimum_int)
}Applying the unique R function:
vector <- c(1, 3, 6, 10, 11, 15)
min_unrepresented_int(vector)## [1] 2The smallest positive integer that cannot be represented as a sum of elements from the array [1, 3, 6, 10, 11, 15] is 2.
vector <- c(1, 1, 1, 1)
min_unrepresented_int(vector)## [1] 5The smallest positive integer that cannot be represented as a sum of elements from the array [1, 1, 1, 1] is 5.
vector <- c(1, 1, 3, 4)
min_unrepresented_int(vector)## [1] 10The smallest positive integer that cannot be represented as a sum of elements from the array [1, 1, 3, 4] is 10.
Libraries:
import pandas as pd
import numpy as np
import itertoolsArrays in Python:
# Array
array = [1, 3, 6, 10, 11, 15]
# Length of array
len(array)## 6Combinations in Python:
combinations = pd.DataFrame(itertools.combinations(array, 3),
columns = ["one", "two", "three"]) # Columns names
print(combinations)
# Sum rows:## one two three
## 0 1 3 6
## 1 1 3 10
## 2 1 3 11
## 3 1 3 15
## 4 1 6 10
## 5 1 6 11
## 6 1 6 15
## 7 1 10 11
## 8 1 10 15
## 9 1 11 15
## 10 3 6 10
## 11 3 6 11
## 12 3 6 15
## 13 3 10 11
## 14 3 10 15
## 15 3 11 15
## 16 6 10 11
## 17 6 10 15
## 18 6 11 15
## 19 10 11 15combinations["sum"] = combinations.sum(1)
# combinations["sum"] = combinations.one + combinations.two + combinations.threeFunction that calculates the sum of all possible combinations selecting n elements from an array:
def sum_combinations(array, n):
combinations = pd.DataFrame(list(itertools.combinations(array, 3))).sum(1)
return combinations.sum(1)
Using map function to apply a function to an iterable object like arrays:
represented_int = list(map(lambda n:
pd.DataFrame(itertools.combinations(array, n)).sum(1), # Combinations Sum
list(np.arange(1, len(array) + 1)))) # Iterable object, arguments for the lambda function
# Return a list of series
represented_int = pd.concat(represented_int, 0) # Concatenate Series by rows
represented_int = represented_int.drop_duplicates().sort_values() # Drop duplicates and sort elements
# represented_int.index = np.arange(0, len(represented_int), 1) # Replace indexes of a serie
type(represented_int) # Type of object
# dir(represented_int) # Attributes of the given object## <class 'pandas.core.series.Series'>To obtain the minimum integer that can’t be represented:
all_numbers = np.arange(1, represented_int.max() + 1)
# All elements that are in all_numbers but not represented_int
diff_int = list(set(all_numbers).difference(set(represented_int)))
# Conditional selection
if len(diff_int) != 0:
minimum_int = min(diff_int)
else:
minimum_int = represented_int.max() + 1
print(minimum_int)## 2def min_unrepresented_int(array):
# 1.
represented_int = list(map(lambda n:
pd.DataFrame(itertools.combinations(array, n)).sum(1),
list(np.arange(1, len(array) + 1))))
represented_int = pd.concat(represented_int, 0)
represented_int = represented_int.drop_duplicates().sort_values()
# 2.
all_numbers = np.arange(1, represented_int.max() + 1)
diff_int = list(set(all_numbers).difference(set(represented_int)))
# 3.
if len(diff_int) != 0:
minimum_int = min(diff_int)
else:
minimum_int = represented_int.max() + 1
# 4.
return minimum_intApplying the unique Python function:
integers = [1, 3, 6, 10, 11, 15]
min_unrepresented_int(integers)## 2The smallest positive integer that cannot be represented as a sum of elements from the array [1, 3, 6, 10, 11, 15] is 2.
integers = [1, 1, 1, 1]
min_unrepresented_int(integers)## 5The smallest positive integer that cannot be represented as a sum of elements from the array [1, 1, 1, 1] is 5.
integers = [1, 1, 3, 4]
min_unrepresented_int(integers)## 10The smallest positive integer that cannot be represented as a sum of elements from the array [1, 1, 3, 4] is 10.
integers = [15, 30, 45, 50]
min_unrepresented_int(integers)## 1The smallest positive integer that cannot be represented as a sum of elements from the array [15, 30, 45, 50] is 1.