# Fill up to duplicate ranges

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, 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 , 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 of L or M? Aug 13, 2018 at 6:49
• @Kroppeb i is the biggest element of L, it was a typo in the specs. Aug 13, 2018 at 6:57
• Is it OK to return M=[1,1,2,2,3] for L= while "merging L and M results in a list which can entirely split into identical ranges of integers [1..i]"?
– tsh
Aug 13, 2018 at 7:57
• @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. Aug 13, 2018 at 7:59
• @digEmAll Done. Aug 14, 2018 at 6:27

# Perl 6, 37 33 bytes

-4 bytes thanks to nwellnhof!

{^.keys.max+1 xx.values.max∖$_}  Try it online! Anonymous code block that takes a Bag and returns a Bag of values. ### Explanation: { } # Anonymous code block ^.keys.max+1 # Create a range from 1 to the maximum value of the list xx # Multiply the list by: .values.max # The amount of the most common element ∖$_   # Subtract the original Bag

• Nice! You can save a few bytes by coercing the second operand to Bag: {^.max+1 xx.Bag.values.max∖.Bag} Aug 13, 2018 at 9:43
• @nwellnhof Ah, thanks! I didn't realise the second argument could be the Bag
– Jo King
Aug 13, 2018 at 9:48
• OTOH, the challenge requires that the data structures for input and output must be the same. With Bags as input, {^.keys.max+1 xx.values.max∖$_} saves another byte. Aug 13, 2018 at 9:58 # Jelly, 9 bytes Saved 1 byte thanks to Jonathan Allan. The footer calls the main link, sorts the result to match the test cases and formats the output as a grid. RṀẋLƙṀœ-  ### Alternatives ṀRẋLƙṀœ- RṀẋṢŒɠṀƊœ- ṀRẋṢŒɠṀƊœ- LƙɓṀRẋṀœ-⁸ LƙɓRṀẋṀœ-⁸  Try one of them online! ### Explanation ṀRẋLƙṀœ- Full program. N = Input. ṀR Range from 1 to max(N): [1 ... max(N)] Lƙ Map length over groups formed by identical elements. ẋ Repeat the range T times, for each T in the result of the above. Ṁ Maximum. Basically, get the range repeat max(^^) times. œ- Multiset difference with N.  # R, 5949 48 bytes rep(s<-1:max(L<-scan()),max(y<-table(c(L,s)))-y)  Try it online! • I have a 55 byte answer that basically generates the second argument to rep differently, but is otherwise the same as yours. I could post it myself but I don't think I would have thought of it unless I'd seen yours first. I challenge you to find it! Aug 13, 2018 at 16:28 • @Giuseppe: I don't know if that's was similar to your approach, but I saved 10 bytes :D Aug 13, 2018 at 18:20 • huh, no, I was using split but tabulate is much better! Aug 13, 2018 at 18:22 • mmh... now I'm curious, how did you use split for this ? Aug 13, 2018 at 18:45 • I had x=max(L<-scan());rep(1:x,1:x-lengths(split(L,c(L,1:x)))) which upon further testing doesn't work for test cases like 7... Aug 13, 2018 at 18:58 # Python 2, 868380 72 bytes def f(l):m=range(1,max(l)+1)*max(map(l.count,l));map(m.remove,l);print m  Try it online! # 05AB1E, 171617 11 bytes ZLŠ¢àиIð.;þ  -1 byte thanks to @Mr.Xcoder. +1 byte after bug-fixing the work-around.. -5 bytes by using the new 05AB1E version and -1 byte because ordering of the output is unimportant Maybe I completely look past it, but does 05AB1E even have a remove all elements of list b from list a.. (EDIT: It indeed doesn't..) I know how to remove all multiple times, but not once each.. (multiset difference) Explanation: Z # Push the maximum of the (implicit) input-list (without popping) # i.e. [5,3,3,2,7] → 7 L # Pop and push a list in the range [1,max] # → [1,2,3,4,5,6,7] Š # Tripleswap: a,b,c → c,a,b, so input,[1,max] to [1,max],input,input ¢ # Count for each value in the input-list how many times it occurs # → [1,2,2,1,1] à # Pop and push the maximum count # → 2 и # Repeat the list [1,max] that many times # → [1,2,3,4,5,6,7,1,2,3,4,5,6,7] #Now the work-around bit because 05AB1E lacks a builtin for multiset difference.. Ið.; # Replace first occurrence of the values in the input-list with a space " " # → [1," "," ",4," ",6," ",1,2," ",4,5,6,7] þ # Remove all spaces by only keeping digits # → [1,4,6,1,2,4,5,6,7] # (after which the result is output implicitly)  • Are you looking for: K a,b Push a without b's? Oh wait, "once each"... hmm Aug 13, 2018 at 7:22 • @JonathanAllan No, that won't work, it removes all occurrences rather than the first occurrence of each. Kevin is looking for something like multiset difference Aug 13, 2018 at 7:24 • @JonathanAllan Almost. [1,2,3,4,5,6,7,1,2,3,4,5,6,7] and [5,3,3,2,7] with K results in [1,4,6,1,4,6] unfortunately. It removes all items instead of doing a multiset difference. Aug 13, 2018 at 7:24 • ¢ZIZLŠŠи should save 1 byte Aug 13, 2018 at 8:01 • @Mr.Xcoder Thanks, but that wasn't the part I was looking to golf. ;p Funny how two triple-swaps is shorter than removing the access after the count.. Aug 13, 2018 at 8:06 # R, 59 55 bytes Using the vecsets package we can drop the answer length some. With gl we can get the ordered output. This doesn't work in TIO. Following @digEmAll's style of (rather clever) solution without a function definition, this can be considered a 55 byte solution. vecsets::vsetdiff(c(gl(m<-max(L<-scan()),sum(L==m))),L) f=function(x){scan<-function()x vecsets::vsetdiff(c(gl(m<-max(L<-scan()),sum(L==m))),L) } f(c(1)) # expected: integer(0) f(c(7)) # expected: c(1, 2, 3, 4, 5, 6) f(c(1, 1, 1)) # expected: integer(0) f(c(1, 8)) # expected: c(2, 3, 4, 5, 6, 7) f(c(3, 3, 3, 3)) # expected: c(1, 1, 1, 1, 2, 2, 2, 2) f(c(5, 2, 4, 5, 2)) # expected: c(1, 1, 3, 3, 4) f(c(5, 2, 4, 5, 5)) # expected: c(1, 1, 1, 2, 2, 3, 3, 3, 4, 4)  • digEmAll's answer is perfectly valid; it takes input via stdin! Aug 13, 2018 at 13:36 • Also, as this is not base R, this should be considered a separate language "R + vecsets" (I can't find the relevant meta discussion for that, but I know it's standard practice) Aug 13, 2018 at 13:39 • This fails when the maximum value is not the maximum repeated one, e.g. try f(c(5,3,3,2,7)) Aug 13, 2018 at 19:38 # JavaScript (ES6), 98 bytes This turned out to be pretty hard to golf below 100 bytes. There may be a better approach. a=>(a.map(o=M=m=n=>m=(c=o[M=n<M?M:n,n]=-~o[n])<m?m:c),g=k=>k?o[k]^m?[...g(k,o(k)),k]:g(k-1):[])(M)  Try it online! ### How? We first walk through the input array a[] to gather the following data: • M = highest element found in the input array • m = highest number of occurrences of the same element • o[n] = number of occurrences of n Note that o is primarily defined as a function, but the underlying object is also used to store the number of occurrences. a.map( // a[] = input array() o = // o = callback function of map() M = m = // initialize m and M to non-numeric values n => // for each value n in a[]: m = ( // this code block will eventually update m c = o[ // c = updated value of o[n] M = n < M ? M : n, // update M to max(M, n) n // actual index into o[] ] = -~o[n] // increment o[n] ) < m ? // if o[n] is less than m: m // let m unchanged : // else: c // set it to c ) // end of map()  We then use the recursive function g() to build the output. (g = k => // k = current value k ? // if k is not equal to 0: o[k] ^ m ? // if o[k] is not equal to m: [ ...g(k, o(k)), // increment o[k] and do a recursive call with k unchanged k ] // append k to the output : // else: g(k - 1) // do a recursive call with k - 1 : // else: [] // stop recursion )(M) // initial call to g() with k = M  ## Haskell, 72 bytes import Data.List f l=(last(sortOn(0<$)$group$sort l)>>[1..maximum l])\\l


Try it online!

            sort l      -- sort input list
group            -- group identical elements
sortOn(0<\$)          -- sort by length
last                   -- take the last element, i.e. the list
-- of the most common element
>>[1..maximum l]  -- replace each of it's elements
-- with the list [1..maximum l]
\\l                   -- remove elements of the input list


# Brachylog, 18 17 bytes

⌉⟦₁;Ij₎R⊇p?;.cpR∧


Try it online!

Saved 1 byte thanks to @Kroppeb.

### Explanation

⌉                  Take the largest element in the Input
⟦₁                 Construct the range [1, …, largest element in the Input]
;Ij₎R            Juxtapose that range to itself I times, I being unknown;
call the result R
R⊇p?         The Input must be an ordered subset of R, up to a permutation
?;.c      Concatenate the Input and the Output
(the Output being unknown at this point)
pR    This concatenation must result in R, up to a permutation
∧   (Find a fitting value for the Output that verifies all of this)

• You could use ⌉ instead of ot Aug 13, 2018 at 20:25

# Java 10, 186 bytes

import java.util.*;L->{Integer m=0,f=0,t;for(int i:L){m=i>m?i:m;f=(t=Collections.frequency(L,i))>f?t:f;}var r=new Stack();for(;m>0;m--)for(t=f;t-->0;)if(!L.remove(m))r.add(m);return r;}


Try it online.

Explanation:

import java.util.*;   // Required import for Collections and Stack
L->{                  // Method with Integer-list as both parameter and return-type
Integer m=0,        //  Max, starting at 0
f=0,        //  Max frequency, starting at 0
t;          //  Temp integer
for(int i:L){       //  Loop over the input-List
m=i>m?i:m;        //   If the current item is larger than the max, set it as new max
f=(t=Collections.frequency(L,i))>f?t:f;}
//   If the current frequency is larger than the max freq, set it as new max
var r=new Stack();  //  Result-List
for(;m>0;m--)       //  Loop the maximum in the range [m,0)
for(t=f;t-->0;)   //   Inner loop the frequency amount of times
if(!L.remove(m))//    Remove m from the input list
//    If we were unable to remove it:
return r;}          //  Return the result-List


# Husk, 12 bytes

Saved 1 byte thanks to BWO.

S-§*oḣ▲(▲Ṡm#


Try it online!

# MATL, 24 21 bytes

X>:GS&Y'X>yGhS&Y'q-Y"


Try it online!

# MATL, 14 bytes

Input is a column vector, with ; as separator.

llXQtn:yX>b-Y"


Try it online! Or verify all test cases (this displays -- after each output so that empty output can be identified).

### Explanation

Consider input [5; 2; 4; 5; 5] as an example.

llXQ     % Implicit input. Accumarray with sum. This counts occurrences
% of each number, filling with zeros for numbers not present
% STACK: [0; 1; 0; 1; 3]
tn:      % Duplicate, number of elements, range
% STACK: [0; 1; 0; 1; 3], [1 2 3 4 5]
yX>      % Duplicate from below, maximum of array
% STACK: [0; 1; 0; 1; 3], [1 2 3 4 5], 3
b        % Bubble up
% STACK: [1 2 3 4 5], 3, [0; 1; 0; 1; 3]
-        % Subtract, element-wise
% STACK: [1 2 3 4 5], [3; 2; 3; 2; 0]
Y"       % Repelem (run-length decode). Implicit display
% STACK: [1 1 1 2 2 3 3 3 4 4]


# Pyth, 13 bytes

.-*SeSQeSlM.g


# Charcoal, 19 bytes

Ｆ…·¹⌈θＥ⁻⌈Ｅθ№θκ№θιＩι


Try it online! Link is to verbose version of code. Would have been 16 bytes if the integers had been non-negative instead of positive. Explanation:

     θ              First input
⌈               Maximum
…·¹                Inclusive range starting at 1
Ｆ                   Loop over range
θ         First input
Ｅ          Loop over values
θ       First input
κ      Inner loop value
№        Count occurrences
⌈           Maximum
θ    First input
ι   Outer loop value
№     Count occurrences
⁻            Subtract
Ｅ             Map over implicit range
ι Current value
Ｉ  Cast to string
Implicitly print on separate lines


# APL (Dyalog Classic), 18 17 bytes

∊{⊂⍳⌈/⍵}~¨∘↓∘⍉⊣¨⌸


Try it online!

uses ⎕io←1

# Prolog (SWI), 211 bytes

It's been a while since I programmed in Prolog. Can definitely be golfed further, but I have an exam to study for hahaha.

### Code

f(L,X):-max_list(L,M),f(L,M,[],X,M).
f([],0,_,[],_).
f(L,0,_,A,M):-f(L,M,[],A,M).
f([],I,H,[I|A],M):-N is I-1,f(H,N,[],A,M).
f([I|R],I,H,A,M):-append(H,R,S),f(S,I,[],[I|A],M).
f([H|R],I,G,A,M):-f(R,I,[H|G],A,M).


Try it online!

### Ungolfed version

f(List, Result) :-
max_list(List, MaxIndex),
f(List, MaxIndex, [], Result, MaxIndex).

f([], 0, _, [], _).

f(List, 0, _, Acc, MaxIndex) :-
f(List, MaxIndex, [], Acc, MaxIndex).

f([], Index, History, [Index | Acc], MaxIndex) :-
NewIndex is Index - 1, f(History, NewIndex, [], Acc, MaxIndex).

f([Index | Remaining], Index, History, Acc, MaxIndex) :-
append(History, Remaining, Result),
f(Result, Index, [], [Index | Acc], MaxIndex).

f([Head | Remaining], Index, History, Acc, MaxIndex) :-
f(Remaining, Index, [Head | History], Acc, MaxIndex).

• Surprisingly not that long! Aug 13, 2018 at 14:31

## Clojure, 94 bytes

#(for[F[(frequencies %)]i(range 1(+(apply max %)1))_(range(-(apply max(vals F))(or(F i)0)))]i)


# C++, 234 bytes

#include<vector>
#include<map>
using X=std::vector<int>;
X f(X x){int q,z;q=z=0;std::map<int,int>y;X o;
for(auto i:x)++y[i];for(auto i:y)q=q>i.second?q:i.second;
for(;++z<=y.rbegin()->first;)for(;y[z]++<q;)o.push_back(z);return o;}


(Newlines in the function body are for readability).

The function takes and returns a vector of ints. It utilizes std::map for finding the max element of the input list and also for counting the occurrences of each distinct element.

Explanation:

// necessary includes. Note that each of these is longer than whole Jelly program!
#include <vector>
#include <map>

// this type occurs three times in the code
using X = std::vector<int>;

// The function
X f (X x)
{
// initialize some variables
int q, z; // q will hold the max count
q = z = 0;
std::map <int, int> y; // The map for sorting
X o; // The output vector

// Populate the map, effectively finding the max element and counts for all of them
for (auto i : x)
++y[i];

// find the max count
for (auto i : y)
q = q > i.second ? q : i.second;

// Populate the output vector

// Iterate all possible values from 1 to the max element (which is the key at y.rbegin ())
// Note that z was initialized at 0, so we preincrement it when checking the condition
for (; ++z <= y.rbegin ()->first;)
// for each possible value, append the necessary quantity of it to the output
for(; y[z]++ < q;)
o.push_back (z);

return o;
}


# Gaia, 12 bytes

::⌉┅¤:C¦⌉&¤D


Try it online!

# C (gcc), 177 bytes

Input and output are done through stdin and stdout. Both arrays are capped at 2^15 elements, but they could be as large as 2^99 elements.

f(j){int n=0,m=0,i=0,a[1<<15],b[1<<15]={0};for(;scanf("%i",&a[i])>0;i++)j=a[i],m=j>m?j:m,b[j-1]++;for(i=m;i--;)n=b[i]>n?b[i]:n;for(i=m;i--;)for(j=n-b[i];j--;)printf("%i ",i+1);}


With some formatting:

f(j){
int n=0, m=0, i=0, a[1<<15], b[1<<15]={0};
for(;scanf("%i",&a[i])>0;i++) j=a[i], m=j>m?j:m, b[j-1]++;
for(i=m;i--;) n=b[i]>n?b[i]:n;
for(i=m;i--;) for(j=n-b[i];j--;) printf("%i ",i+1);
}


Try it online!