Remove excessive occurrences

Question

Given an array \$A\$ of positive integers between \$1\$ and \$9\$ inclusive and a positive integer \$n\$, remove all integers in \$A\$ which appear more than \$n\$ times.

For example:

             [1,2,3,2,3,2,4,1,2], n = 2
Occurrence:   1 1 1 2 2 3 1 2 4
Keep?         1 1 1 1 1 0 1 1 0
Kept values: [1,2,3,2,3,  4,1  ]

so the output is [1,2,3,2,3,4,1]

You can assume that:

• At least one element will always appear more than \$n\$ times
• At least one element will appear fewer than \$n\$ times
• \$A\$ will have a minimum of 2 distinct elements
• \$n\$ and the length of \$A\$ are within the integer bounds of your language.

You may take input and output in any convenient method. As the elements of \$A\$ are digits, you may also take input as an integer, or a single string, if that suits you.

This is code-golf so the shortest code in bytes wins

Test cases

A, n -> out
[7,3,3,9], 1 -> [7,3,9]
[4,1,7,7,4,2,1], 1 -> [4,1,7,2]
[6,9,7,6,7,9,9], 2 -> [6,9,7,6,7,9]
[6,5,3,9,4,9,6,9], 2 -> [6,5,3,9,4,9,6]
[4,8,9,7,3,1,7,5,4,6], 1 -> [4,8,9,7,3,1,5,6]
[5,6,7,8,1,7,3,3,6,4], 1 -> [5,6,7,8,1,3,4]
[2,3,8,1,6,4,8,2,8,3], 2 -> [2,3,8,1,6,4,8,2,3]
[4,1,4,4,2,4,4,5,7,1,3], 1 -> [4,1,2,5,7,3]
[1,5,5,2,5,1,4,1,6,7,7,6,9,8,8,1,7,8,1,3,1,1,7,4], 3 -> [1,5,5,2,5,1,4,1,6,7,7,6,9,8,8,7,8,3,4]
[8,8,6,2,9,6,4,7,1,2,9,5,5,6,6,2,5,8,9,1,2,8,4,4,7,2,1,1], 3 -> [8,8,6,2,9,6,4,7,1,2,9,5,5,6,2,5,8,9,1,4,4,7,1]
[8,8,4,9,7,1,2,9,8,8,5,2,2,9,1,7,4,6,6,8,6,6,1,6,1,9,2,8,5,1,2,6,1,7,6,4,7,9], 4 -> [8,8,4,9,7,1,2,9,8,8,5,2,2,9,1,7,4,6,6,6,6,1,1,9,2,5,7,4,7]
[8,8,9,2,7,4,7,5,6,9,7,2,7,7,6,2,6,9,6,3,5,1,1,6,2,8,7,4,2,4,5,9,3,3,3,3,7,4,8,7,5,4,1,4,7,8], 2 -> [8,8,9,2,7,4,7,5,6,9,2,6,3,5,1,1,4,3]
[6,8,1,8,6,9,2,2,5,8,7,6,2,5,4,3,3,1,4,2,7,1,6,3,9,8,9,5,2,6,8,8,7,7,5,2,5,1,4,7,5,5,3,7,6,3,7,6,3,6,7], 4 -> [6,8,1,8,6,9,2,2,5,8,7,6,2,5,4,3,3,1,4,2,7,1,6,3,9,8,9,5,7,7,5,1,4,3]
[1,3,5,6,1,2,8,8,8,4,4,4,5,8,9,9,6,4,5,3,8,7,9,7,8,6,1,6,1,6,4,5,5,3,9,3,5,4,2,1,6,6,5,4,2,6,2,1,1,1,5,5], 2 -> [1,3,5,6,1,2,8,8,4,4,5,9,9,6,3,7,7,2]
[9,9,9,4,6,1,5,4,5,3,7,9,8,9,8,2,9,1,3,4,9,5,8,7,8,6,1,9,9,5,1,3,1,9,5,7,3,5,9,6,6,2,2,4,1,4,2,1,7,5,3,7,9,8,2,3,1,6], 9 -> [9,9,9,4,6,1,5,4,5,3,7,9,8,9,8,2,9,1,3,4,9,5,8,7,8,6,1,9,9,5,1,3,1,5,7,3,5,6,6,2,2,4,1,4,2,1,7,5,3,7,8,2,3,1,6]
[9,6,3,5,5,2,8,2,9,6,7,9,5,3,1,1,1,3,6,9,4,3,6,9,2,2,3,7,5,3,9,5,2,1,1,1,1,6,2,2,4,6,1,5,7,3,7,9,5,3,1,2,6,4,3,1,7,9,3,8,5,2,4,2,8,2,6,7,3,9,1,7,9,4,7,4], 5 -> [9,6,3,5,5,2,8,2,9,6,7,9,5,3,1,1,1,3,6,9,4,3,6,9,2,2,3,7,5,5,2,1,1,6,4,7,7,4,7,8,4,8,4]
[7,1,8,2,2,1,4,9,8,6,5,1,9,7,5,5,8,1,7,8,6,8,5,9,3,2,7,9,4,3,9,1,5,2,5,7,8,5,2,6,6,2,7,6,2,9,3,3,5,3,7,9,8,7,3,6,7,4,6,1,4,5,8,9,8,6,9,1,1,1,8,2,4,2,9,3,4,2,9,6], 8 -> [7,1,8,2,2,1,4,9,8,6,5,1,9,7,5,5,8,1,7,8,6,8,5,9,3,2,7,9,4,3,9,1,5,2,5,7,8,5,2,6,6,2,7,6,2,9,3,3,5,3,7,9,8,7,3,6,4,6,1,4,8,9,6,1,1,2,4,3,4]
[7,2,8,9,7,5,1,4,6,8,6,9,1,8,6,2,2,6,1,1,6,8,4,5,2,6,5,5,4,5,5,3,6,8,3,7,9,3,9,8,4,9,6,7,2,7,9,2,4,8,3,3,2,5,9,1,4,6,4,8,2,5,8,6,8,1,8,3,3,9,4,8,1,1,2,9,1,9,3,3,7], 11 -> [7,2,8,9,7,5,1,4,6,8,6,9,1,8,6,2,2,6,1,1,6,8,4,5,2,6,5,5,4,5,5,3,6,8,3,7,9,3,9,8,4,9,6,7,2,7,9,2,4,8,3,3,2,5,9,1,4,6,4,8,2,5,8,6,8,1,8,3,3,9,4,1,1,2,9,1,9,3,3,7]
[7,7,6,5,9,7,2,6,1,4,4,5,4,3,1,7,5,5,8,1,6,3,9,3,3,9,5,9,1,2,4,3,8,2,6,6,5,2,8,7,5,6,5,7,3,2,5,3,5,8,6,1,9,7,4,3,9,8,2,4,5,7,8,8,2,8,1,8,7,8,7,6,3,8,6,7,9,4,6,1,6,1,2,5,6,7,7,2,8,3,2,1,7], 11 -> [7,7,6,5,9,7,2,6,1,4,4,5,4,3,1,7,5,5,8,1,6,3,9,3,3,9,5,9,1,2,4,3,8,2,6,6,5,2,8,7,5,6,5,7,3,2,5,3,5,8,6,1,9,7,4,3,9,8,2,4,5,7,8,8,2,8,1,8,7,8,7,6,3,8,6,7,9,4,6,1,6,1,2,2,3,2,1]
[3,4,1,1,2,4,4,8,4,9,1,1,7,7,6,8,6,2,9,4,2,9,9,7,5,7,6,5,3,7,6,6,1,9,1,5,2,4,9,6,1,5,4,1,7,2,4,3,8,5,1,9,5,9,1,7,4,7,3,1,2,1,3,8,7,9,2,5,1,6,2,4,5,9,1,5,5,5,2,6,3,7,2,2,5,7,6,8,3,7,5,9,3,3,9], 7 -> [3,4,1,1,2,4,4,8,4,9,1,1,7,7,6,8,6,2,9,4,2,9,9,7,5,7,6,5,3,7,6,6,1,9,1,5,2,4,9,6,1,5,4,7,2,3,8,5,9,5,7,3,2,3,8,2,5,6,3,8,3]

Test case generator. Run with no arguments to have a max length of 100 for \$A\$. For a different max length (no larger than \$891\$), run with that as an argument.

Answer 1

AWK -vn=, 9

a[$1]++<n

This is so competitive with the golfing-language answers, I feel like I might have misunderstood the question - did I?

The limit n is passed as a variable at the command line with -vn=<value>. The array is read from STDIN.

Try it online!

Answer 2

Husk, 4 bytes

n¹*u

Try it online!

I've tried a few different ways, but Razetime's approach turned out to be very concise in Husk.

Explanation

n¹*u    Function of two arguments: A=[6,9,7,6,7,9,9], n=2
   u    Unique values of A: [6,9,7]
  *     Repeated n times: [6,9,7,6,9,7]
n¹      Intersected with A: [6,9,7,6,7,9]

Answer 3

JavaScript (ES6), 35 bytes

Expects (A)(n), where A is an array of digit characters.

a=>n=>a.filter(v=>!(a[~v]+=v)[n+9])

Try it online!

How?

We use the underlying object of a[] to keep track of the number of times each digit has appeared in the string.

By using ~v, we make sure that we use a property of the object (a negative value as a string) rather than an index of the array (which is already filled with the input values).

The first time we append v to a[~v], we get undefined coerced to a string followed by the digit character. Because "undefined" is 9 characters long, we know that we've reached n+1 occurrences of v by testing a[~v][n+9].

---

JavaScript (ES6), 37 bytes

Expects (A)(n), where A is an array of integers.

a=>n=>a.filter(v=>(a[~v]=-~a[~v])<=n)

Try it online!

Answer 4

Stax, ⁶ 5 bytes

°º☻¿_

Run and debug it

Output as a string of codepoints(since stax prints all numeric arrays as strings). Verifiable version

Explanation

cua*|b
c       copy the list
 u      uniquify
  a     bring the count to the top
   *    repeat the elements n times
    |b  multiset intersect

Answer 5

MATL, 9 bytes

t&=Rsi>~)

Inputs A, then n. Try it online!

Or verify all test cases. For each case this takes a third input containing the desired output. The footer code checks if the program output equals the desired output, and prints Correct or Incorrect accordingly.

How it works

Consider inputs [1 2 3 2 3 2 4 1 2] and 2 as an example.

t    % Implicit input: array A. Duplicate
     % STACK: [1 2 3 2 3 2 4 1 2], [1 2 3 2 3 2 4 1 2]
&=   % Matrix of pairwise comparisons
     % STACK: [1 2 3 2 3 2 4 1 2], [1 0 0 0 0 0 0 1 0
                                    0 1 0 1 0 1 0 0 1;
                                    0 0 1 0 1 0 0 0 0;
                                    0 1 0 1 0 1 0 0 1;
                                    0 0 1 0 1 0 0 0 0;
                                    0 1 0 1 0 1 0 0 1;
                                    0 0 0 0 0 0 1 0 0;
                                    1 0 0 0 0 0 0 1 0;
                                    0 1 0 1 0 1 0 0 1]
R    % Upper triangular part: sets entries below the diagonal to 0
     % STACK: [1 2 3 2 3 2 4 1 2], [1 0 0 0 0 0 0 1 0;
                                    0 1 0 1 0 1 0 0 1;
                                    0 0 1 0 1 0 0 0 0;
                                    0 0 0 1 0 1 0 0 1;
                                    0 0 0 0 1 0 0 0 0;
                                    0 0 0 0 0 1 0 0 1;
                                    0 0 0 0 0 0 1 0 0;
                                    0 0 0 0 0 0 0 1 0;
                                    0 0 0 0 0 0 0 0 1]
s    % Sum of each column. For each entry of A this gives the number
     % of repetitions up to that point
     % STACK: [1 2 3 2 3 2 4 1 2], [1 1 1 2 2 3 1 2 4]
i    % Input: number a
     % STACK: [1 2 3 2 3 2 4 1 2], [1 1 1 2 2 3 1 2 4], 2
>~   % Less than or equal? Element-wise
     % STACK: [1 2 3 2 3 2 4 1 2], [1 1 1 1 1 0 1 1 0]
)    % Apply as an index (logical mask)
     % STACK: [1 2 3 2 3 4 1]
     % Implicit display

Answer 6

J, 13 bytes

(>:1#.]=]\)#]

Try it online!

Answer 7

Husk, 9 bytes

fm≤⁰Sz#ḣ³

Try it online!

f           # filter input to retain only elements at positions of truthy values of
 m≤⁰        # elements less-than-or-equal to arg 2 of
    Sz#     # count the occurrences of each element of arg1
       ḣ³   # in the list of prefixes of arg1

Answer 8

J, 17 bytes

0-.~]-1&(]*(-~:))

Try it online!

Apparently, this is shorter than a solution using Self-classify = or self equality =/~.

How it works

0-.~]-1&(]*(-~:))  NB. left: n, right: A
      1&(       )  NB. Apply this function on A, n times...
      1    (-~:)   NB.   Negation of Nub Sieve (mark first occurrence of each number)
         ]*        NB.   Multiply to A so that each first occurrence becomes 0
    ]-             NB. Kill (change to 0) survivors of ^ from the original A
0-.~               NB. Erase zeros by set difference

Illustration:

n = 2, A = 2 3 8 1 6 4 8 2 8 3
First iteration:
Nub sieve of A = 1 1 1 1 1 1 0 0 0 0
Kill them      = 0 0 0 0 0 0 8 2 8 3

Second iteration:
Nub sieve of ^ = 1 0 0 0 0 0 1 1 0 1
Kill them      = 0 0 0 0 0 0 0 0 8 0

Kill the survivors of ^ = 2 3 8 1 6 4 8 2 0 3
Erase zeros by set diff = 2 3 8 1 6 4 8 2 3

Answer 9

Python 3, 57 bytes

lambda a,n:[e for i,e in enumerate(a)if a[:i].count(e)<n]

Try it online!

Answer 10

Haskell, 44 bytes

f n=foldl(\r x->r++[x|sum[1|y<-r,y==x]<n])[]

Try it online!

Answer 11

Python 2, 50 bytes

lambda s,n:reduce(lambda r,x:r+x*(r.count(x)<n),s)

Try it online!

-2 bytes from Leo by taking input and output as a string of digits, which is also used in the answers below

---

Python 3.8 (pre-release), 53 bytes

lambda s,n,r='':[x for x in s if(r:=r+x).count(x)<=n]

Try it online!

Input and output as list of characters.

---

55 bytes

f=lambda s,n:s and f(s[:-1],n)+s[-1][s.count(s[-1])>n:]

Try it online!

Repeatedly takes and removes the last element of the list, keeping it if it appears a maximum of n times in the current list.

It feels like there should be a better way to express this, but I'm not seeing it. Python is clumsy at dealing with the end of a list. While l[-k:] usually takes the last k elements from the end, for k=0 it instead takes the whole list. So, I didn't find a nice single slice that conditionally takes 0 or 1 elements from the end of a list. Also, doing l.pop() has the trouble that the recursive function call comes before the expression where we want the last element.

Answer 12

PowerShell Core, 38 37 bytes

$a,$b=$args
$t=@{}
$a|?{++$t.$_-le$b}

-1 byte thanks to mazzy!

Try it online!

Answer 13

R, 48 bytes

function(x,n)x[diag(diffinv(outer(x,x,"=="))<n)]

Try it online!

Test harness taken from Dominic's answer.

Closely related to Luis Mendo's answer, though implementing it in MATL is longer. Rather than zeroing out the lower triangle of the matrix and computing the column sums, this calculates the cumulative sum of each column, then takes the diagonal of the resulting matrix as the filtering criterion -- for some element \$a_i\$ this tells the number of occurrences of \$a_i\$ before index \$i\$.

So for instance, using [6,9,7,6,7,9,9]:

Pairwise equality check:
     [,1] [,2] [,3] [,4] [,5] [,6] [,7]
[1,]    1    0    0    1    0    0    0
[2,]    0    1    0    0    0    1    1
[3,]    0    0    1    0    1    0    0
[4,]    1    0    0    1    0    0    0
[5,]    0    0    1    0    1    0    0
[6,]    0    1    0    0    0    1    1
[7,]    0    1    0    0    0    1    1

Column-wise cumulative sum (with an initial condition of 0):
     [,1] [,2] [,3] [,4] [,5] [,6] [,7]
[1,]    0    0    0    0    0    0    0
[2,]    1    0    0    1    0    0    0
[3,]    1    1    0    1    0    1    1
[4,]    1    1    1    1    1    1    1
[5,]    2    1    1    2    1    1    1
[6,]    2    1    2    2    2    1    1
[7,]    2    2    2    2    2    2    2
[8,]    2    3    2    2    2    3    3
The diagonal:
[1] 0 0 0 1 1 1 2

Answer 14

K (ngn/k), 18 16 bytes

{x@&~y<+/'x=,\x}

Try it online!

Adapted from @rak1507's message in the APL Orchard. Takes the list as x and the number of occurrences as y.

• +/'x=,\x get the running totals of the counts of each number in the input
• &~y< get indices of the first y instances of each value
• x@ index back into the input

Answer 15

APL (Dyalog Unicode), 23 19 bytes

Saved a couple bytes by looking at Bubbler how negated the mask in their answer.

{⍺/⍨(⊢∨(≠⍺×~))⍣⍵⊢0}

Don't try it online! because TIO has an older version of Dyalog APL without Unique Mask.

Takes the array on the left and n on the right.

This takes advantage of monadic ≠, which gives a mask to obtain unique elements. While ≠A lets you keep unique elements in A, the mask 1-≠A inverts it and lets you keep only repeated elements in A. Then A×1-≠A replaces unique elements with zeroes (this is safe because as the question states, A only contains numbers 1-9). The mask ≠A×1-≠A gives us only unique elements from this new array, but since we replaced unique elements, it lets us keep duplicates (and the first element, but that is always kept no matter what anyway). (≠A)∨≠A×1-≠A now gives us a mask for unique elements and duplicates, but not triplicates, etc. By repeating this process n times, we get a mask for keeping only n-plicates, and then we just apply that mask to A to get the result.

Answer 16

Jelly, 5 bytes

œ&Qx¥

Try it online!

Accidental translation of Razetime's Stax answer based on his comment.

œ&       Multiset intersection of A with
  Q ¥    the unique elements of A
   x     repeated n times.

Jelly, 7 bytes

xċṪ$Ƥ<¥

Try it online!

I was going to hold off on posting until I tied caird's 6 bytes, but I feel like I'm so far off the mark that it's worth documenting anyhow.

x     ¥    Repeat each element of A by the corresponding elements of:
    Ƥ      for each prefix of A,
 ċ         how many times it contains
  Ṫ$       its last element (which is then not considered).
     <     Is each count less than n?

Answer 17

Java, 157 bytes

l->n->java.util.stream.IntStream.range(0,l.length).filter(i->java.util.stream.IntStream.range(0,i+1).filter(j->l[j]==l[i]).count()<=n).map(i->l[i]).toArray()

Takes a int[] and the integer n as input and returns a int[].

Try it online!

Answer 18

R, 62 bytes

function(x,n)x[sapply(seq(x),function(i)sum(x[1:i]==x[i]))<=n]

Try it online!

---

...although a port of Luis Mendo's answer is shorter at 59 58 bytes (Thanks to Giuseppe)

Answer 19

T-SQL, 114 bytes

SELECT C FROM (SELECT B,C,row_number() OVER (PARTITION BY C ORDER BY B) AS D FROM @A) E WHERE D <= @n ORDER BY B;

Example:

DECLARE @A TABLE(B INT IDENTITY(1,1), C INT);
DECLARE @n INT;
INSERT INTO @A SELECT * FROM (VALUES(1),(2),(3),(2),(3),(2),(4),(1),(2)) AS A(C);
SET @n = 2;

SELECT C --4.Finally select the filtered rows
FROM (SELECT B
            ,C
            ,row_number() OVER (PARTITION BY C ORDER BY B) AS D --1.Create an ordinal for each repetition that increments in ascending order of B
      FROM @A
      ) E 
WHERE D <= @n --2.Filter on the windowed function in subquery, removing rows with more than n repetitions
ORDER BY B; --3. Preserve original order of table variable @A (Can't order by in subquery)

Returns:

	C
1	1
2	2
3	3
4	2
5	3
6	4
7	1

Only way I could simulate an 'array' was by making a table with an identity on insert to store the insertion order.

Answer 20

Retina 0.8.2, 52 bytes

\d+$
$*
(.)(?=.*,(.)+)(?<=(?(2)$)(?<-2>\1.*)+.)|,.+

Try it online! Link includes test cases. Takes A as a string of digits and n as a positive integer separated by a comma. Explanation:

\d+$
$*

Convert n to unary.

(.)(?=.*,(.)+)(?<=(?(2)$)(?<-2>\1.*)+.)|,.+

Delete any digit of A that is preceded by at least n identical digits and also delete n from the result.

Answer 21

Perl 5 -al, 28 bytes

$l=<>;map$k{$_}++<$l&&say,@F

Try it online!

Answer 22

Ruby, 38 bytes

->a,n{w=[0]*10;a.reject{|x|n<w[x]+=1}}

Try it online!

Answer 23

C# (Visual C# Interactive Compiler), 56 bytes

(a,n)=>{var b=new int[10];return a.Where(c=>b[c]++<n);} 

Try it online!

Or 66 bytes if output should explicitly be an array vs an enumerable:

(a,n)=>{var b=new int[10];return a.Where(c=>b[c]++<n).ToArray();} 

Try it online!

Answer 24

Japt, 8 bytes

fVÆâÃc 2

Try it online! or Check all test cases

Very similar to the Jelly, Stax, and Husk answers.

Explanation:

            # Implicitly store the input array as U and the input number as V
 VÆ         # Create an array of length V
   âà       #  Each item in the array is the unique elements of U
     c      # Flatten that array
f           # Only keep elements of U that are in that array...
       2    # ... up to the number of times it appears in that array

Answer 25

Charcoal, 11 bytes

ＮθΦη‹№…ηκιθ

Try it online! Link is to verbose version of code. Takes input n as an integer and A as a string of digits. Explanation:

Ｎθ          Input `n` as an integer
   η        Input `A`
  Φ         Filtered where
     №      Count of
         ι  Current character in
      …ηκ   Prefix so far
    ‹       Is less than
          θ Input `n`
            Implicitly print

Answer 26

Julia 1.0, 46 43 bytes

l$n=(j=0;!i=sum(l[1:(j+=1)].==i)<=n;l[.!l])

Try it online!

Answer 27

C (clang), 62 bytes

f(*l,n){for(int m[10]={0};*l;++l)m[*l]++<n&&printf("%d ",*l);}

Try it online!

• Expects a 0 terminated array as input

If tacking a 0 filled array as an additional input is valid:

C (clang), 58 bytes

f(*l,n,*o){for(int m[10]={0};*l;++l)m[*l]++<n&&(*o++=*l);}

Try it online!

Answer 28

Haskell, 54 bytes

f n|let a?x|sum[1|y<-a,y==x]<n=a++[x]|1>0=a=foldl(?)[]

Try it online!

• I was on the right track, one big step behind @xnor answer which cost me 10 bytes!

Answer 29

Clojure, 76 bytes

#(for[[i v](map vector(range)%1):when(<(count(filter #{v}(take i %1)))%2)]v)

Try it online!

Answer 30

SNOBOL4 (CSNOBOL4), 87 bytes

	N =INPUT
	T =TABLE()
R	I =INPUT	:F(END)
	T<I> =T<I> + 1
	OUTPUT =I LE(T<I>,N)	:(R)
END

Try it online!

Takes input as N, then A, each element separated by newlines.

	N =INPUT			;* Read in N, number to keep
	T =TABLE()			;* create an empty table
R	I =INPUT	:F(END)		;* read in the next input; if none exists, exit
	T<I> =T<I> + 1			;* increment the value at index I (initially 0)
	OUTPUT =I LE(T<I>,N)	:(R)	;* if T<I> is LEQ to N, then output I. Goto R.
END