20
\$\begingroup\$

You will be given two integers \$M\$ and \$N\$. Find the number of pairs \$(x,y)\$ such that \$1 \le x \le M\$, \$1 \le y \le N\$ and \$(x+y)\bmod5 = 0\$.

For example, if \$M = 6\$ and \$N = 12\$, pairs which satisfies such conditions are, \$(1,4), (4,1), (1,9), (2,3), (2,8), (3,2), (3,7), (3,12), (4,6), (6,4), (4,11), (5,5), (5,10), (6,9)\$

Total \$14\$.

Sample

Input : 6 12
Output: 14

Input : 11 14
Output: 31

Input : 553 29
Output: 3208

Input : 2 2
Output: 0

Input : 752486 871672
Output: 131184195318 

This is a code-golf challenge so code with lowest bytes wins!

Update

Jonathan Allan's solution has the smallest code size, 5 bytes. However, it doesn't produce an answer for the last given test.

I have decided to go with the next answer with the shortest size that produces the correct answer for the largest test, there is a tie between two golfers who competed neck-to-neck.

I proudly present the winners of this challenge Lyxal and Kevin Cruijssen with only 7 bytes code! Congratulations! 🎉

As many of you, I found Arnauld's answer most helpful in finding the correct solution. So, I am accepting Arnauld's answer.

Thank you, Golfers!

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Why are the pairs (4,5) and (5,4) listed in your example? \$\endgroup\$ May 27, 2020 at 19:57
  • \$\begingroup\$ Thanks, It should be \$(4,6), (6,4)\$. I have fixed it. :) \$\endgroup\$ May 27, 2020 at 20:11
  • 2
    \$\begingroup\$ I know many here will agree to select your answer as it is the most helpful for finding the solution. Both winners also found it useful, so this answer deserves to be at the one at the top of the list. Thank you for your nice explanation :) \$\endgroup\$ May 29, 2020 at 20:19
  • 1
    \$\begingroup\$ Ah, ok. I didn't notice the update you made to the post. \$\endgroup\$
    – Arnauld
    May 29, 2020 at 21:21

20 Answers 20

13
\$\begingroup\$

Python 2, 32 bytes

lambda m,n:(m*n+abs(m%5-~n%5))/5

Try it online!

Adapts an idea from Arnauld. We estimate that \$1/5\$ of the \$mn\$ pairs will satisfy the mod-5 condition. Th actual value may be one higher depending on the mod-5 values of \$m\$ and \$n\$, and we bump up \$mn\$ a bit so that these make it pass the next multiple of 5.


34 bytes

lambda m,n:m*n/5+(0<-m%5*(-n%5)<5)

Try it online!

34 bytes

lambda m,n:m*n/5+(m*n%5+m%5+n%5)/9

Try it online!

36 bytes

lambda m,n:m*n/5+((5-m%5)*(5-n%5)<5)

Try it online!

36 bytes

lambda m,n:m*n/5+(abs(m%5+n%5*1j)>4)

Try it online!

36 bytes

lambda m,n:m*n/5+(m%5*5/4+n%5*5/4>5)

Try it online!

36 bytes

lambda m,n:m*n/5+(m%5+n%5+m*n%5/4>5)

Try it online!

\$\endgroup\$
8
  • 2
    \$\begingroup\$ 34 bytes with a shorter residual correction condition. \$\endgroup\$ May 27, 2020 at 18:26
  • \$\begingroup\$ @SurculoseSputum Just posted that a moment before :) \$\endgroup\$
    – xnor
    May 27, 2020 at 18:28
  • \$\begingroup\$ What is 1j in the 3rd code sample? \$\endgroup\$ May 28, 2020 at 3:57
  • \$\begingroup\$ @CodyGray It's the complex unit \$i\$. \$\endgroup\$
    – xnor
    May 28, 2020 at 8:10
  • \$\begingroup\$ It is lesser known, but python supports native complex units :-) \$\endgroup\$
    – mazunki
    May 30, 2020 at 19:55
11
\$\begingroup\$

JavaScript (ES6), 29 bytes

Takes input as (m)(n).

m=>g=n=>n&&(m+n%5)/5+g(n-1)|0

Try it online!

How?

Let's consider a grid of width \$m\$ with 1-indexed coordinates and an X mark on each cell for which:

$$(x+y)\equiv 0\pmod 5$$

Here are the first few rows for \$m=9\$:

   | 1 2 3 4 5 6 7 8 9
---+-------------------
 1 | - - - X - - - - X
 2 | - - X - - - - X -
 3 | - X - - - - X - -
 4 | X - - - - X - - -
 5 | - - - - X - - - -
 6 | - - - X - - - - X
 7 | - - X - - - - X -

Computing \$m+(y\bmod5)\$ is equivalent to left-padding each row in such a way that all X marks are vertically aligned and appear on columns whose index is a multiple of \$5\$.

With such a configuration, the number of marks is directly given by \$\lfloor{L_y/5}\rfloor\$, where \$L_y\$ is the updated length of the \$y\$-th row.

 y | y%5 |         padded row         | length | // 5
---+-----+----------------------------+--------+------
 1 |  1  |  + - - - X - - - - X       |   10   |   2
 2 |  2  |  + + - - X - - - - X -     |   11   |   2
 3 |  3  |  + + + - X - - - - X - -   |   12   |   2
 4 |  4  |  + + + + X - - - - X - - - |   13   |   2
 5 |  0  |  - - - - X - - - -         |    9   |   1
 6 |  1  |  + - - - X - - - - X       |   10   |   2
 7 |  2  |  + + - - X - - - - X -     |   11   |   2
---+-----+----------^---------^-------+--------+------
         |  0 0 0 0 0 0 0 0 0 1 1 1 1 |
         |  1 2 3 4 5 6 7 8 9 0 1 2 3 |

We use this method to recursively compute the number of marks on each row.

\$\endgroup\$
6
\$\begingroup\$

Jelly, 5 bytes

p§5ḍS

Try it online!

How?

p§5ḍS - Link: positive integer, M; positive integer N
p     - (implicit [1..M]) Cartesian product (implicit [1..N])
 §    - sums
  5ḍ  - five divides? (vectorises)
    S - sum
\$\endgroup\$
6
\$\begingroup\$

J, 20 bytes

1#.[+/\0=5|1}.1+i.@+

Try it online!

The standard O(m*n) cartesian product solution saves 3 bytes [:+/@,0=5|2++/&i., but I figured I'd try a different approach:

A solution using a sliding window.

I think J is able to optimize this approach automatically into O(m+n)... in any case, I get an out of memory error on the final test case on TIO with the cartesian product approach but not with this one

Let's take 6 f 12 as an example:

  1. Generate the numbers 1 through 18 1+i.@+:

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
    
  2. Kill the first 1 1}.:

    2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
    
  3. Turn it into a 0-1 list indicating which numbers are divisible by 5 0=5|

    0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0
    
  4. Create a sliding window of length of the left arg (either arg would work though), summing each piece of the window [+/\:

           1
      /`````````\ etc...
    0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0
    \_________/
          1
    
    Final result: 1 1 1 2 1 1 1 1 2 1 1 1
    
  5. Sum of all those numbers 1#.:

    14
    
\$\endgroup\$
5
\$\begingroup\$

Python 3, 50 bytes

lambda n,m:sum((i//n+i%n)%5==3for i in range(n*m))

Try it online!

\$\endgroup\$
5
\$\begingroup\$

APL (Dyalog Unicode), 11 bytes

Full program.

≢⍸0=5|+/¨⍳⎕

Try it online! (largest test case would work with 3TB RAM)

Reads quite literally as the problem specification:

count where 0= 0 equals 5| the mod-5 of +/ the sum of ¨ each of all indices until the input.

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

MATL, 9 bytes

:i:!+5\~z

Try it online!

How it works

:    % Implicit input: M. Range [1 2 ... M]
i:   % Input: N. Range [1 2 ... N]
!    % Transpose
+    % Add, element-wise with broadcast. Gives an N×M matrix
5    % Push 5
\    % Modulus, element-wise
~    % Negate
z    % Number of nonzeros. Implicit display
\$\endgroup\$
4
\$\begingroup\$

Pyth, 12 11 bytes

-1 thanks to @Mukundan

lf!%sT5*FSM

Try it online!

lf!%sT5*FSM
         SM    Map 1-indexed range to each input
       *F      Cartesian product of the two ranges
 f              Filter by:
    sT          - sum of elements..
  !%  5         - .. is divisible by 5
l               Take the length
\$\endgroup\$
2
  • \$\begingroup\$ -1 byte by replacing +F with s. Try it online! \$\endgroup\$ May 27, 2020 at 17:22
  • \$\begingroup\$ @Mukundan Good point, thanks \$\endgroup\$ May 27, 2020 at 17:27
4
\$\begingroup\$

R, 40 bytes

function(m,n)sum(!(rep(1:m,e=n)+1:n)%%5)

Try it online!

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Also 40 bytes \$\endgroup\$
    – Giuseppe
    May 27, 2020 at 19:59
  • 1
    \$\begingroup\$ Ha ha! Yes! I tried it, too! All the possibly-useful built-in R functions seem to have too-many characters to be useful... (outer=40chars, mapply=41chars, matrix=42chars...). What a frustrating golfing language! \$\endgroup\$ May 27, 2020 at 20:16
  • 2
    \$\begingroup\$ 39 bytes with a warning. \$\endgroup\$
    – Giuseppe
    May 27, 2020 at 21:06
  • \$\begingroup\$ That's better than mine! You need to post it! \$\endgroup\$ May 28, 2020 at 7:24
4
\$\begingroup\$

MathGolf, 7 bytes

╒5%+5/Σ

Port of @Arnauld's JavaScript answer, so make sure to upvote him!

Try it online.

Explanation:

╒        # Push a list in the range [1, (implicit) first input]
 5%      # Modulo-5 on each value in the list
   +     # Add the second (implicit) input to each
    5/   # Integer-divide each value by 5
      Σ  # And sum the list
         # (after which the entire stack joined together is output implicitly as result)
\$\endgroup\$
4
\$\begingroup\$

Python 2, 36 bytes

f=lambda m,n:m and(m%5+n)/5+f(m-1,n)

Try it online!

Use @Arnauld's formula, be sure to checkout and upvote his answer!


Original solution, using a longer formula:

Python 2, 42 41 bytes

-1 byte thanks to @xnor!

f=lambda m,n:m and(n%5>~m%5)+n/5+f(m-1,n)

Try it online!

For each number i between 1 to m, there are (n%5+i%5>4)+n/5 numbers between 1 to n that can be paired with i.

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

05AB1E, 9 8 7 bytes

L5%+5÷O

Try it online!

A 100% port of @Arnauld's Javascript answer

\$\endgroup\$
1
  • \$\begingroup\$ -1 byte by porting Arnauld's JavaScript answer: L5%+5÷O. \$\endgroup\$ May 28, 2020 at 14:16
3
\$\begingroup\$

K (ngn/k), 15 bytes

+//~5!+/:/1+!:'

Try it online!

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

Wolfram Language (Mathematica), 56 bytes

Length@Solve[1<=x<=#&&1<=y<=#2&&Mod[x+y,5]==0,Integers]&

Try it online!

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

perl -M5.010 -al, 49 bytes

for(1..$_){for$y(1..$F[1]){($_+$y)%5||$c++}}say$c

Try it online!

This is a pretty stupid, "iterate over all pairs, count the ones where sum mod 5 equals zero", solution. There's a nicer formula, but I couldn't (yet) reduce that down enough. It will take a very long time to calculate the answer to (752486, 871672), but there was no time limit stated.

The TIO link has a $c = 0; in the header. This isn't needed for a single line solution; it's only there to make it work with multiple inputs (and as such, TIO won't count those bytes).

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Same logic, 41 bytes \$\endgroup\$
    – Xcali
    May 28, 2020 at 18:17
2
\$\begingroup\$

Japt, 11 10 bytes

õ ï+Võ)èv5

Try it

õ ï+Võ)èv5     :Implicit input of integers U & V
õ              :Range [1,U]
  ï            :Cartesian product with
    Võ         :  Range [1,V]
   +           :  Reduce each pair by addition
      )        :End Cartesian product
       è       :Count the elements
        v5     :  Divisible by 5
\$\endgroup\$
2
\$\begingroup\$

C (gcc), 36 bytes

f(n,m){n=m*n/5+((5-m%5)*(5-n%5)<5);}

Try it online!

A port of one of xnor's formulas.

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

Erlang (escript), 69 bytes

Posting before I run out of time.

f(X,Y)->[[A,B]||A<-lists:seq(1,X),B<-lists:seq(1,Y),((A+B)rem 5)==0].

Try it online!

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

Charcoal, 16 12 bytes

IΣ÷⁺﹪…·¹N⁵N⁵

Try it online! Link is to verbose version of code. Port of @KevinCruijssen's answer, although that's apparently a port of @Arnauld's answer. Explanation:

     …·        Inclusive range from
       ¹        Literal `1` to
        N       First input number
    ﹪           Vectorised Modulo
         ⁵      Literal `5`
   ⁺            Vectorised Plus
          N     Second input number
  ÷             Vectorised Integer divide by
           ⁵    Literal `5`
 Σ              Take the sum
I               Cast to string
                Implicitly print

Previous 16-byte brute force answer:

NθI№⭆N⭆θ﹪⁺²⁺ιλ⁵0

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

Nθ

Input M.

⭆N⭆θ

Input N and loop over N and M, casting the result to a string.

﹪⁺²⁺ιλ⁵

Take the sum modulo 5, adjusted for 1-indexing (sigh).

I№...0

Count the 0s in the result.

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

Vyxal s, 6 bytes

ɾ5%+5ḭ

Try it Online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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