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

21 Answers 21

up vote 5 down vote accepted

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ƙ`Ṁœ-

Try it online! or Check out a test suite!

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.

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} – nwellnhof Aug 13 at 9:43
  • @nwellnhof Ah, thanks! I didn't realise the second argument could be the Bag – Jo King Aug 13 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. – nwellnhof Aug 13 at 9:58

R, 59 49 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! – Giuseppe Aug 13 at 16:28
  • @Giuseppe: I don't know if that's was similar to your approach, but I saved 10 bytes :D – digEmAll Aug 13 at 18:20
  • huh, no, I was using split but tabulate is much better! – Giuseppe Aug 13 at 18:22
  • mmh... now I'm curious, how did you use split for this ? – digEmAll Aug 13 at 18:45
  • 1
    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... – Giuseppe Aug 13 at 18:58

Python 2, 86 83 80 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, 17 16 17 bytes

¢Z¹ZLŠŠи{ðý¹vyõ.;

-1 byte thanks to @Mr.Xcoder.
+1 byte after bug-fixing the work-around..

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)

Can definitely be golfed. Not really happy with it, tbh.. Will see if I can golf it some more before adding an explanation. EDIT: Added an explanation..

Try it online or verify all test cases.

Explanation:

¢         # Get the occurrences for each item in the (implicit) input-List
          #  i.e. [5,3,3,2,7] → [1,2,2,1,1]
 Z        # And get the maximum
          #  i.e. [1,2,2,1,1] → 2
¹Z        # Also get the maximum from the input-list itself
          #  i.e. [5,3,3,2,7] → 7
  L       # And create a list in the range [1, max]
          #  i.e. 7 → [1,2,3,4,5,6,7]
ŠŠ        # Two triple-swaps so the stack order becomes:
          # trash we don't need; ranged list; occurrence max
  и       # Repeat the ranged list the occurence amount of times
          #  i.e. [1,2,3,4,5,6,7] and 2 → [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..
{         # Sort the list
          #  i.e. [1,2,3,4,5,6,7,1,2,3,4,5,6,7] → [1,1,2,2,3,3,4,4,5,5,6,6,7,7]
 ðý       # Join this list by spaces
          #  i.e. [1,1,2,2,3,3,4,4,5,5,6,6,7,7] → '1 1 2 2 3 3 4 4 5 5 6 6 7 7'
   ¹v     # Loop `y` over the input-List:
     yõ.; # Replace every first occurrence of `y` with an empty string
          #  i.e. '1 1 2 2 3 3 4 4 5 5 6 6 7 7' and 3 → '1 1 2 2  3 4 4 5 5 6 6 7 7'
  • Are you looking for: K a,b Push a without b's? Oh wait, "once each"... hmm – Jonathan Allan Aug 13 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 – Mr. Xcoder Aug 13 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. – Kevin Cruijssen Aug 13 at 7:24
  • 1
    ¢ZIZLŠŠи should save 1 byte – Mr. Xcoder Aug 13 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.. – Kevin Cruijssen Aug 13 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)
  • 2
    digEmAll's answer is perfectly valid; it takes input via stdin! – Giuseppe Aug 13 at 13:36
  • 1
    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) – Giuseppe Aug 13 at 13:39
  • 1
    This fails when the maximum value is not the maximum repeated one, e.g. try f(c(5,3,3,2,7)) – digEmAll Aug 13 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)
  • 1
    You could use instead of ot – Kroppeb Aug 13 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:
        r.add(m);     //     Add it to the result-List
  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

Try it here! or Check out a test suite!

Charcoal, 19 bytes

F…·¹⌈θE⁻⌈Eθ№θκ№θιIι

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
F                   Loop over range
          θ         First input
         E          Loop over values
            θ       First input
             κ      Inner loop value
           №        Count occurrences
        ⌈           Maximum
               θ    First input
                ι   Outer loop value
              №     Count occurrences
       ⁻            Subtract
      E             Map over implicit range
                  ι Current value
                 I  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).
  • 1
    Surprisingly not that long! – Fatalize Aug 13 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!

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.