Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given 3 positive integers a, b, and n (whose maximum values are the maximum representable integer value in your language), output a truthy value if a ≡ b (mod n), and falsey otherwise. For those unfamiliar with congruency relations, a ≡ b (mod n) is true iff a mod n = b mod n (or, equivalently, (a - b) mod n = 0).

Restrictions

  • Built-in congruence testing methods are forbidden
  • Built-in modulo operations are forbidden (this includes operations such as Python's divmod function, which return both the quotient and the remainder, as well as divisibility functions, residue system functions, and the like)

Test Cases

(1, 2, 3) -> False
(2, 4, 2) -> True
(3, 9, 10) -> False
(25, 45, 20) -> True
(4, 5, 1) -> True
(83, 73, 59) -> False
(70, 79, 29) -> False
(16, 44, 86) -> False
(28, 78, 5) -> True
(73, 31, 14) -> True
(9, 9, 88) -> True
(20, 7, 82) -> False

This is , so shortest code (in bytes) wins, with earliest submission as a tiebreaker.

share|improve this question
    
How about divisibility functions? – Cᴏɴᴏʀ O'Bʀɪᴇɴ Feb 12 at 20:28
    
@CᴏɴᴏʀO'Bʀɪᴇɴ Those work by testing remainders, so they are also forbidden. I'll clarify. – Mego Feb 12 at 20:28
    
How about Python 2's integer floor division /? – xnor Feb 12 at 20:29
    
Floating point division? – El'endia Starman Feb 12 at 20:31
1  
Base conversion? – Dennis Feb 12 at 20:33

15 Answers 15

up vote 4 down vote accepted

Jelly, 5 bytes

_ÆD⁵e

Making heavy use of Anything else that is not forbidden is allowed.

Try it online!

How it works

_ÆD⁵e  Main link. Left input: a. Right input: b. Additional input: n

_      Subtract b from a.
 ÆD    Compute all divisors of the difference.
   ⁵e  Test if n is among the divisors.
share|improve this answer

Julia, 24 bytes

f(a,b,n,t=a-b)=t÷n==t/n

This is a function that accepts three integers and returns a boolean.

We simply test whether a - b integer divded by n is equal to a - b float divided by n. This will be true when there is no remainder from division, i.e. a - b | n, which implies that a - b (mod n) = 0.

share|improve this answer

Pyth, 7 bytes

!@UQ-FE

Uses Pyth's cyclic indexing.

  UQ         range(first line). [0,...,Q-1]
    -FE      Fold subtraction over the second line.
 @           Cyclic index UQ at -FE
!            Logical NOT
share|improve this answer

Python 2, 27 bytes

lambda a,b,n:(a-b)/n*n==a-b

Checks if a-b is a multiple of n by dividing by n, which automatically floors, and seeing if multiplying back by n gives the same result.

share|improve this answer

Haskell, 23 bytes

(a#b)n=div(a-b)n*n==a-b

Usage example: (28#78)5 -> True.

Same method as in @xnor's answer.

share|improve this answer

Minkolang 0.15, 14 11 bytes

nn-n$d:*=N.

Try it here! Input is expected as a b n.

Explanation:

n              Take number from input -> a
 n             Take number from input -> a, b
  -            Subtract               -> a-b
   n           Take number from input -> a-b, n
    $d         Duplicate stack        -> a-b, n, a-b, n
      :        Integer division       -> a-b, n, (a-b)//n
       *       Multiply               -> a-b, (a-b)//n*n
        =      1 if equal, 0 otherwise
         N.    Output as number and stop.
share|improve this answer

MATL, 9 bytes

Sdt:i*0hm

Input format is

[a b]
n

Try it online!

S     % implicitly input [a, b]. Sort this array
d     % compute difference. Gives abs(a-b)
t:    % duplicate and generate vector [1,2,...,abs(a-b)]; or [] if a==b
i*    % input n and multiply to obtain [n,2*n,...,abs(a-b)*n]; or []
0h    % concatenate element 0
m     % ismember function. Implicitly display
share|improve this answer

Retina, 20

^(1+) \1*(1*) \1*\2$

Input is given in unary, space-separated, in order n a b. Output 1 for truthy and 0 for falsey.

Try it online.


If you prefer decimal input then you can do this:

\d+
$&$*1
^(1+) \1*(1*) \1*\2$

Try it online.

share|improve this answer

APL, 15 bytes

{(⌊d)=d←⍺÷⍨-/⍵}

This is a dyadic function that accepts n on the left and a and b as an array on the right.

The approach here is basically the same as in my Julia answer. We test whether a - b / n is equal to the floor of itself, which will be true when a - b (mod n) = 0.

share|improve this answer

JavaScript (ES6), 27 bytes

@CᴏɴᴏʀO'Bʀɪᴇɴ posted a version which does not work; here is the "common algorithm" that people are using in a form which "works":

(a,b,n)=>n*(0|(a-b)/n)==a-b

The word "works" is in scare quotes because the shortcut we're using for Math.floor() implicitly truncates a number to be in the signed 32-bit range, so this cannot handle the full 52-bit-or-whatever space of integers that JavaScript can describe.

share|improve this answer
    
If this answer cannot handle all representable positive integers in the language, it is not valid. – Mego Feb 12 at 20:55
1  
@Mego: Given that some languages will be using 32-bit integers, I think that restriction is onerously arbitrary unless you further specify either the bit-width of the integers or else that the language must have bignums. – CR Drost Feb 12 at 20:59
1  
It's not at all arbitrary. The challenge clearly states that the inputs may be any 3 positive integers, up to the maximum representable integer value in the chosen language. If the submission might fail for a set of inputs in that range, it's not valid. Relevant meta post. – Mego Feb 12 at 21:02
    
@Mego: Let me ask you point-blank: Are you going to object to the Haskell solution on the same criterion? (The Haskell solution is polymorphic because it does not have a signature and is not written in a way which invokes the Dreaded Monomorphism Restriction. For normal signed types it works perfectly well across the whole range; however there exists a set of inputs that you can put in -- a test set is (2, 150, 3) :: (Word8, Word8, Word8); the criterion you specify is explicitly "if theoretically an input exists that makes the answer invalid, the answer should be deemed invalid.") – CR Drost Feb 12 at 21:18
1  
@Mego: If you're wondering why I'm making a big deal out of this, the JavaScript number type contains noncontinuous integers around the 2^52-ish fringes, so that it becomes very possible that (a - b) == a for certain values of a. An answer which has to be valid off in those borderlands is nearly impossible even if I take the byte penalty and replace (0|...) with Math.floor(...). – CR Drost Feb 12 at 21:25

CJam, 7 bytes

l~-\,=!

Input order is n a b.

Test it here.

Explanation

l~  e# Read input and evaluate to push n, a and b onto the stack.
-   e# Subtract b from a.
\,  e# Swap with n and turn into range [0 1 ... n-1].
=   e# Get (a-b)th element from that range, which uses cyclic indexing. This is
    e# equivalent to modulo, and as opposed to the built-in % it also works correctly
    e# for negative (a-b).
!   e# Negate, because a 0 result from the previous computation means they are congruent.
share|improve this answer

Python 3, 27 bytes

lambda a,b,n:pow(a-b,1,n)<1

pow(x,y,n) calculates (x**y)%n, so this is just (a-b)**1%n.

share|improve this answer

ES6, 28 bytes

(a,b,n)=>!/\./.test((a-b)/n)

Works by looking for a decimal point in (a-b)/n which I'm hoping is allowed.

share|improve this answer

Seriously, 10 bytes

,,,-A│\)/=

Takes input as N\nA\nB\n (capital letters used to distinguish from newlines).

Try it online

This uses the same method as @AlexA's answer

Explanation (capital letters used as variable names for explanatory purposes):

,,,-A│\)/=
,,,         push N, A, B
   -A       push C = abs(A-B)
     │      duplicate entire stack (result is [N, C, N, C])
      \)/=  1 if C//N == C/N (floored division equals float division)
share|improve this answer

F#, 24 bytes

fun a b n->(a-b)/n*n=a-b

Implements the same check as @xnor's answer.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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