28
\$\begingroup\$

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]
\$\endgroup\$
  • \$\begingroup\$ Sandbox (deleted) \$\endgroup\$ – Jo King Aug 6 '18 at 10:39
  • 5
    \$\begingroup\$ Suggested 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. \$\endgroup\$ – Kevin Cruijssen Aug 6 '18 at 12:07
  • \$\begingroup\$ @Kevin Good suggestion, added \$\endgroup\$ – Jo King Aug 6 '18 at 12:38

29 Answers 29

11
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Holloway Aug 7 '18 at 12:02
  • 2
    \$\begingroup\$ @Holloway Brachylog uses a custom code page \$\endgroup\$ – Fatalize Aug 7 '18 at 12:07
11
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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! \$\endgroup\$ – CriminallyVulgar Aug 6 '18 at 12:59
  • 1
    \$\begingroup\$ combn(scan(),2,prod) works instead of using apply \$\endgroup\$ – Giuseppe Aug 6 '18 at 13:24
8
\$\begingroup\$

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Æṃ
\$\endgroup\$
7
\$\begingroup\$

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

\$\endgroup\$
7
\$\begingroup\$

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
\$\endgroup\$
6
\$\begingroup\$

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]
\$\endgroup\$
  • 1
    \$\begingroup\$ æ2ùP.M for 6 bytes \$\endgroup\$ – Kaldo Aug 6 '18 at 12:22
  • \$\begingroup\$ @Kaldo Thanks! Completely forgot about ù. \$\endgroup\$ – Kevin Cruijssen Aug 6 '18 at 12:30
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Actually it looks like both of us misread the question. This fails for input {3, 3, 3}. Fixed: Commonest[1##&@@@#~Subsets~{2}]& \$\endgroup\$ – JungHwan Min Aug 6 '18 at 20:21
  • \$\begingroup\$ @JungHwanMin Huh. I thought that Subsets didn't count repeats as separate elements. It seems like it does, though, so thanks! \$\endgroup\$ – LegionMammal978 Aug 7 '18 at 1:28
5
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ i am not sure you need to do I'*I*1-eye Why not just I'*I-eye? \$\endgroup\$ – aaaaaa Aug 8 '18 at 0:45
5
\$\begingroup\$

Perl 6, 41 38 bytes

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

Try it online!

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Ramillies Aug 6 '18 at 22:08
  • 1
    \$\begingroup\$ @Ramillies That's the infix : operator. \$\endgroup\$ – nwellnhof Aug 6 '18 at 23:18
  • \$\begingroup\$ Ah, I see. Thank you. \$\endgroup\$ – Ramillies Aug 6 '18 at 23:22
4
\$\begingroup\$

Stax, 12 10 bytes

╢êv^⌐ö►♣Ä»

Run and debug it

\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Is the UpperTriangle part required? Can you just flatten the table and sort? \$\endgroup\$ – svavil Aug 7 '18 at 12:14
  • \$\begingroup\$ @svavil Yes, it is required; [5, 2, 9, 10, 3, 4, 4, 4, 7] -> 16 instead of 20 without it. \$\endgroup\$ – Conor O'Brien Aug 7 '18 at 18:41
4
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ @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\$. \$\endgroup\$ – Arnauld Nov 19 '18 at 8:40
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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]
\$\endgroup\$
3
\$\begingroup\$

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.
\$\endgroup\$
  • 1
    \$\begingroup\$ This is only 27. \$\endgroup\$ – Adám Aug 7 '18 at 15:18
3
\$\begingroup\$

Japt, 20 16 bytes

  • -4 bytes from @Shaggy

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

Try it online!

\$\endgroup\$
  • \$\begingroup\$ 16 bytes \$\endgroup\$ – Shaggy Sep 4 '18 at 9:09
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
2
\$\begingroup\$

MATLAB 39 bytes

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

Also check out answer by Jacob Watson

\$\endgroup\$
  • 1
    \$\begingroup\$ Having the second line be b=triu(a'*a,1); saves 4 bytes. \$\endgroup\$ – sundar Aug 8 '18 at 12:32
  • \$\begingroup\$ @sundar Oh snap, you are right :) I had triu intially but drifted away somehow \$\endgroup\$ – aaaaaa Aug 8 '18 at 14:47
  • \$\begingroup\$ Good solution, I didn't realise the upper triangle function was so short! \$\endgroup\$ – Jacob Watson Aug 10 '18 at 8:19
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

CJam, 29 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

Japt -h, 11 bytes

à2 ®×Ãü ñÊÌ

Try it

á2 ®×
ñ@è¥X

Try it

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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