15
Let \$L\$ be a list of positive integers with no particular ordering, and which can contain duplicates. Write a program or function which outputs a list of positive integers \$M\$ (whose ordering is unimportant) such that merging \$L\$ and \$M\$ results into the smallest list which can entirely split into identical ranges of integers \$[1..i]\$, where \$i\$ is the biggest element in \$L\$
Example
Let L = [5,3,3,2,7]
. The maximum element of L
is 7
. The most times a specific integer occurs is 2
(3
appears 2 times). Therefore, we need to output the list M
that will allow to complete L
so that we can construct 2
ranges of integers from 1
to 7
.
Therefore, we need to output M = [1,1,2,4,4,5,6,6,7]
, so that each integer from 1
to 7
appears 2
times.
Inputs and outputs
- Use anything in your language that is similar to lists. The data structure used for the input and the output must be the same.
- The input list will contain only positive integers.
- The input list will not be empty.
- You cannot assume the input list is sorted.
- The ordering in the output list is unimportant.
Test cases
Input Output
[1] []
[7] [1, 2, 3, 4, 5, 6]
[1, 1, 1] []
[1, 8] [2, 3, 4, 5, 6, 7]
[3, 3, 3, 3] [1, 1, 1, 1, 2, 2, 2, 2]
[5, 2, 4, 5, 2] [1, 1, 3, 3, 4]
[5, 2, 4, 5, 5] [1, 1, 1, 2, 2, 3, 3, 3, 4, 4]
[5, 3, 3, 2, 7] [1, 1, 2, 4, 4, 5, 6, 6, 7]
Scoring
This is code-golf, so the shortest answer in bytes wins.
Just to be clear, as your test cases and statement contradict each other, is
i
the biggest element ofL
orM
? – Kroppeb – 2018-08-13T06:49:04.777@Kroppeb
i
is the biggest element ofL
, it was a typo in the specs. – Fatalize – 2018-08-13T06:57:59.887Is it OK to return
M=[1,1,2,2,3]
forL=[3]
while "merging L and M results in a list which can entirely split into identical ranges of integers [1..i]"? – tsh – 2018-08-13T07:57:10.987@tsh No, it should return
[1,2]
. I will clarify it so that it's clear it should result in the minimum number of ranges. – Fatalize – 2018-08-13T07:59:42.657I suggest you to add your first example [5,3,3,2,7] among the test cases, since it's the only one with the maximum value != maximum repeated one – digEmAll – 2018-08-13T19:39:23.863
1@digEmAll Done. – Fatalize – 2018-08-14T06:27:10.253