Most Common Multiple

Question

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 code-golf, 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]

Answer 1

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

Answer 2

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.

Answer 3

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Æṃ

Answer 4

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).

Answer 5

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

Answer 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]

Answer 7

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.

Answer 8

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

Answer 9

Perl 6, 41 38 bytes

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

Try it online!

Answer 10

Stax, 12 10 bytes

╢êv^⌐ö►♣Ä»

Run and debug it

Answer 11

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!

Answer 12

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.

Answer 13

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!

Answer 14

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.

Answer 15

Thunno 2, 5 bytes

2ċ€pṀ

Explanation

2ċ€pṀ  # Implicit input
2ċ     # Combinations of length 2 of the input
  €p   # Product of each pair in this list
    Ṁ  # Mode of this list
       # Implicit output

Screenshot

Answer 16

Charcoal, 24 bytes

ＷθＦ×⊟θθ⊞υκＩ⊟Φυ⁼№υι⌈Ｅυ№υλ

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

Ｗθ

While the input array is non-empty...

×⊟θθ

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

Ｆ...⊞υκ

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

⌈Ｅυ№υλ

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...

Ｉ⊟

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

Answer 17

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]

Answer 18

Japt, 20 16 bytes

• -4 bytes from @Shaggy

---

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

Try it online!

Answer 19

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.

Answer 20

Vyxal, ⁷ 6 bytes

-1 byte thanks to The Thonnu

2ḋvΠ∆M

Try it Online!

Answer 21

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!

Answer 22

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!

Answer 23

MATLAB 39 bytes

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

Also check out answer by Jacob Watson

Answer 24

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.

Answer 25

CJam, 29 bytes

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

Try it online!

Answer 26

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")

Answer 27

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

Answer 28

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

Answer 29

Husk, 6 bytes

►=mΠṖ2

Try it online!

►= gives -1 over the other answer.

×* has too many duplicates and doesn't give the right value.

Answer 30

Julia 1.0, 99 83 bytes

~=length
!x=argmax(sum.(.==(1:max((M=[x[i]x[j] for i=1:~x for j=i+1:~x])...)),[M]))

Try it online!

-16 bytes (!!) thanks to MarcMush:

• Remove * (use implicit multiplication)
• Replace map with a broadcast
• Replace findmax with argmax
• Use the return value of a variable assignment
• Use sum instead of count