#37298•Extreme

Integer Divide

Build integer division in the type system: quotient and remainder for both signs, up to MAX_SAFE_INTEGER, by long division over digit tuples.

Long division is the one piece of school arithmetic that never collapses into a one-liner.

Divide<Dividend, Divisor> takes two integers and returns a tuple of [quotient, remainder], with never when the divisor is 0. Both operands may be negative, and both may be as large as Number.MAX_SAFE_INTEGER, which rules out every technique that counts: a tuple of nine quadrillion elements is not something TypeScript will build for you. The arithmetic has to happen one decimal digit at a time, the way it does on paper. Division truncates toward zero, so the quotient carries the combined sign of the two operands while the remainder keeps the sign of the dividend.

type T0 = Divide<15, 6> // [2, 3]
type T1 = Divide<1234567890, 54321> // [22727, 14523]
type T2 = Divide<-9007199254740991, 77786731> // [-115793518, -18531333]
type T3 = Divide<-999, 0> // never

Challenge Instructions: Integer Divide

Extreme

Implement the division algorithm for integers (including negative integers). The type utility should accept two integers as parameters and return a tuple with two elements: the quotient as the first, and the remainder as the second. If the divisor is 0, return never.

View on GitHub: https://tsch.js.org/37298

Change the following code to make the test cases pass (no type check errors).

ChallengeSolution
/* _____________ Your Code Here _____________ */

type Divide<Dividend extends number, Divisor extends number> = any

/* _____________ Test Cases _____________ */
import type { Equal, Expect } from '../helpers'

type cases = [
  Expect<Equal<Divide<15, 6>, [2, 3]>>,
  Expect<Equal<Divide<18864543, 67843>, [278, 4189]>>,
  Expect<Equal<Divide<1234567890, 54321>, [22727, 14523]>>,
  Expect<Equal<Divide<1234567890123499, 3>, [411522630041166, 1]>>,
  // Number.MAX_SAFE_INTEGER = 9007199254740991
  Expect<Equal<Divide<9007199254740991, 200346>, [44958218555, 120961]>>,
  Expect<Equal<Divide<-90071

Pro Challenge

Get access to all 200+ challenges, including every medium, hard, and extreme one.

One-time payment, lifetime access. 30-day money-back guarantee.

Detailed Explanation

The solution in full. The first third is decimal arithmetic on digit tuples, the middle is the division loop, and the last few types handle signs and the conversion back to number:

type Digit = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
 
// A magnitude is a tuple of digits, least significant first, with no leading
// zeros. Zero is the empty tuple.
type Num = Digit[]
 
// Digit -> tuple of that length, so single-digit arithmetic becomes tuple
// arithmetic, and back again.
type Ones = {
  '0': []
  '1': [1]
  '2': [1, 1]
  '3': [1, 1, 1]
  '4': [1, 1, 1, 1]
  '5': [1, 1, 1, 1, 1]
  '6': [1, 1, 1, 1, 1, 1]
  '7': [1, 1, 1, 1, 1, 1, 1]
  '8': [1, 1, 1, 1, 1, 1, 1, 1]
  '9': [1, 1, 1, 1, 1, 1, 1, 1, 1]
}
type Flag = { 0: []; 1: [1] }
type Ten = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
type Char = { 0: '0'; 1: '1'; 2: '2'; 3: '3'; 4: '4'; 5: '5'; 6: '6'; 7: '7'; 8: '8'; 9: '9' }
 
type DigitOf<T extends unknown[]> = T['length'] extends infer L extends keyof Char ? Char[L] : never
 
// A + B + carry in, as [digit written down, carry out].
type AddStep<A extends Digit, B extends Digit, C extends 0 | 1> =
  [...Ones[A], ...Ones[B], ...Flag[C]] extends [...Ten, ...infer Rest]
    ? [DigitOf<Rest>, 1]
    : [DigitOf<[...Ones[A], ...Ones[B], ...Flag[C]]>, 0]
 
// A - B - borrow in, offset by ten so no tuple ever has to go negative.
type SubStep<A extends Digit, B extends Digit, Bo extends 0 | 1> =
  [...Ten, ...Ones[A]] extends [...Ones[B], ...Flag[Bo], ...infer Rest]
    ? Rest extends [...Ten, ...infer Short]
      ? [DigitOf<Short>, 0]
      : [DigitOf<Rest>, 1]
    : never
 
// Leading zeros sit at the end of a little-endian tuple.
type Trim<T extends Num> = T extends [...infer Rest extends Num, '0'] ? Trim<Rest> : T
 
type Add<A extends Num, B extends Num, C extends 0 | 1 = 0, Acc extends Num = []> =
  A extends [infer AH extends Digit, ...infer AR extends Num]
    ? B extends [infer BH extends Digit, ...infer BR extends Num]
      ? AddStep<AH, BH, C> extends [infer D extends Digit, infer NC extends 0 | 1]
        ? Add<AR, BR, NC, [...Acc, D]>
        : never
      : Add<A, ['0'], C, Acc>
    : B extends [Digit, ...Num]
      ? Add<['0'], B, C, Acc>
      : C extends 1
        ? [...Acc, '1']
        : Acc
 
// Only ever called with A >= B, so the final borrow is always 0.
type Sub<A extends Num, B extends Num, Bo extends 0 | 1 = 0, Acc extends Num = []> =
  A extends [infer AH extends Digit, ...infer AR extends Num]
    ? B extends [infer BH extends Digit, ...infer BR extends Num]
      ? SubStep<AH, BH, Bo> extends [infer D extends Digit, infer NB extends 0 | 1]
        ? Sub<AR, BR, NB, [...Acc, D]>
        : never
      : Sub<A, ['0'], Bo, Acc>
    : Trim<Acc>
 
type Ordering = 'lt' | 'eq' | 'gt'
 
type CmpLen<A extends unknown[], B extends unknown[]> =
  A extends [unknown, ...infer AR]
    ? B extends [unknown, ...infer BR]
      ? CmpLen<AR, BR>
      : 'gt'
    : B extends [unknown, ...unknown[]]
      ? 'lt'
      : 'eq'
 
// Equal digit counts, so walk from the most significant end: the tuple's tail.
type CmpTop<A extends Num, B extends Num> =
  A extends [...infer AR extends Num, infer AH extends Digit]
    ? B extends [...infer BR extends Num, infer BH extends Digit]
      ? CmpLen<Ones[AH], Ones[BH]> extends infer O extends Ordering
        ? O extends 'eq'
          ? CmpTop<AR, BR>
          : O
        : never
      : 'gt'
    : 'eq'
 
type Cmp<A extends Num, B extends Num> =
  CmpLen<A, B> extends infer O extends Ordering ? (O extends 'eq' ? CmpTop<A, B> : O) : never
 
// [['9', 9 * D], ['8', 8 * D], ..., ['0', 0]], built once per division.
type Multiples<
  D extends Num,
  Acc extends [Digit, Num][] = [['0', []]],
  Cur extends Num = [],
  Left extends Digit[] = ['1', '2', '3', '4', '5', '6', '7', '8', '9'],
> = Left extends [infer H extends Digit, ...infer Rest extends Digit[]]
  ? Add<Cur, D> extends infer Next extends Num
    ? Multiples<D, [[H, Next], ...Acc], Next, Rest>
    : never
  : Acc
 
// The largest multiple of the divisor that still fits into R, and the rest of R.
type TakeOut<R extends Num, T extends [Digit, Num][]> =
  T extends [[infer D extends Digit, infer M extends Num], ...infer Rest extends [Digit, Num][]]
    ? Cmp<M, R> extends 'gt'
      ? TakeOut<R, Rest>
      : [D, Sub<R, M>]
    : never
 
// Schoolbook long division over the dividend's digits, most significant first.
type LongDiv<
  Ds extends Digit[],
  T extends [Digit, Num][],
  R extends Num = [],
  Q extends Digit[] = [],
> = Ds extends [infer H extends Digit, ...infer Rest extends Digit[]]
  ? TakeOut<Trim<[H, ...R]>, T> extends [infer QD extends Digit, infer NR extends Num]
    ? LongDiv<Rest, T, NR, [...Q, QD]>
    : never
  : [Q, R]
 
type ToDigits<S extends string, Acc extends Digit[] = []> =
  S extends `${infer H extends Digit}${infer Rest}` ? ToDigits<Rest, [...Acc, H]> : Acc
 
type ToNum<S extends string, Acc extends Num = []> =
  S extends `${infer H extends Digit}${infer Rest}` ? ToNum<Rest, [H, ...Acc]> : Trim<Acc>
 
type JoinDigits<D extends Digit[], Acc extends string = ''> =
  D extends [infer H extends Digit, ...infer Rest extends Digit[]]
    ? JoinDigits<Rest, `${Acc}${H}`>
    : Acc
 
type JoinNum<D extends Num, Acc extends string = ''> =
  D extends [infer H extends Digit, ...infer Rest extends Num]
    ? JoinNum<Rest, `${H}${Acc}`>
    : Acc extends ''
      ? '0'
      : Acc
 
type StripZeros<S extends string> =
  S extends `0${infer Rest}` ? (Rest extends '' ? '0' : StripZeros<Rest>) : S
 
// Back to a number literal, carrying the sign only when the value is not zero.
type Signed<S extends string, Neg extends boolean> =
  S extends '0'
    ? 0
    : (Neg extends true ? `-${S}` : S) extends `${infer N extends number}`
      ? N
      : never
 
type Magnitude<N extends number> = `${N}` extends `-${infer A}` ? A : `${N}`
type IsNeg<N extends number> = `${N}` extends `-${string}` ? true : false
type Xor<A extends boolean, B extends boolean> = A extends B ? false : true
 
type Divide<Dividend extends number, Divisor extends number> =
  Divisor extends 0
    ? never
    : LongDiv<ToDigits<Magnitude<Dividend>>, Multiples<ToNum<Magnitude<Divisor>>>> extends [
          infer Q extends Digit[],
          infer R extends Num,
        ]
      ? [
          Signed<StripZeros<JoinDigits<Q>>, Xor<IsNeg<Dividend>, IsNeg<Divisor>>>,
          Signed<JoinNum<R>, IsNeg<Dividend>>,
        ]
      : never

Digits as tuples, and back again

Every arithmetic trick here rests on one conversion. Ones maps a digit character to a tuple of that length, which turns single-digit addition into tuple concatenation, and Char maps a tuple length back to a digit character. DigitOf is the return trip, reading T['length'] and looking it up:

// DigitOf<[1, 1, 1, 1]> -> Char[4] -> '4'
// [...Ones['7'], ...Ones['5']] -> a tuple of length 12

A magnitude is then a tuple of digit characters stored least significant first, with leading zeros stripped, and zero represented by the empty tuple. Little-endian storage is what makes the loops cheap: [H, ...R] prepends a new least significant digit, which is exactly the shift that long division needs at every step.

One column of addition, one column of subtraction

AddStep concatenates the two digit tuples and the carry, then asks a single question: does the result still contain ten elements after Ten is matched off the front? If it does, the leftover is the digit written down and the carry out is 1. If the pattern does not match at all, the total was under ten and nothing carries.

SubStep has the same shape with one adjustment. A column of a subtraction can go negative, and tuples cannot, so the whole thing is offset by ten: [...Ten, ...Ones[A]] is matched against [...Ones[B], ...Flag[Bo], ...infer Rest], leaving Rest at length 10 + A - B - borrow, always between 0 and 19. Ten or more elements means the column was non-negative, so strip the offset and borrow nothing. Fewer than ten means it went negative, and Rest is already the correct digit with a borrow out of 1.

// AddStep<'7', '5', 0>  -> 12 elements -> ['2', 1]
// SubStep<'3', '8', 0>  -> 10 + 3 - 8 = 5 elements -> ['5', 1]
// SubStep<'9', '4', 1>  -> 10 + 9 - 4 - 1 = 14 elements -> ['4', 0]

Add and Sub walk both operands in step, pass the carry or borrow along, and push each digit onto an accumulator. When one operand runs out first, the recursion feeds itself ['0'] for that side rather than branching into a separate padding type. Sub is only ever called when the result is non-negative, so it never has to report a final borrow, and it finishes with Trim because a subtraction is the one operation that can produce leading zeros.

Comparing without subtracting

CmpLen pops one element off each tuple until one of them is empty, which gives 'lt', 'eq' or 'gt' for lengths. That single type does two jobs. Applied to magnitudes it compares digit counts, and a number with more digits is larger as long as neither has leading zeros. Applied to Ones[AH] and Ones[BH] it compares two digits. When the digit counts tie, CmpTop matches [...infer AR, infer AH] to peel digits off the end of the tuple, which in little-endian order is the most significant end, and stops at the first position where the two differ.

Nine multiples, computed once

The expensive part of long division is choosing the next quotient digit: the largest q with q * Divisor still at or below the current remainder. Searching for it with repeated subtraction inside the loop would redo the same work sixteen times over. Multiples instead builds the full table [['9', 9 * D], ['8', 8 * D], ..., ['0', 0]] once, by adding the divisor to a running total nine times and prepending each result, which leaves the table in descending order for free.

TakeOut then walks that table from the top and returns the first entry whose multiple is not greater than the remainder, together with the remainder minus that multiple. The ['0', []] row at the bottom always matches, so the search cannot fall off the end.

The division loop

LongDiv is the paper method, unchanged. For each digit of the dividend, from the most significant end, it forms Trim<[H, ...R]>, which is the previous remainder times ten plus the new digit. TakeOut supplies the quotient digit and the new remainder, the quotient digit is appended, and the loop moves on. Termination is immediate to see: one digit leaves Ds per step, and Ds has at most sixteen of them.

// Divide<15, 6>, table = [['9', 54], ['8', 48], ..., ['2', 12], ['1', 6], ['0', 0]]
// H = '1'  R = 1   largest fit is 0 * 6   Q = '0'   R = 1
// H = '5'  R = 15  largest fit is 2 * 6   Q = '02'  R = 3
// quotient '02' -> StripZeros -> '2', remainder 3

The remainder stays strictly below the divisor after every step, so it never grows past the divisor's digit count, and the cost of the whole division is proportional to the digits of the dividend times the digits of the divisor. Seventeen digits cost about as much as three.

Signs, and the trip back to number

The arithmetic never sees a minus sign. Magnitude strips one off the template literal form of the input, IsNeg records whether there was one, and Signed puts it back at the end. Truncation toward zero is then two independent rules: the quotient is negative when exactly one operand was, which is Xor, and the remainder simply inherits the sign of the dividend.

Signed converts a digit string back into a number literal through S extends `${infer N extends number}`. That inference only succeeds when the string is the canonical form of the number, which is why the quotient passes through StripZeros first: '02' would infer nothing, while '2' gives 2. The zero case is special-cased ahead of the conversion, since '-0' is not a form any test expects to see.

Edge cases the tests cover

Once addition, subtraction and comparison exist as types, division is the loop that was waiting for them.

This challenge is originally from here.

Share this challenge

Related Challenges

Learn the Concepts

Become a TypeScript Pro

Track your progress through 200+ hands-on challenges. Free, sign in with GitHub.

Or start solving right away: explore all TypeScript challenges