15
\$\begingroup\$

The task is simple, divide, get the quotient and the remainder, and if the remainder isn't 1 or 0, do the same thing (quotient divmod remainder) until the remainder is 1 or 0, then get the remainder. If the last input number is 1 or 0, output it.

If the input is [15, 4], then the output would be 0, because the divmod of 15 and 4 is [3, 3] which if you do it again, you get [1, 0], and you can't divmod further, then get the last element, and you got 0.

Another example would be [102, 7], which if you divmod, you get [14, 4], which if you do again, you get [3, 2], which if you divmod again, you get [1, 1], and you get the last element 1, which is the output.

Both input numbers are assumed to be non-negative integers less than 1000.

This is , so the shortest program/function in bytes wins.

Testcases:

[15, 4] => 0
[102, 7] => 1
[20, 2] => 0
[10, 0] => 0
[11, 1] => 1
[99, 7] => 1
[45, 45] => 0
[31, 30] => 1
[999, 7] => 0
[999, 6] => 1
[88, 7] => 0
[1, 999] => 1
[98, 7] => 0
[999, 998] => 1
\$\endgroup\$
6
  • \$\begingroup\$ Is it permissible to output two unique outputs for 1 and 0 other than 1 and 0? \$\endgroup\$ Jan 14 at 8:35
  • 3
    \$\begingroup\$ It would also be worth clarifying the spec. As currently written, I would say that [10, 0] is an invalid input because the spec suggests there is always at least one divmod. You’ve also not specified that the input have to be integers or non-negative, but the examples would suggest that is the case. \$\endgroup\$ Jan 14 at 11:17
  • \$\begingroup\$ "and if the remainder is 1 or 0, do the same thing" - is that supposed to say "if the remainder isn't 1 or 0"? \$\endgroup\$ Jan 14 at 12:51
  • \$\begingroup\$ @user2357112 Fixed \$\endgroup\$
    – Fmbalbuena
    Jan 14 at 12:54
  • \$\begingroup\$ So this is the gcd algorithm, but implemented by a student who sucks at arithmetic! \$\endgroup\$
    – Stef
    Jan 14 at 13:17

21 Answers 21

5
\$\begingroup\$

Nekomata, 4 bytes

ʷ{Ƶþ
ʷ{Ƶþ
ʷ{      While; run the following code until it fails
  Ƶ       Check if the absolute value of the top of the stack is greater than 1
   þ      Divmod

Both Ƶ and þ are new built-ins in Nekomata 0.5.1, which is not yet on ATO.

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

JavaScript (ES6), 27 bytes

f=(p,q)=>q>1?f(p/q|0,p%q):q

Try it online!

Or 25 bytes with BigInts.

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

Python 2, 35 bytes

f=lambda a,b:f(a/b,a%b)if b>1else b

Try it online!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ -1: f=lambda a,b:1-(b>1>f(a/b,a%b))**b \$\endgroup\$ Jan 14 at 5:54
  • \$\begingroup\$ @Albert.Lang Uh. I learned something today. \$\endgroup\$
    – Stef
    Jan 14 at 12:50
3
\$\begingroup\$

R, 33 bytes

f=\(x,y)`if`(y>1,f(x%/%y,x%%y),y)

Attempt This Online!

A recursive function taking two arguments and returning 1 or 0.

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

C (gcc), 27 bytes

f(a,b){a=b>1?f(a/b,a%b):b;}

Try it online!

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

x86-32 machine code, 9 bytes

x86-64 machine code, 10 bytes, same asm source

Args in EAX (dividend), ECX (divisor), return value in ECX (0 or 1 final remainder).

To call from C, gcc -mregparm=3 will put args in EAX, EDX, ECX in that order (so a dummy second arg works), but won't look for retval in ECX. Returning in EAX costs 1 extra byte for xchg eax,ecx at the end.

Args must be signed non-negative. (At least the dividend must be; the divisor can be full-range 32-bit unsigned. And the first remainder must also be non-negative). Divisor must be non-zero or the first iteration will fault.

               divmod_repeat:
               .loop:
 99               cdq        ; zero-extend (for numbers that fit as non-negative integers)
 F7F1             div ecx        ; EAX = EDX:EAX/ecx unsigned; EDX = remainder
                
 89D1             mov ecx, edx
 4A               dec edx        ; 1 byte instruction in 32-bit mode
 7FF8             jg .loop       ; }while(remainder-- > 1);   or  }while(--rem > 0)
 C3               ret            

               ;   cmp ecx, 2     ; simple but less golfed version
               ;   jae .loop      ; }while(new_divisor >= 2);

This shows a hexdump of the 32-bit machine code on the left, from a NASM listing. The x86-64 version (still using 32-bit operand-size) uses FFCA dec edx.

Not much scope for golfing, other than choosing a good calling convention. div only works with EDX:EAX / src, producing its outputs in EDX (remainder) and EAX (quotient). We don't want to touch quotient, so all the special-case accumulator short-form encodings of instructions like xchg eax, reg and cmp al, imm8.

But we can destroy the old copy of the remainder in EDX after copying it to ECX as the new divisor (or return value). So we can use 1-byte (in 32-bit mode) dec reg to set FLAGS instead of cmp. The next iteration's cdq will overwrite EDX anyway, and we need cdq anyway.

We can only use signed conditions with dec because it leaves CF unmodified, but is otherwise like sub or cmp ecx, 1.

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

Retina 0.8.2, 35 bytes

.+
$*
+`(..+)¶(\1)*(.*)
$3¶$#2$*
^.

Try it online! Takes the integers in reverse order on separate lines but link is to test suite that takes input in the format given in the question. Explanation:

.+
$*

Convert to unary.

(..+)¶(\1)*(.*)
$3¶$#2$*

If the denominator is at least 2, divmod the numerator by the denominator, replacing the denominator by the remainder and the numerator by the quotient.

+`

Repeat until the denominator is reduced to less than 2.

^.

Convert the denominator to 0 or 1.

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

Uiua SBCS, 13 bytes

⊙◌⍢(:⌊⊃÷◿|>1)

Try it!

⊙◌⍢(:⌊⊃÷◿|>1)
  ⍢(     |  )  # while
          >1   # top of stack is greater than one
      ⊃÷◿      # quotient and remainder
     ⌊         # take the floor of the quotient
    :          # swap so remainder is on top
⊙◌             # drop the quotient from the stack
\$\endgroup\$
2
  • \$\begingroup\$ That version of the SBCS does not have the glyph added today. Here's my updated version: tinyurl.com/Uiua-SBCS-Jan-14 \$\endgroup\$
    – Tbw
    Jan 14 at 12:25
  • \$\begingroup\$ @Tbw Thanks, updated. \$\endgroup\$
    – chunes
    Jan 14 at 12:49
2
\$\begingroup\$

05AB1E, 6 bytes

[`D!#‰

Try it online or verify all test cases.

Explanation:

[       # Start an infinite loop:
 `      #  Pop and push both values in the pair separately to the stack
        #  (which will use the implicit input-pair in the first iteration)
  D     #  Duplicate the top value (the remainder)
   !    #  Take its factorial (0 becomes 1; 1 remains 1; ≥2 becomes larger)
    #   #  If it's truthy (==1), stop the infinite loop
        #  (after which the duplicated remainder is output implicitly as result)
     ‰  #  (else) Divmod the two values
\$\endgroup\$
2
\$\begingroup\$

Funge-98, 51 bytes

v   >.@   @.<
>    "HTRF"4 (&& v
\/RRw1`1:%OOw1`1:<

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Welcome to Code Golf, nice first answer! \$\endgroup\$
    – noodle man
    Jan 17 at 2:58
2
\$\begingroup\$

Scratch, 77 70 bytes

Ports @enzo's answer. Run without screen refresh.

define(x)(y
if<(y)>(1)>then
([floor v]of((x)/(y)))((x)mod(y
else
say(y

enter image description here

\$\endgroup\$
1
  • \$\begingroup\$ set[i v]to(y => say(y, with "run without screen refresh" checked on \$\endgroup\$
    – noodle man
    Jan 17 at 3:00
1
\$\begingroup\$

Go, 47 bytes

func(a,b int)int{for b>1{a,b=a/b,a%b}
return b}

Attempt This Online!

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

Google Sheets, 74 bytes

=LET(F,LAMBDA(F,d,m,LET(x,MOD(d,m),IF(x<2,x,F(F,INT(d/m),x)))),F(F,A1,A2))

Simple recursive function that stops the execution when the remainder is 0 or 1.

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

Pyth, 10 bytes

eu?>eG1.DF

Attempt This Online!

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

Jelly, 8 bytes

d/ỊṪ¬Ɗ¿Ṫ

Try it online!

A monadic link taking a pair of non-negative integers and returning 1 or 0.

Explanation

     Ɗ¿  | While the following is true:
  Ị      | - <= 1
   Ṫ     | - Tail (i.e. second list member)
    ¬    | - Not
d/       | … Reduce using divmod
       Ṫ | Tail
 

If we were allowed to guarantee the second input were non-zero, this is shorter:

Jelly, 7 bytes

d/%/¿ṪỊ

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ Can you please explain it? I like this language. \$\endgroup\$
    – Fmbalbuena
    Jan 15 at 16:40
  • \$\begingroup\$ @Fmbalbuena thanks, hope that makes sense! \$\endgroup\$ Jan 16 at 23:33
1
\$\begingroup\$

TI-BASIC, 37 bytes

While 1<Ans(2
Ans→L
Ans(1)/Ans(2
int({Ans,ʟL(2)fPart(Ans
End
Ans(2

Takes input in Ans. Replace the second to fourth lines with int({Ans(1)/Ans(2),remainder(Ans(1),Ans(2 for -2 bytes if remainder( is supported.

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

Charcoal, 23 bytes

NθNηW∧⊖ηη«≔﹪θιη≔÷θιθ»Iη

Try it online! Link is to verbose version of code. Explanation: Lack of divmod and recursion makes this annoyingly long.

NθNη

Input the two values.

W∧⊖ηη«

Compare the second value against both 1 and 0, but in such a way that if it is neither than the implicit loop variable has the same value.

≔﹪θιη≔÷θιθ

Modulo and divide the first value by the copy of the second, thus allowing the second and first values to be safely overwritten.

»Iη

Output the final value.

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

Perl 5 -Minteger -ap, 37 bytes

@F=("@F"/$_,"@F"%$_)while($_=$F[1])>1

Try it online!

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

APL(Dyalog Unicode), 18 bytes SBCS

{1<⍵:(⌊⍺÷⍵)∇⍵|⍺⋄⍵}

Try it on APLgolf!

A dfn that takes the first number as the left argument and the second number as the right argument.

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

TypeScript's type system, 97 bytes

//@ts-ignore
type M<A,B,T=[]>=A extends[...B,...infer I]?M<I,B,[...T,1]>:A extends[1]|[]?A:M<T,A>

Try it at the TypeScript playground!

I/O is unary numbers / tuples of 1s.

Modified from my solution to Division and remainder.

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

T-SQL 77 bytes

declare @x int = 88, @y int = 7, @z int
while @y > 1 BEGIN
select @z = @x/@y, @y = @x-(@z*@y)
set @x = @z
end
select @y

Try it!

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