Most Common Multiple

28

Not to be confused with Least Common Multiple.

Given a list of positive integers with more than one element, return the most common product of two elements in the array.

For example, the MCM of the list [2,3,4,5,6] is 12, as a table of products is:

    2  3  4  5  6
  ---------------
2 | #  6  8  10 12
3 | #  #  12 15 18
4 | #  #  #  20 24
5 | #  #  #  #  30
6 | #  #  #  #  #

Thanks DJMcMayhem for the table

As 12 appears the most times (two times as 2*6 and 3*4). Note that we aren't including the product of an element and itself, so 2*2 or 4*4 do not not appear in this list. However, identical elements will still be multiplied, so the table for [2,3,3] looks like:

    2  3  3
  ----------
2 | #  6  6 
3 | #  #  9
3 | #  #  #

With the MCM being 6.

In the event of a tie, you may return any of the tied elements, or a list of all of them.

  • This is , so the shortest byte count for each language wins!

Test-cases:

[2,3,4,5,6] -> 12
[7,2] -> 14
[2,3,3] -> 6
[3,3,3] -> 9
[1,1,1,1,2,2] -> 2
[6,200,10,120] -> 1200
[2,3,4,5,6,7,8,8] -> 24
[5,2,9,10,3,4,4,4,7] -> 20
[9,7,10,9,7,8,5,10,1] -> 63, 70, 90 or [63,70,90]

Jo King

Posted 2018-08-06T10:38:31.977

Reputation: 38 234

Sandbox (deleted) – Jo King – 2018-08-06T10:39:34.607

5Suggested test case: one where all elements are the same (i.e. [3,3,3] -> 9). With all your current test cases filtering out any pairs where elements are the same (even for test cases like [2,3,3] containing the same values) will still hold the correct test-results, but will fail for this test case because none will remain after filtering. – Kevin Cruijssen – 2018-08-06T12:07:30.723

@Kevin Good suggestion, added – Jo King – 2018-08-06T12:38:59.330

Answers

11

Brachylog, 11 bytes

{⊇Ċ×}ᶠọtᵒth

Try it online!

Explanation

{   }ᶠ          Find all:
 ⊇Ċ×              Product of a subset of 2 elements
      ọtᵒ       Order by occurrences
         th     Take the last element and discard the number of occurrences

Fatalize

Posted 2018-08-06T10:38:31.977

Reputation: 32 976

I don't know how code golf usually works but aren't some of these characters outside the standard 256 code points and therefore multiple bytes each? – Holloway – 2018-08-07T12:02:05.860

2

@Holloway Brachylog uses a custom code page

– Fatalize – 2018-08-07T12:07:13.423

11

R, 54 50 41 bytes

order(-tabulate(combn(scan(),2,prod)))[1]

Try it online!

Alternatively, for 54 53 44 bytes:

names(sort(-table(combn(scan(),2,prod))))[1]

Try it online!

In principle, the latter version outputs the relevant result even without the names function, but followed by the count of such most frequent products, which isn't asked for...

Thanks to CriminallyVulgar for -4 and -1, and Giuseppe for -9 on both.

Kirill L.

Posted 2018-08-06T10:38:31.977

Reputation: 6 693

1

On the second on you can use -table() instead of descending=TRUE for -1. I really like the cleverness of the first one though. EDIT: Just realised you can also apply that to the first one for -4, so there's that. Try it online!

– CriminallyVulgar – 2018-08-06T12:59:15.343

1combn(scan(),2,prod) works instead of using apply – Giuseppe – 2018-08-06T13:24:50.020

8

Jelly, 6 bytes

ŒcP€Æṃ

Try it online! or Check out the test suite.

How it works

ŒcP€Æṃ – Full program / Monadic link.
Œc     – Unordered pairs without replacement.
  P€   – Product of each.
    Æṃ – Mode (most common element).

Alternative: ŒcZPÆṃ

Mr. Xcoder

Posted 2018-08-06T10:38:31.977

Reputation: 39 774

7

Pyth, 12 bytes

eo/QN=*M.cQ2

Test suite

First, we take all 2 element combinations of the input without replacement (.cQ2). Then, we map each of these pairs to their product (*M). Next, we overwrite the input variable with the list of products (=). Next, we sort the list of products by the number of occurrences in the list of products (o/QN). Finally, the take the final element of the sorted list (e).

isaacg

Posted 2018-08-06T10:38:31.977

Reputation: 39 268

7

MATL, 8 7 bytes

2XN!pXM

Try it online!

(-1 byte by using the method from @Mr. Xcoder's Jelly answer.)

2XN     % nchoosek - get all combinations of 2 elements from input
!p      % get the product of each combination
XM      % 'mode': get the most common value from that

Older answer:

8 bytes

&*XRXzXM

Try it online!

&*    % multiply input by its transpose,
      %  getting all elementwise products
XR    % take the upper-triangular portion of that,
      %  zeroing out repetitions and mainly self-multiplications
Xz    % remove the zeroed out parts
XM    % 'mode' calculation - get the most common value from that

sundar - Reinstate Monica

Posted 2018-08-06T10:38:31.977

Reputation: 5 296

6

Mathematica, 32 bytes

-17 bytes (and a fix) thanks to JungHwan Min.

Commonest[1##&@@@#~Subsets~{2}]&

Pure function. Takes a list of numbers as input and returns the list of MCMs as output.

LegionMammal978

Posted 2018-08-06T10:38:31.977

Reputation: 15 731

Actually it looks like both of us misread the question. This fails for input {3, 3, 3}. Fixed: Commonest[1##&@@@#~Subsets~{2}]& – JungHwan Min – 2018-08-06T20:21:30.753

@JungHwanMin Huh. I thought that Subsets didn't count repeats as separate elements. It seems like it does, though, so thanks! – LegionMammal978 – 2018-08-07T01:28:30.057

6

05AB1E, 8 6 bytes

æ2ùP.M

-2 bytes thanks to @Kaldo.

Try it online or verify all test cases.

Explanation:

æ         # Take the powerset of the input-list
          #  i.e. [2,3,3] → [[],[2],[3],[3],[2,3],[2,3],[3,3],[2,3,3]]
 2ù       # Leave only the inner lists of size 2:
          #  i.e. [[],[2],[3],[3],[2,3],[2,3],[3,3],[2,3,3]] → [[2,3],[2,3],[3,3]]
   P      # Take the product of each remaining pair
          #  i.e. [[2,3],[2,3],[3,3]] → [6,6,9]
    .M    # Only leave the most frequent value(s) in the list
          #  i.e. [6,6,9] → [6]

Kevin Cruijssen

Posted 2018-08-06T10:38:31.977

Reputation: 67 575

1æ2ùP.M for 6 bytes – Kaldo – 2018-08-06T12:22:22.560

@Kaldo Thanks! Completely forgot about ù. – Kevin Cruijssen – 2018-08-06T12:30:21.210

5

Perl 6, 41 38 bytes

{key max bag(@_ X*@_)∖@_»²: *{*}:}

Try it online!

nwellnhof

Posted 2018-08-06T10:38:31.977

Reputation: 10 037

Could you please explain to me (or point me to the docs) what are the colons doing there? I can't quite make it out... I can see that it has something to do with argument passing but nothing more. – Ramillies – 2018-08-06T22:08:27.043

1

@Ramillies That's the infix : operator.

– nwellnhof – 2018-08-06T23:18:02.117

Ah, I see. Thank you. – Ramillies – 2018-08-06T23:22:38.423

5

MATLAB, 43 bytes

I=input('');i=I'*I*1-eye(nnz(I));mode(i(:))

It's also kind of a tongue twister!

Explanation

I=input('');           % Takes an input like "[2,3,4,5,6]"
i=I'*I                 % Multiplies the input by its own transverse
      *1-eye(nnz(I));  % Multiplies by 1-identity matrix to remove diagonal
mode(i(:))             % Calculates most common value and prints it

Jacob Watson

Posted 2018-08-06T10:38:31.977

Reputation: 131

1i am not sure you need to do I'*I*1-eye Why not just I'*I-eye? – aaaaa says reinstate Monica – 2018-08-08T00:45:12.580

4

Stax, 12 10 bytes

╢êv^⌐ö►♣Ä»

Run and debug it

wastl

Posted 2018-08-06T10:38:31.977

Reputation: 3 089

4

JavaScript (ES6), 72 70 bytes

a=>a.map(m=o=(y,Y)=>a.map(x=>Y--<0?m=(o[x*=y]=-~o[x])<m?m:o[r=x]:0))|r

Try it online!

Arnauld

Posted 2018-08-06T10:38:31.977

Reputation: 111 334

@tsh The problem is the main diagonal, where multiples should not be counted at all. So it fails for the penultimate test case which has three $16$ on the main diagonal, bringing its score high enough to be returned instead of the expected $20$. – Arnauld – 2018-11-19T08:40:14.753

4

Python 3, 77 72 bytes

f=lambda k,*l,m=[]:l and f(*l,m=m+[k*x for x in l])or max(m,key=m.count)

Try it online!

ovs

Posted 2018-08-06T10:38:31.977

Reputation: 21 408

4

Attache, 59 bytes

Last##~SortBy#`&&:`~##{Flat[UpperTriangle&1!Table&_!`*]^^0}

Try it online!

Still working on golfing this down a bit, but I think this is near optimal for the approach I've chosen.

Explanation

This is a composition of three functions:

  1. {Flat[UpperTriangle&1!Table&_!`*]^^0}
  2. SortBy#`&&:`~
  3. Last

The first function does the bulk of the computation:

{Flat[UpperTriangle&1!Table&_!`*]^^0}
{                                   }    anonymous lambda; input: _ (e.g.: [2,3,4,5,6])
                      Table&_!`*         shorthand for Table[`*, _]
                                         this creates a multiplication table using the input
                                         e.g.:
                                           4  6  8 10 12
                                           6  9 12 15 18
                                           8 12 16 20 24
                                          10 15 20 25 30
                                          12 18 24 30 36

      UpperTriangle&1!                   takes the strict upper triangle of this matrix
                                         e.g.:
                                          0 6  8 10 12
                                          0 0 12 15 18
                                          0 0  0 20 24
                                          0 0  0  0 30
                                          0 0  0  0  0
Flat[                           ]^^0     flattens this list and removes all 0s
                                         e.g.: [6, 8, 10, 12, 12, 15, 18, 20, 24, 30]

The second is a bit complicated but does something rather simple. First, it is useful to know that f&n is a function which, when called with arguments ...x, returns f[...x, n]. f&:n is similar, returning f[n, ...x]. Now, let's decompose this:

( ~SortBy ) # (`& &: `~)

First, f#g creates a fork. With input n, it returns f[n, g[n]]. However, in this case, f is the function ~SortBy. ~f reverses the arguments of the function. This means that ~f#g is equivalent to f[g[n], n], or here, SortBy[(`& &: `~)[n], n].

`& &: `~ follows the form f&:n. But what are `& and `~? They are "operator quotes", and return a function equivalent to the quoted operator. So, in this case, `& is the same thing as ${ x & y }. With that in mind, this expression is equivalent to the following for binary operators:

f&:n   <=>   ${ f[n, x] }
       <=>   ${ (`&)[`~, x] }
       <=>   ${ `~ & x }

This yields the function `~&x, where x is the result from the first function. n ~ a counts the occurrences of n in a. So, this returns a function which counts the occurrences of the argument in the computed array from function 1.

Going back to SortBy, this each element in the array by the number of times it appears in it.

Finally, Last takes the element which occurs the most. Ties are broken by the sorting algorithm.

Conor O'Brien

Posted 2018-08-06T10:38:31.977

Reputation: 36 228

Is the UpperTriangle part required? Can you just flatten the table and sort? – svavil – 2018-08-07T12:14:19.247

@svavil Yes, it is required; [5, 2, 9, 10, 3, 4, 4, 4, 7] -> 16 instead of 20 without it. – Conor O'Brien – 2018-08-07T18:41:18.653

3

Charcoal, 24 bytes

WθF×⊟θθ⊞υκI⊟Φυ⁼№υι⌈Eυ№υλ

Try it online! Link is to verbose version of code. Explanation:

Wθ

While the input array is non-empty...

×⊟θθ

... pop the last element and multiply the rest of the array by that element...

F...⊞υκ

... and push the results to the predefined empty list.

⌈Eυ№υλ

Count the number of times each product appears in the list and take the maximum...

Φυ⁼№υι...

... then filter for the products whose count equals that maximum...

I⊟

...then pop the last element and cast to string for implicit print.

Neil

Posted 2018-08-06T10:38:31.977

Reputation: 95 035

3

APL (Dyalog Unicode), 29 27 19 bytes

{⌈/⊢/⊣¨⌸∊⍵}⍳∘≢↓¨⊢×⊂

Try it online!

Tacit fn.

Thanks to Adám for the tacit version and 2 bytes.

Thanks to ngn for 8 bytes!

How:

{⌈/⊢/⊣¨⌸∊⍵}⍳∘≢↓¨⊢×⊂
                ⊢×⊂   ⍝ Multiply each element with the entire argument, then
           ⍳∘≢↓¨      ⍝ Remove 1 from the first, two from the next etc. (removes repeated multiplications);
                      ⍝ The result is then fed into the function:
{       ∊⍵}           ⍝ Flatten the result;
     ⊣¨⌸              ⍝ Key; creates a matrix in which each row corresponds to a unique product;
   ⊢/                 ⍝ Get the rightmost column of the matrix;
 ⌈/                   ⍝ Get the highest value.

J. Sallé

Posted 2018-08-06T10:38:31.977

Reputation: 3 233

1

This is only 27.

– Adám – 2018-08-07T15:18:46.317

3

Japt, 20 16 bytes

  • -4 bytes from @Shaggy

£s°Y m*XÃc
ñ@è¥X

Try it online!

Luis felipe De jesus Munoz

Posted 2018-08-06T10:38:31.977

Reputation: 9 639

16 bytes – Shaggy – 2018-09-04T09:09:21.450

3

Husk, 7 bytes

Ṡ►#mΠṖ2

Try it online!

Explanation

Ṡ►#mΠṖ2  -- example input [3,3,3]
     Ṗ2  -- subsequences of length 2: [[3,3],[3,3],[3,3]]
   mΠ    -- map product: [9,9,9]
Ṡ        -- apply 
  #      -- | count occurences in list
 ►       -- to maxOn that list: [9]

ბიმო

Posted 2018-08-06T10:38:31.977

Reputation: 15 345

3

CJam, 70 68 bytes

q',/S*~_,(:L{LX-,0a\+[{X1++}*](;{_X=\_Y=@*\}fY}fX]~;]_{\_@e=}$\;_,(=

Try it online!

Explanation

q',/S*~                                                                  Turn input string into a valid CJam array
       _,(                                                               Find the length of the array and subtract 1
          :L                                                             Assign the result to L
            {                                 }fX                        Outer for loop
             LX-,0a\+[{X1++}*](;                                         Create an array with all the array indexes bigger than X
                                {          }fY                           Inner for loop
                                 _X=\_Y=@*\                              Create a multiple of array[X] and array[Y] (Guaranteed to be from a unique combination of factors)
                                                 ~;]                     Casts away all stack items except for an array of the multiples
                                                    _{\_@e=}$\;          Sorts array by number of occurrences (largest number of occurences at the end)
                                                               _,(=      Gets the last element of the array

You will need to scroll right to see the explanations as the code is quite long, as well as the explanations.


This was an absolute nightmare to write. CJam doesn't have a powerset function (unlike a ton of other golfing languages - great choice on my part), which means that I had to manually find the powerset. However, this gave me the opportunity to ignore any invalid number of factors, unlike other answers with a powerset function.

This should be golfable, considering I'm terrible at CJam.


Changes:

Helen cut off 2 bytes!

Old: q',/S*~_,1-:L{LX-,0a\+[{X1++}*](;{_X=\_Y=@*\}fY}fX]~;]_{\_@e=}$\;_,1-=
New: q',/S*~_,(:L{LX-,0a\+[{X1++}*](;{_X=\_Y=@*\}fY}fX]~;]_{\_@e=}$\;_,(=

By changing the 1-s to simply ( we get the same effect but with a lower byte count.

Helen

Posted 2018-08-06T10:38:31.977

Reputation: 125

2

Java (JDK 10), 132 bytes

a->{int l=a.length,i=l,j=0,r=99999,m[]=new int[r];for(;i-->0;)for(j=l;--j>i;)m[a[i]*a[j]]++;for(;r-->0;)i=m[r]<i?i:m[j=r];return j;}

Try it online!

Olivier Grégoire

Posted 2018-08-06T10:38:31.977

Reputation: 10 647

2

Haskell, 96 94 bytes

-2 bytes thanks to nimi (using sortOn(0<$) instead of length)!

import Data.List
f a|b<-zip[0..]a=last.last.sortOn(0<$).group$sort[x*y|(i,x)<-b,(j,y)<-b,i/=j]

Try it online!

ბიმო

Posted 2018-08-06T10:38:31.977

Reputation: 15 345

2

MATLAB 39 bytes

a=input('');
b=triu(a'*a,1);
mode(b(b~=0))

Also check out answer by Jacob Watson

aaaaa says reinstate Monica

Posted 2018-08-06T10:38:31.977

Reputation: 381

1Having the second line be b=triu(a'*a,1); saves 4 bytes. – sundar - Reinstate Monica – 2018-08-08T12:32:32.127

@sundar Oh snap, you are right :) I had triu intially but drifted away somehow – aaaaa says reinstate Monica – 2018-08-08T14:47:42.107

Good solution, I didn't realise the upper triangle function was so short! – Jacob Watson – 2018-08-10T08:19:46.953

2

SQL Server, 93 bytes

SELECT TOP 1a.a*b.a
FROM @ a
JOIN @ b ON a.i<b.i
GROUP BY a.a*b.a
ORDER BY COUNT(a.a*b.a)DESC

Input is assumed to come from a table of the form

DECLARE @ TABLE (A int, i int identity);

Example table population:

INSERT INTO @ VALUES (9), (7), (10), (9), (7), (8), (5), (10), (1);

Explanation:

I assume a "list of integers" will have an index associated with them, which in my case is the column i. The column a contains the values of the list.

I create products of every pair, where the left pair comes in the list earlier than the right pair. I then group on the product, and sort by the most populous number.

I'm a little sad I didn't get to use any cte or partitioning clauses, but they were just too long. SELECT is a very expensive keyword.

Alternative, 183 bytes

WITH c
AS(SELECT a,ROW_NUMBER()OVER(ORDER BY a)r
FROM @),d AS(SELECT a.a*b.a p,COUNT(a.a*b.a)m
FROM c a
JOIN c b ON a.r<b.r GROUP BY a.a*b.a)SELECT TOP 1p
FROM d
ORDER BY m DESC

If SQL doesn't get to have a separate index column, here is a solution where I create an index using the ROW_NUMBER function. I personally don't care about the order, but an order is required and using the a column is the shortest.

Brian J

Posted 2018-08-06T10:38:31.977

Reputation: 653

2

CJam, 29 bytes

q~:L,2m*{:-},{Lf=:*}%$e`:e>1=

Try it online!

Erik the Outgolfer

Posted 2018-08-06T10:38:31.977

Reputation: 38 134

2

Burlesque - 8 bytes

Jcp)pdn!

J        duplicate
 cp      cross product
   )pd   map . product
      n! most common element

Try it online here.

(and yes, Burlesque also has a command for "least common element")

mroman

Posted 2018-08-06T10:38:31.977

Reputation: 1 382

2

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

x=>x.SelectMany(y=>(x=x.Skip(1)).Select(z=>y*z)).GroupBy(y=>y).OrderBy(y=>y.Count()).Last().Key

Try it online!

Less golfed code:

// x is a list of integers
x=>
  // iterate over each integer and
  // return a list per element.
  // flatten the list of lists to 1 list
  x.SelectMany(y=>
    // skip the current value and save
    // newly offset list to x so that it
    // can be incrementally offset
    // again next pass
    (x=x.Skip(1))
      // compute the product
      .Select(z=>y*z))
    // get the unique products
    .GroupBy(y=>y)
    // sort the products by number
    // of occurrences
    .OrderBy(y=>y.Count())
    // pick the product with the
    // greatest number of occurrences
    .Last().Key

dana

Posted 2018-08-06T10:38:31.977

Reputation: 2 541

1

PHP, 91 bytes

while($c=$argv[++$i])for($k=$i;--$k;)$r[$c*$argv[$k]]++;asort($r);echo end(array_flip($r));

takes input from command line arguments; run with -nr or try it online.

Use PHP 7 to avoid STRICT MODE warning.

Titus

Posted 2018-08-06T10:38:31.977

Reputation: 13 814

1

J, 29 25 24 23 bytes

(0{~.\:1#.=)@(</#&,*/)~

Try it online!

how

(~. {.@\: 1 #. =)@(</ #&, */)~
                  (</ #&, */)~  NB. all products, dups removed:
                          */    NB. create the times table
                   </           NB. lower triangular ones matrix
                       &,       NB. flatten each and
                      #         NB. filter based on lower triangle
                 @              NB. pass that result to
(~. {.@\: 1 #. =)               NB. get the most frequent list item:
       \:                       NB. sort down
 ~.                             NB. the uniq elements
          1 #. =                NB. by their count
    {.@                         NB. and take the first element

Jonah

Posted 2018-08-06T10:38:31.977

Reputation: 8 729

1

Japt -h, 11 bytes

à2 ®×Ãü ñÊÌ

Try it

á2 ®×
ñ@è¥X

Try it

Shaggy

Posted 2018-08-06T10:38:31.977

Reputation: 24 623

0

APL(NARS), 53 chars, 106 bytes

{0=l←↑⍴⍵:⍵⋄t⊃⍨q⍳⌈/q←{+/t=⍵}¨t←×/¨(∊(⍳l)∘.<⍳l)/,⍵∘.,⍵}

Test:

  p←{0=l←↑⍴⍵:⍵⋄t⊃⍨q⍳⌈/q←{+/t=⍵}¨t←×/¨(∊(⍳l)∘.<⍳l)/,⍵∘.,⍵}
  p 9
9
  p 1 3
3
  p 2 3 4 5 6
12
  p 7 2
14
  p 2 3 3
6
  p 3 3 3
9
  p 1 1 1 1 2 2
2
  p 6 200 10 120
1200
  p 2 3 4 5 6 7 8 8
24
  p 5 2 9 10 3 4 4 4 7
20
  p 9 7 10 9 7 8 5 10 1
63
  p 3 3
9

RosLuP

Posted 2018-08-06T10:38:31.977

Reputation: 3 036