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)\mod5 = 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\$
  • 1
    \$\begingroup\$ Why are the pairs (4,5) and (5,4) listed in your example? \$\endgroup\$ – Dominic van Essen May 27 at 19:57
  • \$\begingroup\$ Thanks, It should be \$(4,6), (6,4)\$. I have fixed it. :) \$\endgroup\$ – Jubayer Abdullah Joy May 27 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\$ – Jubayer Abdullah Joy May 29 at 20:19
  • 1
    \$\begingroup\$ Ah, ok. I didn't notice the update you made to the post. \$\endgroup\$ – Arnauld May 29 at 21:21

19 Answers 19

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.

| improve this answer | |
\$\endgroup\$
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!

| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ 34 bytes with a shorter residual correction condition. \$\endgroup\$ – Surculose Sputum May 27 at 18:26
  • \$\begingroup\$ @SurculoseSputum Just posted that a moment before :) \$\endgroup\$ – xnor May 27 at 18:28
  • \$\begingroup\$ What is 1j in the 3rd code sample? \$\endgroup\$ – Cody Gray May 28 at 3:57
  • \$\begingroup\$ @CodyGray It's the complex unit \$i\$. \$\endgroup\$ – xnor May 28 at 8:10
  • \$\begingroup\$ It is lesser known, but python supports native complex units :-) \$\endgroup\$ – mazunki May 30 at 19:55
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
| improve this answer | |
\$\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
    
| improve this answer | |
\$\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!

| improve this answer | |
\$\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.

| improve this answer | |
\$\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
| improve this answer | |
\$\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
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ -1 byte by replacing +F with s. Try it online! \$\endgroup\$ – Mukundan314 May 27 at 17:22
  • \$\begingroup\$ @Mukundan Good point, thanks \$\endgroup\$ – math junkie May 27 at 17:27
4
\$\begingroup\$

R, 40 bytes

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

Try it online!

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Also 40 bytes \$\endgroup\$ – Giuseppe May 27 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\$ – Dominic van Essen May 27 at 20:16
  • 2
    \$\begingroup\$ 39 bytes with a warning. \$\endgroup\$ – Giuseppe May 27 at 21:06
  • \$\begingroup\$ That's better than mine! You need to post it! \$\endgroup\$ – Dominic van Essen May 28 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)
| improve this answer | |
\$\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.

| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

05AB1E, 9 8 7 bytes

L5%+5÷O

Try it online!

A 100% port of @Arnauld's Javascript answer

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ -1 byte by porting Arnauld's JavaScript answer: L5%+5÷O. \$\endgroup\$ – Kevin Cruijssen May 28 at 14:16
3
\$\begingroup\$

K (ngn/k), 15 bytes

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

Try it online!

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 56 bytes

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

Try it online!

| improve this answer | |
\$\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).

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Same logic, 41 bytes \$\endgroup\$ – Xcali May 28 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
| improve this answer | |
\$\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.

| improve this answer | |
\$\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!

| improve this answer | |
\$\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.

| improve this answer | |
\$\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.