Solution that avoids the need for creating digit dictionaries or matrices. I utilized a Sum type, which I created during the 476 Sum challenge.
type SumDigits<
A1 extends number,
A2 extends number,
Acc extends unknown[][] = [[], []]
> = Acc[0]['length'] extends A1
? Acc[1]['length'] extends A2
? [...Acc[0], ...Acc[1]]['length']
: SumDigits<A1, A2, [Acc[0], [unknown, ...Acc[1]]]>
: SumDigits<A1, A2, [[unknown, ...Acc[0]], Acc[1]]>;
type SumHelper<A extends string, B extends string, Rest extends number = 0> =
A extends `${infer HeadA extends number}${infer TailA}`
? B extends `${infer HeadB extends number}${infer TailB}`
? `${SumDigits<SumDigits<HeadA, HeadB>, Rest>}` extends `${infer SumRest extends number}${infer Result extends number}`
? `${Result}${SumHelper<TailA, TailB, SumRest>}`
: `${SumDigits<SumDigits<HeadA, HeadB>, Rest>}${SumHelper<TailA, TailB, 0>}`
: Rest extends 0 ? A : SumHelper<A, '0', Rest>
: Rest extends 0 ? B : SumHelper<B, '0', Rest>;
type Sum<A extends string | number | bigint, B extends string | number | bigint> =
ReverseString<SumHelper<ReverseString<`${A}`>, ReverseString<`${B}`>>>;
type MultiplyReverseString<S extends string> = S extends `${infer Head}${infer Tail}`
? `${ReverseString<Tail>}${Head}`
: '';
type MultiplyDigits<
A1 extends number,
A2 extends number,
MultiplyCounter extends unknown[] = [],
Acc extends unknown[][] = [[], []]
> = MultiplyCounter['length'] extends A1
? Acc[0]['length']
: Acc[1]['length'] extends A2
? MultiplyDigits<A1, A2, [unknown, ...MultiplyCounter], [[...Acc[0], ...Acc[1]], []]>
: MultiplyDigits<A1, A2, MultiplyCounter, [Acc[0], [unknown, ...Acc[1]]]>;
type CreateMultiplyComponent<A extends string, B extends number, Rest extends number = 0> =
A extends `${infer Head extends number}${infer Tail}`
? `${Sum<MultiplyDigits<B, Head>, Rest>}` extends `${infer SumRest extends number}${infer Result extends number}`
? `${Result}${CreateMultiplyComponent<Tail, B, SumRest>}`
: `${Sum<MultiplyDigits<B, Head>, Rest>}${CreateMultiplyComponent<Tail, B, 0>}`
: Rest extends 0 ? '' : `${Rest}`;
type IsAOrBZero<A extends string, B extends string> = '0' extends A | B ? true : false;
type MultiplyHelper<
A extends string,
B extends string,
Zeros extends string = ''
> = B extends `${infer Head extends number}${infer Tail}`
? Sum<
ReverseString<`${Zeros}${CreateMultiplyComponent<A, Head>}`>,
MultiplyHelper<A, Tail, `${Zeros}0`>
>
: 0;
type Multiply<A extends string | number | bigint, B extends string | number | bigint> =
IsAOrBZero<`${A}`, `${B}`> extends true
? '0'
: MultiplyHelper<MultiplyReverseString<`${A}`>, MultiplyReverseString<`${B}`>>;
Solution by user1808 #32694
type Num<A extends number, P extends 1[] = []> = A extends P['length'] ? P : Num<A, [1, ...P]>
type PlusNums<A extends number, B extends number> = Num<A> extends [...infer P] ? Num<B> extends [...infer Q] ? [...P, ...Q]['length'] : never : never
type MinusOne<A extends number, P extends 1[] = [1], Cnt extends 1[] = []> = A extends P['length'] ? Cnt['length'] : MinusOne<A, [...P, 1], [...Cnt, 1]>
type GreaterThanEqual<A extends number , B extends number, P = Num<A>, Q = Num<B>> = P extends 1[] ? Q extends 1[] ? Q['length'] extends 0 ? true:
P['length'] extends 0 ? false :
P extends [1, ...infer R] ?
Q extends [1, ...infer S] ?
GreaterThanEqual<A, B, R, S>
: never
: never
: never
: never
type StringNum<A extends string | number | bigint> = A extends string ? A : `${A}`
type StringSize<A extends string, P extends 1[] = []> = A extends `${number}${infer B}` ? StringSize<B, [1, ...P]> : P['length']
type Reverse<A extends string> = A extends `${infer B}${infer C}` ? `${Reverse<C>}${B}` : ""
type ArrayJoin<A extends unknown[], P extends string = ""> = A['length'] extends 0 ? P : A extends [infer K extends number, ...infer B] ? ArrayJoin<B, `${P}${K}`> : never
type AppendZeros<A extends string, Count extends number, P extends 0[] = []> = P['length'] extends Count ? `${A}${ArrayJoin<P>}` : AppendZeros<A, Count, [0, ...P]>
type ReverseSum<A extends string, B extends string, Result extends string = "" , PlusOne = false> =
A extends `${infer AFirst extends number}${infer ARest}` ?
B extends `${infer BFirst extends number}${infer BRest}` ?
PlusNums<PlusNums<AFirst, BFirst>, PlusOne extends true ? 1 : 0> extends (infer U extends number)
? `${U}` extends `${infer UFirst extends number}${infer ULast extends number}`
? ARest extends "" ? `${Result}${ULast}${UFirst}` :ReverseSum<ARest, BRest, `${Result}${ULast}`, true>
: ReverseSum<ARest, BRest, `${Result}${U}`, false>
: never
: Result
: Result
type MakeSameOrder<A extends string, B extends string> =
StringSize<A> extends StringSize<B> ? [A, B] :
GreaterThanEqual<StringSize<A>, StringSize<B>> extends true ?
MakeSameOrder<A, AppendZeros<B, 1>> :
MakeSameOrder<AppendZeros<A,1>, B>
type Sum<A extends string | number | bigint, B extends string | number | bigint> = MakeSameOrder<Reverse<`${A}`>, Reverse<`${B}`>> extends [infer U extends string, infer R extends string] ?
Reverse<ReverseSum<U, R>>
: never
type Time<A extends string, Times extends number, P extends 1[] = [1], Result extends string = A> = Times extends P['length'] ? Result :Time<A, Times, [...P, 1], Sum<Result, A>>
type TimeWithZero<A extends string, Times extends number> = Times extends 0 ? "0" : Time<A, Times>
type RecursiveMultiply<A extends string, B extends string, Result extends string = "0"> =
A extends "" ? Result :
A extends `${infer AFirst extends number}${infer ARest}` ?
AFirst extends 0 ?
RecursiveMultiply<ARest, B, Result>: Time<B, AFirst> extends `${infer NewResult extends string}` ?
RecursiveMultiply<ARest, B, Sum<Result, AppendZeros<NewResult, StringSize<ARest>>>>
: never
: Result
type Multiply<A extends string | number | bigint, B extends string | number | bigint> = `${B}` extends "0" ? "0" : RecursiveMultiply<`${A}` ,`${B}`>
Solution by john-cremit #32496
type ReverseString<S extends string> = S extends `${infer First}${infer Rest}`
? `${ReverseString<Rest>}${First}`
: "";
type Tuple<T, C extends 0[] = []> = C["length"] extends T
? C
: Tuple<T, [...C, 0]>;
type SimpleAdd<A extends number, B extends number, Carry extends number = 0> = [
...Tuple<A>,
...Tuple<B>,
...Tuple<Carry>
]["length"];
type SumReversedString<
A extends string,
B extends string,
Carry extends number = 0
> = A extends `${infer FirstA extends number}${infer RestA}`
? B extends `${infer FirstB extends number}${infer RestB}`
? `${SimpleAdd<FirstA, FirstB, Carry> &
number}` extends `${infer NewCarry extends number}${infer Sum extends number}`
? `${Sum}${SumReversedString<RestA, RestB, NewCarry>}`
: `${SimpleAdd<FirstA, FirstB, Carry> & number}${SumReversedString<
RestA,
RestB,
0
>}`
: SumReversedString<A, `${Carry}`>
: B extends `${number}${string}`
? SumReversedString<`${Carry}`, B>
: Carry extends 0
? ""
: `${Carry}`;
type Matrix<
A extends number,
B extends number,
C extends 0[] = []
> = C["length"] extends B ? [] : [...Tuple<A>, ...Matrix<A, B, [...C, 0]>];
type SingleMultiply<
A extends number,
B extends number,
Carry extends number = 0
> = [...Matrix<A, B>, ...Tuple<Carry>]["length"];
type SingleMultiplyLong<
S extends number,
L extends string,
Carry extends number = 0
> = L extends `${infer First extends number}${infer Rest}`
? `${SingleMultiply<S, First, Carry> &
number}` extends `${infer NewCarry extends number}${infer Sum extends number}`
? `${Sum}${SingleMultiplyLong<S, Rest, NewCarry>}`
: `${SingleMultiply<S, First, Carry> & number}${SingleMultiplyLong<
S,
Rest,
0
>}`
: Carry extends 0
? ""
: `${Carry}`;
type LeadingZero<N extends number, C extends 0[] = []> = C["length"] extends N
? ""
: `0${LeadingZero<N, [...C, 0]>}`;
type MultiplyReversedString<
A extends string,
B extends string,
C extends 0[] = []
> = A extends `${infer FirstA extends number}${infer RestA}`
? SumReversedString<
`${LeadingZero<C["length"]>}${SingleMultiplyLong<FirstA, B>}`,
MultiplyReversedString<RestA, B, [...C, 0]>
>
: "";
type Multiply<
A extends string | number | bigint,
B extends string | number | bigint
> = "0" extends `${A}` | `${B}`
? "0"
: ReverseString<
MultiplyReversedString<ReverseString<`${A}`>, ReverseString<`${B}`>>
>;
Solution by vangie #32393
type AddMap = [
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'],
['1', '2', '3', '4', '5', '6', '7', '8', '9', '10'],
['2', '3', '4', '5', '6', '7', '8', '9', '10', '11'],
['3', '4', '5', '6', '7', '8', '9', '10', '11', '12'],
['4', '5', '6', '7', '8', '9', '10', '11', '12', '13'],
['5', '6', '7', '8', '9', '10', '11', '12', '13', '14'],
['6', '7', '8', '9', '10', '11', '12', '13', '14', '15'],
['7', '8', '9', '10', '11', '12', '13', '14', '15', '16'],
['8', '9', '10', '11', '12', '13', '14', '15', '16', '17'],
['9', '10', '11', '12', '13', '14', '15', '16', '17', '18']
];
type Reverse<S extends string> = S extends `${infer E}${infer R}`
? `${Reverse<R>}${E}`
: S; //反转字符串 从低位开始算
type Get<X, Y> = X extends keyof AddMap
? Y extends keyof AddMap[X]
? AddMap[X][Y]
: '0'
: '0'; //从 Map 中取运算结果
type AddTwo<A extends string, B extends string> = B extends ''
? A
: A extends `1${infer R}${infer N}`
? `1${Get<R, B>}`
: Get<A, B>; // 加两个单位数
type AddThree<A extends string, B extends string, C extends string> = AddTwo<
AddTwo<A, B>,
C
>; // 加三个单位数 第三个数为进位
type SumString<
A extends string,
B extends string,
E extends string = ''
> = A extends `${infer A1}${infer A2}`
? B extends `${infer B1}${infer B2}`
? `${AddThree<A1, B1, E> extends `1${infer S}${infer N}`
? S
: AddThree<A1, B1, E>}${SumString<
A2,
B2,
AddThree<A1, B1, E> extends `1${infer S}${infer N}` ? '1' : ''
>}`
: E extends ''
? A
: SumString<A, '1'>
: E extends ''
? B
: SumString<'1', B>;
type Format<S extends string> = S extends `${infer L}_${infer R}`
? `${L}${Format<R>}`
: S extends `${infer A}n${infer B}`
? `${A}${Format<B>}`
: S; //格式化特殊数字
type Sum<
A extends string | number | bigint,
B extends string | number | bigint
> = Reverse<SumString<Reverse<Format<`${A}`>>, Reverse<Format<`${B}`>>>>;
type MulMap = [
['0', '0', '0', '0', '0', '0', '0', '0', '0', '0'],
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'],
['0', '2', '4', '6', '8', '01', '21', '41', '61', '81'],
['0', '3', '6', '9', '21', '51', '81', '12', '42', '72'],
['0', '4', '8', '21', '61', '02', '42', '82', '23', '63'],
['0', '5', '01', '51', '02', '52', '03', '53', '04', '54'],
['0', '6', '21', '81', '42', '03', '63', '24', '84', '45'],
['0', '7', '41', '12', '82', '53', '24', '94', '65', '36'],
['0', '8', '61', '42', '23', '04', '84', '65', '46', '27'],
['0', '9', '81', '72', '63', '54', '45', '36', '27', '18']
];
type GetMul<X extends string, Y extends string> = X extends keyof MulMap
? Y extends keyof MulMap[X]
? MulMap[X][Y]
: '0'
: '0';
type MulOne<
X extends string,
Y extends string,
O extends string = ''
> = X extends '0'
? '0'
: X extends `${infer E}${infer R}`
? SumString<`${O}${GetMul<E, Y>}`, MulOne<R, Y, `0${O}`>>
: '0';
type MulAll<
X extends string,
Y extends string,
O extends string = ''
> = X extends '0'
? '0'
: Y extends '0'
? '0'
: Y extends `${infer E}${infer R}`
? SumString<`${O}${MulOne<X, E>}`, MulAll<X, R, `0${O}`>>
: '0';
type Multiply<
A extends string | number | bigint,
B extends string | number | bigint
> = Reverse<MulAll<Reverse<Format<`${A}`>>, Reverse<Format<`${B}`>>>>;
type T = Multiply<'43423', '321543'>;
Solution by Royce-DaDaDa #29812
// Utils
type Reverse<S extends string> = S extends `${infer F}${infer R}`
? `${Reverse<R>}${F}`
: S;
// Sum helpers
type SumMod10 = [
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9],
[1, 2, 3, 4, 5, 6, 7, 8, 9, 0],
[2, 3, 4, 5, 6, 7, 8, 9, 0, 1],
[3, 4, 5, 6, 7, 8, 9, 0, 1, 2],
[4, 5, 6, 7, 8, 9, 0, 1, 2, 3],
[5, 6, 7, 8, 9, 0, 1, 2, 3, 4],
[6, 7, 8, 9, 0, 1, 2, 3, 4, 5],
[7, 8, 9, 0, 1, 2, 3, 4, 5, 6],
[8, 9, 0, 1, 2, 3, 4, 5, 6, 7],
[9, 0, 1, 2, 3, 4, 5, 6, 7, 8]
];
type SumCarryOver = [
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 1, 1],
[0, 0, 0, 0, 0, 0, 0, 1, 1, 1],
[0, 0, 0, 0, 0, 0, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 1, 1, 1, 1, 1, 1],
[0, 0, 0, 1, 1, 1, 1, 1, 1, 1],
[0, 0, 1, 1, 1, 1, 1, 1, 1, 1],
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
];
type StringSum<
A extends string,
B extends string,
C extends number = 0
> = A extends `${infer AF extends number}${infer AR}`
? B extends `${infer BF extends number}${infer BR}`
? `${SumMod10[SumMod10[AF][BF]][C]}${StringSum<
AR,
BR,
SumMod10[SumCarryOver[AF][BF]][SumCarryOver[SumMod10[AF][BF]][C]]
>}`
: `${SumMod10[AF][C]}${SumCarryOver[AF][C] extends 1
? StringSum<AR, '', 1>
: AR}`
: B extends `${infer BF extends number}${infer BR}`
? `${SumMod10[BF][C]}${SumCarryOver[BF][C] extends 1
? StringSum<'', BR, 1>
: BR}`
: C extends 0
? ''
: `${C}`;
type Sum<
A extends string | number | bigint,
B extends string | number | bigint
> = Reverse<StringSum<Reverse<`${A}`>, Reverse<`${B}`>>>;
// Multiply helpers
type MultiplyMod10 = [
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9],
[0, 2, 4, 6, 8, 0, 2, 4, 6, 8],
[0, 3, 6, 9, 2, 5, 8, 1, 4, 7],
[0, 4, 8, 2, 6, 0, 4, 8, 2, 6],
[0, 5, 0, 5, 0, 5, 0, 5, 0, 5],
[0, 6, 2, 8, 4, 0, 6, 2, 8, 4],
[0, 7, 4, 1, 8, 5, 2, 9, 6, 3],
[0, 8, 6, 4, 2, 0, 8, 6, 4, 2],
[0, 9, 8, 7, 6, 5, 4, 3, 2, 1]
];
type MultiplyCarryOver = [
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 1, 1, 1, 2, 2, 2],
[0, 0, 0, 1, 1, 2, 2, 2, 3, 3],
[0, 0, 1, 1, 2, 2, 3, 3, 4, 4],
[0, 0, 1, 1, 2, 3, 3, 4, 8, 5],
[0, 0, 1, 2, 2, 3, 4, 4, 5, 6],
[0, 0, 1, 2, 3, 4, 4, 5, 6, 7],
[0, 0, 1, 2, 3, 4, 5, 6, 7, 8]
];
type MultiplyWithZero<T> = '0' extends T ? true : false;
type TrailingZeros<N extends number, I extends 1[] = []> = I['length'] extends N
? ''
: `0${TrailingZeros<N, [...I, 1]>}`;
type MultiplyWithDigit<
S extends string,
D extends number,
C extends number = 0
> = S extends `${infer F extends number}${infer R}`
? `${SumMod10[MultiplyMod10[F][D]][C]}${MultiplyWithDigit<
R,
D,
SumMod10[MultiplyCarryOver[F][D]][SumCarryOver[MultiplyMod10[F][D]][C]]
>}`
: C extends 0
? ''
: `${C}`;
type StringMultiply<
A extends string,
B extends string,
S extends string = '0',
I extends 1[] = []
> = B extends `${infer F extends number}${infer R}`
? StringMultiply<
A,
R,
Sum<
`${Reverse<MultiplyWithDigit<A, F>>}${TrailingZeros<I['length']>}`,
S
>,
[...I, 1]
>
: S;
type Multiply<
A extends string | number | bigint,
B extends string | number | bigint
> = MultiplyWithZero<`${A}` | `${B}`> extends true
? '0'
: StringMultiply<Reverse<`${A}`>, Reverse<`${B}`>>;
Solution by JohnLi1999 #27482
/**0~9 */
type Digit = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9;
/**个位 RRRF ==> F */
type DigitFirst<T extends string | number | bigint> = T extends string ?
(Number<T> extends Digit ?
Number<T> :
(T extends `${number}${infer R}` ? DigitFirst<R> : never)) :
DigitFirst<`${T}`>;
/**个位以上 RRRF ==> RRR */
type DigitRest<T extends string | number | bigint, _Result extends string = ``> = T extends string ?
(T extends `${infer F}${infer R extends `${any}${any}`}` ?
DigitRest<R, `${_Result}${F}`> :
Number<_Result> extends 0/*去0*/ ? `` : _Result) :
DigitRest<`${T}`>;
type MakeCounter<T extends number, _Result extends 1[] = []> = _Result[`length`] extends T ? _Result : MakeCounter<T, [..._Result, 1]>;
/**个位相加 */
type DigitAdd<X extends Digit, Y extends Digit> = [...MakeCounter<X>, ...MakeCounter<Y>][`length`] extends (infer N extends number) ? N : 0;
/**Parse Int */
type Number<T extends string | number | bigint> = T extends `0${infer R}`/*去0*/ ? Number<R> : T extends `${infer N extends number | bigint}` ? N : 0;
/**+1（进位） */
type AddOne<T extends number | string, _DigitAdd extends number = DigitAdd<DigitFirst<T>, 1>> = `${_DigitAdd extends Digit ? DigitRest<T> : /*进位*/AddOne<DigitRest<T>>}${DigitFirst<_DigitAdd>}`;
/**个位乘 */
type DigitMultiply<T extends string | number | bigint, U extends Digit, _Counter extends 1[] = [], _Result extends string = `0`> = _Counter[`length`] extends U ? _Result : DigitMultiply<T, U, [..._Counter, 1], Sum<_Result, T>>;
/**x10^n */
type TenPow<T extends string | number | bigint, N extends number, _Counter extends 1[] = []> = _Counter[`length`] extends N ? T : `${TenPow<T, N, [..._Counter, 1]>}0`;
/**加法器（自然数） */
type Sum<A extends string | number | bigint, B extends string | number | bigint, _Result extends string = ``, _DigitAdd extends number = DigitAdd<DigitFirst<A>, DigitFirst<B>>> =
`${A}${B}` extends `` ? _Result : //return
Sum<DigitRest<A>, _DigitAdd extends Digit ? DigitRest<B> : /*进位*/AddOne<DigitRest<B>>, `${DigitFirst<_DigitAdd>}${_Result}`>;
/**乘法器（自然数） */
type Multiply<A extends string | number | bigint, B extends string | number | bigint, _CarryCounter extends 1[] = [], _Result extends string = `0`> = B extends `` ? _Result : //return
Multiply<A, DigitRest<B>, [..._CarryCounter, 1], Sum<_Result, TenPow<DigitMultiply<A, DigitFirst<B>>, _CarryCounter[`length`]>>>;
// 123 * 12345 ==> (123 * 5)
// ==> + (123 * 40)
// ==> + (123 * 300)
// ==> + (123 * 2000)
// ==> + (123 * 10000)
Solution by E-uler #25531
// handles arbitrarily large numbers
type IntADT = number | string | bigint;
type DigitLUT = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'];
type Digit = DigitLUT[number];
type Multiply<
A extends IntADT,
B extends IntADT,
B_TUPLE extends Digit[] = IntToTuple<B>,
OUTPUT extends Digit[] = [],
OFFSET extends number = 0,
B_LSD extends Digit = B_TUPLE extends [] ? '0' : Last<B_TUPLE, Digit>,
MUL extends IntADT = MultiplyByDigit<A, B_LSD>,
MUL_LSHIFT extends IntADT = LeftShift<MUL, OFFSET>,
NEXT extends Digit[] = $sum<never, MUL_LSHIFT, OUTPUT>,
IS_ANY_ZERO extends boolean = Any<[Equal<`${A}`, '0'>, Equal<`${B}`, '0'>]>,
RESULT extends IntADT = IS_ANY_ZERO extends true ? '0'
: B_TUPLE extends []
? Join<OUTPUT>
: Multiply<A, B, Pop<B_TUPLE>, NEXT, Add<OFFSET, 1>>,
> = RESULT;
type MultiplyByDigit<
A extends IntADT,
B extends Digit,
A_TUPLE extends Digit[] = IntToTuple<A>,
OUTPUT extends Digit[] = [],
CARRY_IN extends Digit = '0',
A_LSD extends Digit = A_TUPLE extends [] ? '0' : Last<A_TUPLE, Digit>,
MUL extends number = Add<MultiplyDigits<A_LSD, B>, CARRY_IN>,
CURR extends Digit = LSD<MUL>,
CARRY_OUT extends Digit = `${MUL}` extends CURR ? '0' : MSD<MUL>,
NEXT extends Digit[] = Unshift<OUTPUT, CURR>,
IS_ANY_ZERO extends boolean = Any<[Equal<`${A}`, '0'>, Equal<B, '0'>]>,
RESULT extends IntADT = IS_ANY_ZERO extends true ? '0'
: A_TUPLE extends []
? CARRY_IN extends '0' ? Join<OUTPUT> : Join<Unshift<OUTPUT, CARRY_IN>>
: MultiplyByDigit<A, B, Pop<A_TUPLE>, NEXT, CARRY_OUT>
> = RESULT;
type MultiplyDigits<
A extends Digit,
B extends Digit,
X extends number = `${A}` extends `${infer X extends number}` ? X : 0,
Y extends number = `${B}` extends `${infer Y extends number}` ? Y : 0,
OUTPUT extends unknown[] = [],
RESULT extends IntADT = Y extends 0
? `${OUTPUT["length"]}`
: MultiplyDigits<A, B, X, Subtract<Y, 1>, Concat<OUTPUT, Repeat<X>>>
> = RESULT;
type multiply_digits_tests = [
Expect<Equal<MultiplyDigits<'0', '0'>, '0'>>,
Expect<Equal<MultiplyDigits<'0', '9'>, '0'>>,
Expect<Equal<MultiplyDigits<'1', '1'>, '1'>>,
Expect<Equal<MultiplyDigits<'1', '5'>, '5'>>,
Expect<Equal<MultiplyDigits<'5', '1'>, '5'>>,
Expect<Equal<MultiplyDigits<'6', '6'>, '36'>>,
Expect<Equal<MultiplyDigits<'8', '9'>, '72'>>,
];
type multiply_by_digit_tests = [
Expect<Equal<MultiplyByDigit<'0', '0'>, '0'>>,
Expect<Equal<MultiplyByDigit<1, '2'>, '2'>>,
Expect<Equal<MultiplyByDigit<999, '0'>, '0'>>,
Expect<Equal<MultiplyByDigit<'999', '1'>, '999'>>,
Expect<Equal<MultiplyByDigit<13, '2'>, '26'>>,
Expect<Equal<MultiplyByDigit<999, '9'>, '8991'>>,
Expect<Equal<MultiplyByDigit<'1923', '9'>, '17307'>>,
Expect<Equal<MultiplyByDigit<123456789, '9'>, '1111111101'>>,
];
type $sum<
A extends IntADT,
B extends IntADT,
A_TUPLE extends Digit[] = IntToTuple<A>,
B_TUPLE extends Digit[] = IntToTuple<B>,
OUTPUT extends Digit[] = [],
CARRY_IN extends 0 | 1 = 0,
A_LSD extends Digit = A_TUPLE extends [] ? '0' : Last<A_TUPLE, Digit>,
B_LSD extends Digit = B_TUPLE extends [] ? '0' : Last<B_TUPLE, Digit>,
SUM extends number = Add<CARRY_IN, Add<A_LSD, B_LSD>>,
CURR extends Digit = LSD<SUM>,
CARRY_OUT extends 0 | 1 = `${SUM}` extends `${CURR}` ? 0 : 1,
NEXT extends Digit[] = Unshift<OUTPUT, CURR>,
RESULT extends Digit[] = All<[Equal<A_TUPLE["length"], 0>, Equal<B_TUPLE["length"], 0>]> extends true
? CARRY_IN extends 1 ? Unshift<OUTPUT, '1'> : OUTPUT
: $sum<A, B, Pop<A_TUPLE>, Pop<B_TUPLE>, NEXT, CARRY_OUT>,
> = RESULT;
/** @returns Digit */
type MSD<N extends IntADT> =
`${N}` extends `${infer H extends Digit}${string}` ? H : '0';
/** @returns Digit */
type LSD<N extends IntADT> =
`${N}` extends `${string}${infer Rest extends `${infer H}${infer D extends Digit}`}`
? LSD<Rest>
: `${N}` extends `${infer X extends Digit}` ? X : never;
/** @returns string */
type LeftShift<
T extends IntADT,
N extends number = 1,
OUTPUT extends string = `${T}`,
NEXT extends string = `${OUTPUT}0`,
RESULT extends IntADT = N extends 0 ? OUTPUT : LeftShift<T, Subtract<N, 1>, NEXT>,
> = RESULT;
type IntToTuple<
N extends IntADT,
OUTPUT extends Digit[] = [],
CURR extends Digit = `${N}` extends `${infer D extends Digit}${string}` ? D : never,
NEXT extends string = `${N}` extends `${CURR}${infer Rest}` ? Rest : never,
RESULT extends Digit[] = N extends '' ? OUTPUT : IntToTuple<NEXT, Push<OUTPUT, CURR>>,
> = RESULT;
type Join<T extends any[], OUTPUT extends string = ``> =
T extends [T[0], ...infer Rest]
? Join<Rest, `${OUTPUT}${T[0]}`>
: OUTPUT;
/** @returns number | never */
type Subtract<M extends IntADT, S extends IntADT> =
`${M}` extends `${infer A extends number}`
? `${S}` extends `${infer B extends number}`
? Repeat<A> extends [...Repeat<B>, ...infer Rest] ? Rest["length"] : never
: A
: never;
/** @returns number */
type Add<A extends IntADT, B extends IntADT> =
`${A}` extends `${infer X extends number}`
? `${B}` extends `${infer Y extends number}`
? Concat<Repeat<X>, Repeat<Y>>["length"]
: X
: `${B}` extends `${infer Y extends number}`
? Y
: 0;
type All<T extends boolean[]> =
T extends [infer B, ...infer Rest extends boolean[]]
? B extends true ? All<Rest> : false
: true;
type Any<T extends boolean[]> =
T extends [infer B, ...infer Rest extends boolean[]]
? B extends true ? true : Any<Rest>
: false;
type Shift<T extends unknown[], N extends number = 1> =
N extends 0 ? T
: T extends [infer _, ...infer Rest]
? Shift<Rest, Subtract<N, 1>>
: [];
type Unshift<T extends unknown[], U extends unknown> =
[U, ...T];
type Last<T extends U[], U = any> =
T extends [...infer _, infer P extends U] ? P : never;
type Pop<T extends unknown[], N extends number = 1> =
N extends 0 ? T
: T extends [...infer Rest, infer _]
? Pop<Rest, Subtract<N, 1>>
: [];
type Push<T extends unknown[], U extends unknown> =
[...T, U];
type Concat<T extends unknown[], U extends unknown[]> =
[...T, ...U];
type Repeat<N extends number, T extends unknown = null, M extends T[] = []> =
M["length"] extends N ? M : Repeat<N, T, Push<M, T>>;
Solution by MajorLift #22399
type IsIncludesZero<T> = [Extract<T, 0 | '0'>] extends [never] ? false : true
type MultiplyWithSmallNumber<
A extends string | number | bigint,
B extends string | number | bigint,
AC extends unknown[] = [],
T extends string = '0',
> = `${A}` extends `${infer X extends number}`
? X extends AC['length']
? T
: MultiplyWithSmallNumber<A, B, [unknown, ...AC], Sum<T, B>>
: never
type MultiplyNoZero<
A extends string | number | bigint,
B extends string | number | bigint,
T extends string = '0',
Add extends string = '',
> = ReverseString<`${A}`> extends `${infer F extends number}${infer R}`
? MultiplyNoZero<ReverseString<R>, B, Sum<`${MultiplyWithSmallNumber<F, B>}${Add}`, T>, `${Add}0`>
: T
type Multiply<
A extends string | number | bigint,
B extends string | number | bigint,
> = IsIncludesZero<A | B> extends true ? '0' : MultiplyNoZero<A, B>
Solution by thanhhtse04588 #22284
type _Number2Array<
N extends string,
_AddOne extends boolean = false,
_Result extends 0[] = [],
_NN extends number = `${ N }` extends `${ infer I extends number }` ? I : never,
> = _Result['length'] extends _NN
? _AddOne extends false ? _Result : [ 0, ..._Result ]
: _Number2Array<N, _AddOne, [ ..._Result, 0 ]>
type _TwoSingleDigitSum<
A extends _DigitString,
B extends _DigitString,
_PlusOne extends boolean = false,
_Carry extends boolean = false,
_Counter extends 0[] = [],
_SumArray extends unknown[] = [ ..._Number2Array<A, _PlusOne>, ..._Number2Array<B> ],
> = _Counter['length'] extends 10
? _TwoSingleDigitSum<A, B, _PlusOne, true>
: _Carry extends false
? _Counter['length'] extends _SumArray['length']
? { carry: false, digit: _Counter['length'] }
: _TwoSingleDigitSum<A, B, _PlusOne, false, [ ..._Counter, 0 ]>
: [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ..._Counter ]['length'] extends _SumArray['length']
? { carry: true, digit: _Counter['length'] }
: _TwoSingleDigitSum<A, B, _PlusOne, true, [ ..._Counter, 0 ]>
type _DigitString = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
type _GetLast<T extends string | number | bigint, _Rest extends string = ''> = `${ T }` extends _DigitString
? { rest: _Rest, last: `${ T }` }
: `${ T }` extends `${ infer Rest extends string }${ infer I extends string }`
? _GetLast<I, `${ _Rest }${ Rest }`>
: { rest: '', last: '0' }
type Sum<
A extends string | number | bigint,
B extends string | number | bigint,
_PlusOne extends boolean = false,
_Result extends string = '',
_AL extends { rest: string, last: _DigitString } = _GetLast<A>,
_BL extends { rest: string, last: _DigitString } = _GetLast<B>,
_LastSum extends { carry: boolean, digit: number } = _TwoSingleDigitSum<_AL['last'], _BL['last'], _PlusOne>,
> = `${ _AL['rest'] }${ _BL['rest'] }` extends ''
? `${ _LastSum['carry'] extends true ? 1 : '' }${ _LastSum['digit'] }${ _Result }`
: Sum<_AL['rest'], _BL['rest'], _LastSum['carry'], `${ _LastSum['digit'] }${ _Result }`>
// 476
// =============================================================================
// Present
type _ShiftZero<T extends string> = T extends `0${ infer Rest }` ? (Rest extends '' ? '0' : _ShiftZero<Rest>) : T
type _TwoSingleDigitMultiply<
A extends _DigitString,
B extends _DigitString,
_Acc extends string = '0',
_Times extends 0[] = [],
_A extends _DigitString = _ShiftZero<A>,
_B extends _DigitString = _ShiftZero<B>,
> = `${ _Times['length'] }` extends _B
? _Acc extends `${ infer Tens }${ infer Single }`
? Single extends ''
? { carry: '0', digit: _Acc & _DigitString }
: { carry: Tens & _DigitString, digit: Single & _DigitString }
: never
: _TwoSingleDigitMultiply<_A, _B, Sum<_A, _Acc>, [ ..._Times, 0 ]>
type _OnlyOneSingleDigitMultiply<
A extends string,
B extends _DigitString,
_Carry extends _DigitString = '0',
_AL extends { rest: string, last: _DigitString } = _GetLast<A>,
_Step extends { carry: _DigitString, digit: _DigitString } = _TwoSingleDigitMultiply<_AL['last'], B, _Carry>,
_Result extends string = '',
> = _AL['rest'] extends ''
? `${ _Step['carry'] extends '0' ? '' : _Step['carry'] }${ _Step['digit'] }`
: `${ _OnlyOneSingleDigitMultiply<_AL['rest'], B, _Step['carry']> }${ _Step['digit'] }`
type Multiply<
A extends string | number | bigint,
B extends string | number | bigint,
_Acc extends string = '0',
_Zeroes extends string = '',
_BL extends { rest: string, last: _DigitString } = _GetLast<B>,
> = _BL['rest'] extends ''
? _ShiftZero<Sum<`${ _Acc }`, _OnlyOneSingleDigitMultiply<`${ A }${ _Zeroes }`, _BL['last']>>>
: Multiply<A, _BL['rest'], Sum<`${ _Acc }`, _OnlyOneSingleDigitMultiply<`${ A }${ _Zeroes }`, _BL['last']>>, `${ _Zeroes }0`>
Solution by lvjiaxuan #22281
// reverse a string
type Reverse<S extends string> = S extends `${infer F}${infer Rest}` ? `${Reverse<Rest>}${F}` : ''
// convert number to tuple, tail-recursion
type Number2Tuple<N extends number, _T extends unknown[] = []> = _T['length'] extends N ? _T : Number2Tuple<N, [..._T, unknown]>
// sum two numbers
type SumNumber<A extends number, B extends number> = [...Number2Tuple<A>, ...Number2Tuple<B>]['length'] & number
// sum two numbers in reversed string format
type SumReversedString<A extends string, B extends string> =
A extends `${infer AF extends number}${infer ARest}`
? B extends `${infer BF extends number}${infer BRest}`
? Reverse<`${SumNumber<AF, BF>}`> extends `${infer Gewei}${infer Shiwei}`
? `${Gewei}${SumReversedString<ARest, SumReversedString<BRest, Shiwei>>}`
: never
: A
: B
type Sum<A extends string | number | bigint, B extends string | number | bigint> = Reverse<SumReversedString<Reverse<`${A}`>, Reverse<`${B}`>>>
// ----Above is from Sum----
type MultiplicationTable = {
'00': 0, '01': 0, '02': 0, '03': 0, '04': 0, '05': 0, '06': 0, '07': 0, '08': 0, '09': 0,
'11': 1, '12': 2, '13': 3, '14': 4, '15': 5, '16': 6, '17': 7, '18': 8, '19': 9,
'22': 4, '23': 6, '24': 8, '25': 10, '26': 12, '27': 14, '28': 16, '29': 18,
'33': 9, '34': 12, '35': 15, '36': 18, '37': 21, '38': 24, '39': 27,
'44': 16, '45': 20, '46': 24, '47': 28, '48': 32, '49': 36,
'55': 25, '56': 30, '57': 35, '58': 40, '59': 45,
'66': 36, '67': 42, '68': 48, '69': 54,
'77': 49, '78': 56, '79': 63,
'88': 64, '89': 72,
'99': 81
}
// sort digits A and B, ouptut a string with the smaller one left and bigger one right
type SortDigits<A extends number | string, B extends number | string> = '0123456789' extends `${any}${A}${any}${B}${any}` ? `${A}${B}` : `${B}${A}`
// multiply two digits A and B
type MultiDigits<A extends number | string, B extends number | string> = MultiplicationTable[SortDigits<A, B> & keyof MultiplicationTable]
// append extra zero string right to a number. if the number is zero, just output '0'.
type WithZeros<N extends number, Z extends string> = N extends 0 ? '0' : `${N}${Z}`
// sub step of MultiplyReversedString, where A is a digit but B is a number, and iterate B
type MultiplyReversedString_2<A extends string, B extends string, _Zeros extends string = ''> =
B extends `${infer BF extends number}${infer BRest}`
? Reverse<Sum<WithZeros<MultiDigits<A, BF>, _Zeros>, Reverse<MultiplyReversedString_2<A, BRest, `${_Zeros}0`>>>>
: '0'
// sub step of MultiplyReversedString, where A and B are numbers, and iterate A
type MultiplyReversedString_1<A extends string, B extends string, _Zeros extends string = ''> =
A extends `${infer AF}${infer ARest}`
? Reverse<Sum<Reverse<MultiplyReversedString_2<AF, B, _Zeros>>, Reverse<MultiplyReversedString_1<ARest, B, `${_Zeros}0`>>>>
: '0'
// multiply two number A and B in reversed string format
type MultiplyReversedString<A extends string, B extends string> = MultiplyReversedString_1<A, B>
type Multiply<A extends string | number | bigint, B extends string | number | bigint> = Reverse<MultiplyReversedString<Reverse<`${A}`>, Reverse<`${B}`>>>
Solution by zhaoyao91 #22230
// your answers
namespace SumChallenge {
type NeedingCarryBit = `${1 | 2}${0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9}`;
// 20 => [0, 2]
type TransForm = {
[P in NeedingCarryBit]: P extends `${infer F extends number}${infer R extends number}`
? [R, F]
: never;
};
// ADD 较小的两个数相加
export type Add<
A extends number,
B extends number,
CountA extends 0[] = [],
CountB extends 0[] = []
> = CountA["length"] extends A
? CountB["length"] extends B
? [...CountA, ...CountB]["length"]
: Add<A, B, CountA, [0, ...CountB]>
: CountB["length"] extends B
? Add<A, B, [0, ...CountA], CountB>
: Add<A, B, [0, ...CountA], [0, ...CountB]>;
// 判断两个数字的大小
export type GreaterThan<
A extends number,
B extends number,
I extends 0[] = []
> = A extends B
? false
: I["length"] extends A
? I["length"] extends B
? false
: false
: I["length"] extends B
? true
: GreaterThan<A, B, [0, ...I]>;
// 反转字符串
export type ReverseString<S extends string> = S extends `${infer F}${infer R}`
? `${ReverseString<R>}${F}`
: "";
// 获取字符串长度
export type GetStringLength<
S extends string,
I extends 0[] = []
> = S extends `${string}${infer R}`
? GetStringLength<R, [0, ...I]>
: I["length"];
export type StringNumberAdd<
A extends string,
B extends string,
Jw extends number = 0
> = A extends `${infer AF extends number}${infer AR}`
? B extends `${infer BF extends number}${infer BR}`
? Add<AF, Add<BF, Jw>> extends infer AFBF extends number
? `${AFBF}` extends keyof TransForm
? `${TransForm[`${AFBF}`][0]}${StringNumberAdd<
AR,
BR,
TransForm[`${AFBF}`][1]
>}`
: `${AFBF}${StringNumberAdd<AR, BR, 0>}`
: never
: Jw extends 0
? A
: Add<Jw, AF> extends infer AFJW extends number
? `${AFJW}` extends keyof TransForm
? `${TransForm[`${AFJW}`][0]}${StringNumberAdd<
AR,
"",
TransForm[`${AFJW}`][1]
>}`
: `${AFJW}${StringNumberAdd<AR, "", 0>}`
: never
: Jw extends 0
? ""
: `${Jw}`;
export type Sum<
A extends string | number | bigint,
B extends string | number | bigint
> = ReverseString<
GreaterThan<GetStringLength<`${A}`>, GetStringLength<`${B}`>> extends true
? StringNumberAdd<ReverseString<`${A}`>, ReverseString<`${B}`>>
: StringNumberAdd<ReverseString<`${B}`>, ReverseString<`${A}`>>
>;
// 0 ~ 9 范围内的两个数相加， [a, b] a表示剩余数，b表示进位数
}
namespace MutiplyChallenge {
// 0. 生成一个保存每一相位的值的数组
type InitialZeroArr<
N extends number,
Res extends string[] = []
> = Res["length"] extends N ? Res : InitialZeroArr<N, [...Res, "0"]>;
type LitterNumberMul<
Base extends string,
B extends string,
I extends 0[] = [],
Res extends string = "0"
> = `${I["length"]}` extends B
? Res
: LitterNumberMul<Base, B, [0, ...I], SumChallenge.Sum<Base, Res>>;
type StringToRevArr<S extends string> = S extends `${infer F}${infer R}` ? [...StringToRevArr<R>, F] : [];
type ChangeArrByIndex<Arr extends string[], Tindex extends number, Value, I extends 0[] = []> =
Arr extends [infer F, ...infer R extends string[]] ?
I["length"] extends Tindex ? [Value, ...R]
: [F, ...ChangeArrByIndex<R, Tindex, Value, [0, ...I]>]
: [];
type GetArrValueByIndex<Arr extends string[], Index extends number, I extends 0[] = []> =
Arr extends [infer F, ...infer R extends string[]] ?
I["length"] extends Index ?
F
: GetArrValueByIndex<R, Index, [0, ...I]>
: never;
type MutiplyFirst<A extends string[], B extends string[], Res extends string[] = [], I1 extends 0[] = [], I2 extends 0[] = [], ResI extends number = SumChallenge.Add<I1["length"], I2["length"]>> =
I2["length"] extends B["length"] ?
I1["length"] extends A["length"] ?
Res
: MutiplyFirst<A, B, Res, [0, ...I1], []>
: MutiplyFirst<A, B,
ChangeArrByIndex<Res, ResI, SumChallenge.ReverseString<SumChallenge.Sum<SumChallenge.ReverseString<Res[ResI]>, LitterNumberMul<A[I1["length"]], B[I2["length"]]>>>>
, I1, [0, ...I2]>;
type MutiplySeconde<C extends string[], I extends 0[] = [], JW extends string = "0", Res extends string[] = []> =
I["length"] extends C["length"] ?
Res
: SumChallenge.ReverseString<SumChallenge.Sum<SumChallenge.ReverseString<C[I["length"]]>, SumChallenge.ReverseString<JW>>> extends `${infer F}${infer R}` ?
R extends "" ?
MutiplySeconde<C, [0, ...I], "0", [...Res, F]>
: MutiplySeconde<C, [0, ...I], R, [...Res, F]>
: never;
// 拼接字符串
type MutiplyThree<C extends string[]> = C extends [infer F extends string, ...infer R extends string[]] ?
`${MutiplyThree<R>}${F}`
: "";
// 去除前导0
type MultiplyFour<C extends string> = C extends `0${infer R}` ? MultiplyFour<R> : C extends "" ? "0" : C;
export type Multiply<A extends string | number | bigint, B extends string | number | bigint> = MultiplyFour<MutiplyThree<MutiplySeconde<MutiplyFirst<StringToRevArr<`${A}`>, StringToRevArr<`${B}`>, InitialZeroArr<30>>>>>;
}
type Multiply<A extends string | number | bigint, B extends string | number | bigint> = MutiplyChallenge.Multiply<A, B>;
Solution by acwink #22225
type Build<
T extends number,
Result extends Array<never> = []
> = Result["length"] extends T ? Result : Build<T, [...Result, never]>;
type Add<A extends number, B extends number> = [
...Build<A>,
...Build<B>
]["length"];
type stringToNumber<T> = `${T & string}` extends `${infer A extends number}`
? A
: never;
type Add2<A extends number, B extends number> = `${Add<A, B> &
number}` extends `1${infer G extends number}`
? {
overflow: 1;
value: G;
}
: {
overflow: 0;
value: Add<A, B>;
};
type Reverse<T extends string | number | bigint> =
`${T}` extends `${infer A}${infer B}` ? `${Reverse<B>}${A}` : T;
type GetSLast1<T extends string | number | bigint> =
`${T}` extends `${infer A}${infer B}` ? stringToNumber<A> : "";
type GetSLast<
T extends string | number | bigint,
B extends string | number | bigint
> = [GetSLast1<T>, GetSLast1<B>];
type GetSOther<T extends string | number | bigint> =
`${T}` extends `${infer A}${infer B}` ? B : "";
type GetHaveString<A, B> = A extends "" ? B : A;
type Sum1<
A extends string | number | bigint,
B extends string | number | bigint,
Overflow extends number = 0,
Result extends string = ""
> = [""] extends [A | B]
? [A, B] extends ["", ""]
? `${Result}${Overflow extends 0 ? "" : Overflow}`
: GetHaveString<A, B> extends `${infer Z}`
? Z extends ""
? Result
: Sum1<Z, Overflow, 0, Result>
: never
: GetSLast<A, B> extends [infer A1 extends number, infer B1 extends number]
? Add2<Add<A1, Overflow> & number, B1> extends {
overflow: infer O extends number;
value: infer V;
}
? Sum1<GetSOther<A>, GetSOther<B>, O, `${Result}${V & number}`>
: never
: Result;
type Sum<
A extends string | number | bigint,
B extends string | number | bigint
> = Reverse<Sum1<Reverse<A>, Reverse<B>>>;
type PushZero<B extends string, T extends Array<never>> = T extends [
infer A,
...infer C extends Array<never>
]
? PushZero<`${B}0`, C>
: B;
type Multiply2<
P extends string | number | bigint,
T extends string | number | bigint,
G extends Array<never> = [],
Result extends string = ""
> = P extends 0
? "0"
: P extends G["length"]
? Result
: Multiply2<P, T, [never, ...G], Sum<T, Result>>;
type GetOtherString<
G extends string | number | bigint,
C extends string | number | bigint
> = G extends `${C}${infer R}` ? R : G;
type Multiply1<
A extends string | number | bigint,
B extends string | number | bigint,
Index extends Array<never> = [],
Result extends string = ""
> = A extends ""
? Result
: ["0"] extends [`${A}` | `${B}`]
? "0"
: Multiply2<GetSLast1<A>, B> extends `${infer C}`
? Multiply1<
GetOtherString<A, GetSLast1<A>>,
B,
[never, ...Index],
Sum<PushZero<C, Index>, Result>
>
: never;
type Multiply<
A extends string | number | bigint,
B extends string | number | bigint
> = Multiply1<Reverse<A>, B>;
Solution by so11y #21648
type NumberWithinTen<
T extends string | number,
R extends unknown[] = []
> = `${R['length']}` extends `${T}` ? R : NumberWithinTen<T, [unknown, ...R]>
type StringToCharArray<T extends string> = T extends `${infer A}${infer B}`
? [A, ...StringToCharArray<B>]
: []
type StringToNumberArray<T extends string> = T extends `${infer A}${infer B}`
? [NumberWithinTen<A>, ...StringToNumberArray<B>]
: []
type Reverse<T extends unknown[]> = T extends [infer A, ...infer B]
? [...Reverse<B>, A]
: []
type Shift<T extends unknown[]> = T extends [unknown, ...infer A] ? A : T
type RemoveRightZero<T extends string> = T extends `0${infer A}`
? A extends ''
? '0'
: RemoveRightZero<A>
: T
type SumUnit<
A extends unknown[] | undefined,
B extends unknown[] | undefined,
C extends boolean = false
> = A extends unknown[]
? B extends unknown[]
? C extends true
? [...A, ...B, unknown]
: [...A, ...B]
: C extends true
? [...A, unknown]
: A
: B extends unknown[]
? C extends true
? [...B, unknown]
: B
: C extends true
? [unknown]
: undefined
type BasicSum<
A extends string | number | bigint,
B extends string | number | bigint,
Carry extends boolean = false,
AInNumberArray extends unknown[][] = Reverse<StringToNumberArray<`${A}`>>,
BInNumberArray extends unknown[][] = Reverse<StringToNumberArray<`${B}`>>,
UnitSum extends string = SumUnit<
AInNumberArray[0],
BInNumberArray[0],
Carry
> extends unknown[]
? `${SumUnit<AInNumberArray[0], BInNumberArray[0], Carry>['length']}`
: ''
> = UnitSum extends `${infer SU1}${infer SU2}`
? `${BasicSum<
A,
B,
SU2 extends '' ? false : true,
Shift<AInNumberArray>,
Shift<BInNumberArray>
>}${SU2 extends '' ? SU1 : SU2}`
: UnitSum
type Sum<
A extends string | number | bigint,
B extends string | number | bigint
> =
// @ts-ignore
RemoveRightZero<BasicSum<A, B>>
type MultiplyWithinTen<
A extends unknown[],
B extends unknown[]
> = B['length'] extends 0 ? [] : [...A, ...MultiplyWithinTen<A, Shift<B>>]
type MultiplyUnit<
A extends unknown[] | undefined,
B extends unknown[] | undefined,
Carry extends unknown[] = []
> = A extends unknown[]
? B extends unknown[]
? [...Carry, ...MultiplyWithinTen<A, B>]
: Carry['length'] extends 0
? unknown
: Carry
: Carry['length'] extends 0
? unknown
: Carry
type BasicMultiply<
A extends string | number | bigint,
B extends string | number | bigint,
C extends unknown[] = [],
AInNumberArray extends unknown[][] = Reverse<StringToNumberArray<`${A}`>>,
BInNumber extends unknown[] = NumberWithinTen<`${B}`>,
UnitResult extends string = MultiplyUnit<
AInNumberArray[0],
BInNumber,
C
> extends unknown[]
? // @ts-ignore
`${MultiplyUnit<AInNumberArray[0], BInNumber, C>['length']}`
: ''
> = UnitResult extends `${infer MU1}${infer MU2}`
? `${BasicMultiply<
A,
B,
MU2 extends '' ? [] : NumberWithinTen<MU1>,
Shift<AInNumberArray>,
BInNumber
>}${MU2 extends '' ? MU1 : MU2}`
: UnitResult
type SumProduct<
Product extends unknown[],
Result extends string = '0',
LeftZero extends string = ''
> = Product extends [infer A, ...infer B]
? // @ts-ignore
SumProduct<B, Sum<Result, `${A}${LeftZero}`>, `${LeftZero}0`>
: Result
type Multiply<
A extends string | number | bigint,
B extends string | number | bigint,
BInCharArray extends string[] = Reverse<StringToCharArray<`${B}`>>,
Product extends string[] = []
> = BInCharArray['length'] extends 0
? SumProduct<Product>
: Multiply<
A,
B,
Shift<BInCharArray>,
[...Product, BasicMultiply<A, BInCharArray[0]>]
>
Solution by theoolee #19951
type Numerable = string | number | bigint;
type DigitMap = {
"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 Digit = keyof DigitMap;
type Number = Digit[];
type Val<D extends Digit> = DigitMap[D];
type Inc<N extends Digit> = `${[1, ...Val<N>]["length"] & number}` & Digit;
type GetNumber<N extends Numerable> =
`${N}` extends `${infer D extends Digit}${infer S}`
? S extends ""
? [D]
: [D, ...GetNumber<S>]
: never;
type NumberToString<N extends Number, I = false> = N extends [
infer F extends Digit,
...infer R extends Number
]
? `${F}${NumberToString<R, true>}`
: I extends true
? ""
: "0";
type SplitCarry<
N extends number,
S = `${N}`
> = S extends `${infer C extends Digit}${infer V extends Digit}`
? [C, V]
: S extends Digit
? ["0", S]
: never;
type DigitSum<
A extends Digit,
B extends Digit,
Carry extends Digit = "0"
> = SplitCarry<[...Val<A>, ...Val<B>, ...Val<Carry>]["length"] & number>;
type RemoveLeadingZeros<N extends Number> = N extends [
infer F extends Digit,
...infer R extends Number
]
? R extends []
? [F]
: F extends "0"
? RemoveLeadingZeros<R>
: N
: [];
type Pad<N extends Number> = N extends [] ? ["0"] : N;
type NumberSum<
A extends Number,
B extends Number,
Carry extends Digit = "0"
> = [A, B] extends [["0"] | [], ["0"] | []]
? Carry extends "0"
? []
: [Carry]
: [Pad<A>, Pad<B>] extends [
[...infer RA extends Number, infer NA extends Digit],
[...infer RB extends Number, infer NB extends Digit]
]
? DigitSum<NA, NB, Carry> extends [infer Carry extends Digit, infer N]
? [...NumberSum<RA, RB, Carry>, N]
: never
: never;
type DigitMultiply<
A extends Digit,
B extends Digit,
Carry extends Digit = "0",
Sum extends 1[] = Val<A>,
Count extends Digit = "1"
> = [A, B] extends ["0", Digit] | [Digit, "0"]
? SplitCarry<Val<Carry>["length"]>
: Count extends B
? SplitCarry<[...Sum, ...Val<Carry>]["length"] & number>
: DigitMultiply<A, B, Carry, [...Sum, ...Val<A>], Inc<Count>>;
type NumberByDigitMultiply<
A extends Number,
B extends Digit,
Carry extends Digit = "0"
> = B extends "0"
? Carry extends "0"
? []
: [Carry]
: B extends "1"
? NumberSum<A, [Carry]>
: A extends []
? Carry extends "0"
? []
: [Carry]
: A extends [...infer RA extends Number, infer NA extends Digit]
? DigitMultiply<NA, B, Carry> extends [infer Carry extends Digit, infer N]
? [...NumberByDigitMultiply<RA, B, Carry>, N]
: never
: never;
type NumberMultiply<
A extends Number,
B extends Number,
Sum extends Number = [],
Zeros extends "0"[] = []
> = B extends [...infer R extends Number, infer N extends Digit]
? NumberMultiply<
A,
R,
NumberSum<Sum, NumberByDigitMultiply<[...A, ...Zeros], N>>,
["0", ...Zeros]
>
: Sum;
type Sum<A extends Numerable, B extends Numerable> = NumberToString<
RemoveLeadingZeros<NumberSum<GetNumber<A>, GetNumber<B>>>
>;
type Multiply<A extends Numerable, B extends Numerable> = NumberToString<
RemoveLeadingZeros<NumberMultiply<GetNumber<A>, GetNumber<B>>>
>;
Solution by BulatDashiev #17016
// your answers
type ParamType = string | number | bigint
type NumberToTuple<T extends number, R extends 0[] = []> = R['length'] extends T
? R
: NumberToTuple<T, [0, ...R]>
/**
* Split<12> // [1, 2]
* Split<'1'> // [1]
*/
type Split<S extends ParamType, Result extends number[] = []> = `${S}` extends `${infer F extends number}${infer R}`
? Split<R, [...Result, F]>
: Result
/**
* SingleSum<1, 2> // 3
* SingleSum<4, 8> // 12
*/
type SingleSum<T extends number, D extends number> = [...NumberToTuple<T>, ...NumberToTuple<D>]['length'] & number
/**
* GetRest<[1, 2, 3]> // [1, 2]
* GetRest<[1]> // []
*/
type GetRest<T> = T extends [...infer R, infer L extends number]
? R
: []
type Pop<T> = T extends [...infer R, infer L extends number]
? L
: 0
/**
* GetDigit<12> // 2
* GetDigit<1> // 1
*/
type GetDigit<T extends number> = `${T}` extends `${infer F extends number}${infer R extends number}`
? R
: T
/**
* GetTens<12> // 1
* GetTens<1> // 0
*/
type GetTens<T extends number> = `${T}` extends `${infer F extends number}${infer R extends number}`
? F
: 0
type ArraySum<
A extends number[] = [],
B extends number[] = [],
C extends number = 0, // 4 + 8 => 12 => 1
Result extends string = '', // 4 + 8 => 12 => 2 + Result
AL extends number = Pop<A>,
BL extends number = Pop<B>
> = A extends []
? B extends []
? C extends 0 ? Result : `${C}${Result}`
: ArraySum<[], GetRest<B>, GetTens<SingleSum<SingleSum<AL, BL>, C>>, `${GetDigit<SingleSum<SingleSum<AL, BL>, C>>}${Result}`>
: B extends []
? ArraySum<GetRest<A>, [], GetTens<SingleSum<SingleSum<AL, BL>, C>>, `${GetDigit<SingleSum<SingleSum<AL, BL>, C>>}${Result}`>
: ArraySum<GetRest<A>, GetRest<B>, GetTens<SingleSum<SingleSum<AL, BL>, C>>, `${GetDigit<SingleSum<SingleSum<AL, BL>, C>>}${Result}`>
type Sum<
A extends ParamType,
B extends ParamType,
> = ArraySum<Split<A>, Split<B>>
type MinusOne<T extends number, Result extends 0[] = NumberToTuple<T>> = Result extends [infer F, ...infer R]
? R['length']
: 0
/**
* SingleMultiply<1, 2> // 2
* SingleMultiply<4, 8> // 32
* SingleMultiply<0, 1> // 0
*/
type SingleMultiply<
T extends number,
D extends number,
C extends number = D,
Result extends unknown[] = []
> = D extends 0
? 0
: C extends 0
? Result['length'] & number
: SingleMultiply<T, D, MinusOne<C>, [
...NumberToTuple<T>,
...Result
]>
/**
* ArrayMul<[3, 2, 1], 1> // '321'
* ArrayMul<[1, 2], 2> // '24'
*/
type ArrayMul<
A extends number[],
B extends number,
C extends number = 0,
Result extends string = '',
AL extends number = Pop<A>
> = A extends []
? C extends 0 ? Result : `${C}${Result}`
: ArrayMul<GetRest<A>, B, GetTens<SingleSum<C, SingleMultiply<AL, B>>>, `${GetDigit<SingleSum<C, SingleMultiply<AL, B>>>}${Result}`>
type EachSum<T, Result extends string = ''> = T extends [infer F extends string, ...infer R]
? EachSum<R, Sum<F, Result>>
: Result
type Multiply<
A extends ParamType,
B extends ParamType,
SA extends number[] = Split<A>,
SB extends number[] = Split<B>,
Result extends string[] = [],
Default extends string = '',
SBL extends number = Pop<SB>
> = Equal<`${A}`, '0'> extends true
? '0'
: Equal<`${B}`, '0'> extends true
? '0'
: SB extends []
? EachSum<Result>
: Multiply<never, never, SA, GetRest<SB>, [ArrayMul<SA, SBL, 0, Default>, ...Result], `0${Default}`>
// 123 * 321
// 123 * 1 => 123
// 123 * 2 * 10 => 2460
// 123 * 3 * 100 => 36900
// => 123 + 2460 + 36900
Solution by humandetail #16659
// your answers
type Dictionary<
E extends any = any> =
{
'0':[],
'1':[E],
'2':[E,E],
'3':[E,E,E],
'4':[E,E,E,E],
'5':[E,E,E,E,E],
'6':[E,E,E,E,E,E],
'7':[E,E,E,E,E,E,E],
'8':[E,E,E,E,E,E,E,E],
'9':[E,E,E,E,E,E,E,E,E],
} ;
type _10<E extends any = any> = [E,E,E,E,E,E,E,E,E,E] ;
type Numerable = string | number | bigint ;
type Stringify<
N extends Numerable,
Num extends string =`${N}`> =
Num extends `${infer R}${infer U}`
? R extends keyof Dictionary<any>
? `${R}${Stringify<U>}`
: `${Stringify<U>}`
: '' ;
type ReverseString<
S extends string> =
S extends `${infer R}${infer U}`
? `${ReverseString<U>}${R}`
: '' ;
type Trim0<
S extends string> =
S extends `${0}${infer R}`
? R extends ''
? '0'
: Trim0<R>
: S ;
type KeyByValue<
T extends object,
V extends any,
Keys extends keyof T = keyof T> =
Keys extends Keys
? T[Keys] extends V
? Keys
: never
: never ;
type ReverseStringSum<
A extends string,
B extends string,
Buff extends readonly any[]=[]> =
A extends `${infer R extends keyof Dictionary}${infer U extends string}`
? B extends `${infer V extends keyof Dictionary}${infer W extends string}`
? [...Dictionary[R],...Dictionary[V],...Buff] extends [..._10,...infer S]
? `${KeyByValue<Dictionary,S>}${ReverseStringSum<U,W,[any]>}`
:`${KeyByValue<Dictionary,[...Dictionary[R],...Dictionary[V],...Buff]>}${ReverseStringSum<U,W>}`
: [...Dictionary[R],...Buff] extends [..._10,...infer S]
? `${KeyByValue<Dictionary,S>}${ReverseStringSum<U,'',[any]>}`
: `${KeyByValue<Dictionary,[...Dictionary[R],...Buff]>}${ReverseStringSum<U,''>}`
: B extends `${infer V extends keyof Dictionary}${infer W extends string}`
? [...Dictionary[V],...Buff] extends [..._10,...infer S]
? `${KeyByValue<Dictionary,S>}${ReverseStringSum<'',W,[any]>}`
: `${KeyByValue<Dictionary,[...Dictionary[V],...Buff]>}${ReverseStringSum<'',W>}`
: Buff extends [] ? '' : `${KeyByValue<Dictionary,[...Buff]>}` ;
type Sum<
A extends Numerable,
B extends Numerable> =
ReverseString<ReverseStringSum<ReverseString<Stringify<A>>,ReverseString<Stringify<B>>>> ;
type OneDigitMultiply<
A extends Numerable,
B extends keyof Dictionary,
T extends readonly any[]=[],
Total extends Numerable = '0' > =
B extends `${T['length']}`
? Total
: OneDigitMultiply<A,B,[...T,any],Sum<Total,A>> ;
type ReverseMultiply<
A extends Numerable,
B extends Numerable > =
`${B}` extends `${infer R extends keyof Dictionary}${infer U extends string}`
? Sum<OneDigitMultiply<A,R>,`${ReverseMultiply<A,U>}0`>
: '' ;
type Multiply<
A extends Numerable,
B extends Numerable > =
Trim0<ReverseMultiply<A,ReverseString<Stringify<B>>>> ;
Solution by justBadProgrammer #16251
/* utils */
type Get<T, K> = K extends keyof T ? T[K] : never;
type AsStr<T> = T extends string ? T : never;
type Reverse<S> = S extends `${infer First}${infer Rest}`
? `${Reverse<Rest>}${First}`
: '';
type Head<S> = S extends `${infer First}${string}` ? First : never;
type Tail<S> = S extends `${string}${infer Rest}` ? Rest : never;
type Replace<S, C extends string> = S extends `${string}${infer Rest}`
? `${C}${Replace<Rest, C>}`
: '';
type Rotate<S> = `${Tail<S>}${Head<S>}`;
type Zip<From, To> = From extends `${infer First}${infer Rest}`
? Record<First, Head<To>> & Zip<Rest, Tail<To>>
: {};
/* digits */
type Digits = '0123456789';
type Zero = Head<Digits>;
type One = Head<Tail<Digits>>;
/* helpers */
type GenerateAdd<
To,
Current = Digits,
> = Current extends `${infer First}${infer Rest}`
? Record<First, Zip<Digits, To>> & GenerateAdd<Rotate<To>, Rest>
: {};
type InnerAdd = GenerateAdd<Digits>;
type Add<A, B> = AsStr<Get<Get<InnerAdd, A>, B>>;
type GenerateCarry<
To,
Current = Digits,
> = Current extends `${infer First}${infer Rest}`
? Record<First, Zip<Digits, To>> & GenerateCarry<`${Tail<To>}${One}`, Rest>
: {};
type CarryWithZero = GenerateCarry<Replace<Digits, Zero>>;
type CarryWithOne = GenerateCarry<`${Tail<Replace<Digits, Zero>>}${One}`>;
type Carry<A, B, C> = C extends Zero
? AsStr<Get<Get<CarryWithZero, A>, B>>
: AsStr<Get<Get<CarryWithOne, A>, B>>;
/* sum main */
// type Sum<
// A extends string | number | bigint,
// B extends string | number | bigint,
// > = Reverse<InnerSum<Reverse<`${A}`>, Reverse<`${B}`>>>;
type InnerSum<
A extends string,
B extends string,
C extends string = Zero,
> = A extends `${infer FirstA}${infer RestA}`
? B extends `${infer FirstB}${infer RestB}`
? `${Add<Add<FirstA, FirstB>, C>}${InnerSum<
RestA,
RestB,
Carry<FirstA, FirstB, C>
>}`
: InnerSum<A, C>
: B extends ''
? C extends Zero
? ''
: C
: InnerSum<B, C>;
/* multiply utils */
type ZipArr<From, ToArr> = ToArr extends [infer First, ...infer Rest]
? Record<Head<From>, First> & ZipArr<Tail<From>, Rest>
: {};
type ToArr<S> = S extends `${infer First}${infer Rest}`
? [First, ...ToArr<Rest>]
: [];
/* multiply helpers */
type DigitArr = ToArr<Digits>;
type AddDigitArr<Arr> = {
[Key in keyof Arr]: InnerSum<AsStr<Arr[Key]>, Get<DigitArr, Key>>;
};
type GenerateMulTable<
ToArr,
Current = Digits,
> = Current extends `${infer First}${infer Rest}`
? Record<First, ZipArr<Digits, ToArr>> &
GenerateMulTable<AddDigitArr<ToArr>, Rest>
: {};
type InnerMulTable = GenerateMulTable<ToArr<Replace<Digits, Zero>>>;
type MulTable<A, B> = AsStr<Get<Get<InnerMulTable, A>, B>>;
type TrimEndZeros<S> = S extends `${infer T}0` ? TrimEndZeros<T> : S;
/* main */
type Multiply<
A extends string | number | bigint,
B extends string | number | bigint,
> = Reverse<InnerMultiply<Reverse<`${A}`>, Reverse<`${B}`>>>;
type InnerMultiply<
A extends string,
B extends string,
> = A extends `${infer FirstA}${infer RestA}`
? B extends `${infer FirstB}${infer RestB}`
? InnerSum<
MulTable<FirstA, FirstB>,
InnerSum<
TrimEndZeros<`${Zero}${InnerMultiply<RestA, FirstB>}`>,
InnerSum<
TrimEndZeros<`${Zero}${InnerMultiply<RestB, FirstA>}`>,
TrimEndZeros<`${Zero}${Zero}${InnerMultiply<RestB, RestA>}`>
>
>
>
: ''
: '';
Solution by ryo-mf-fjt #11817
This is a nice small solution that works for multiplication of not too big numbers e.g. 80 x 120
type Multiply<
A extends number | string | bigint,
B extends number | string | bigint,
AArr extends 0[] = [],
BArr extends 0[] = [],
Result extends 0[] = [],
>
= `${A}` extends `${AArr['length']}`
? `${B}` extends `${BArr['length']}`
? `${Result['length']}`
: Multiply<A, B, AArr, [...BArr, 0], [...Result, ...AArr]>
: Multiply<A, B, [...AArr, 0]>
And this is the full solution that passes all test cases
The idea is to represent the multiplication of a big number as a sum of not that many numbers. E. g. 123 x 45 could be represented as 15 + 120 + 100 + 800 + 500 + 4000, or
(3 * 5) + (3 * 4 * 10) + (2 * 5 * 10) + (2 * 4 * 100) + (1 * 5 * 100) * (1 * 4 * 1000). Multiplication of digits can be done with tuples concatenation or with a table of predefined results while multiplication on 10 ^ n is just adding trailing zeros to the result. The n in that 10 ^ n is the sum of positions of multiplied digits e.g. for 2 * 4 * 100, 2 is the second digit in 123 and 4 is the second digit in 45
A decision has been made to represent numbers as Tuples of digits e.g. 23 is [2, 3]. It allows to easily pick the last digit and compare it to tuple length without additional conversions
So Multiply would convert A and B into Tuples and pass them to MultiplyToSum that would transform them into a Tuple of numbers with all possible multiplications of digits of A and B multiplied by 10 ^ n where n depends on the positions of specific digits in A and B
Then the result tuple of numbers would be summed with Sum
Then trailing zeros from the sum would be trimmed with TrimZeros e.g. [0, 5, 5, 3, 5] would become [5, 5, 3, 5]
And finally, the tuple of digits would be converted to string e.g. [5, 5, 3, 5] would become 5535
// Multiplication part.
type Multiply<
A extends number | string | bigint, B extends number | string | bigint,
ATuple extends number[] = ToTuple<A>, BTuple extends number[] = ToTuple<B>,
> = ToString<TrimZeros<Sum<MultiplyToSum<ATuple, BTuple>>>>;
type MultiplyToSum<
A extends number[],
B extends number[],
Result extends number[][] = [],
FullB extends number[] = B,
ABTrailingZeros extends 0[] = [],
ATrailingZeros extends 0[] = ABTrailingZeros
> =
A extends [...infer AS extends number[], infer AL extends number]
? B extends [...infer BS extends number[], infer BL extends number]
? MultiplyToSum<A, BS, [...Result, [...MultTable[AL][BL], ...ABTrailingZeros]], FullB, [...ABTrailingZeros, 0], ATrailingZeros>
: MultiplyToSum<AS, FullB, Result, FullB, [...ATrailingZeros, 0]>
: Result;
// Convertion helpers
type ToString<T extends number[]> = T extends [infer F extends number, ...infer R extends number[]] ? `${F}${ToString<R>}` : '';
type TrimZeros<T extends number[]> = T extends [0, infer F extends number, ...infer R extends number[]] ? TrimZeros<[F, ...R]> : T
type StN = {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8, '9': 9}
type ToTuple<N extends number | string | bigint> = `${N}` extends `${infer H}${infer T}` ? [StN[H & keyof StN], ...ToTuple<T>] : [];
// Sum part
type Sum<A extends number[][], TS extends number[] = [], N extends number[][] = []>
= A extends [[...infer NumP extends number[], infer NumLD extends number], ...infer RNum extends number[][]]
? Sum<RNum, [...TS, NumLD], NumP extends [] ? N : [...N, NumP]>
: N extends []
? SumDigits<TS>
: SumDigits<TS> extends [...infer SumP extends number[], infer SumD extends number]
? [...Sum<SumP extends [] ? N : [...N, SumP]>, SumD]
: never;
type SumDigits<A extends number[], R extends number[] = []> =
A extends [infer H extends number, ...infer T extends number[]]
? SumDigits<T, [...R, ...TupleOfLength[H]]>
: ToTuple<R['length']>
type TupleOfLength = [
[],
[0],
[0, 0],
[0, 0, 0],
[0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
]
type MultTable = [
[[0], [0], [0], [0], [0], [0], [0], [0], [0], [0]],
[[0], [1], [2], [3], [4], [5], [6], [7], [8], [9]],
[[0], [2], [4], [6], [8], [1, 0], [1, 2], [1, 4], [1, 6], [1, 8]],
[[0], [3], [6], [9], [1, 2], [1, 5], [1, 8], [2, 1], [2, 4], [2, 7]],
[[0], [4], [8], [1, 2], [1, 6], [2, 0], [2, 4], [2, 8], [3, 2], [3, 6]],
[[0], [5], [1, 0], [1, 5], [2, 0], [2, 5], [3, 0], [3, 5], [4, 0], [4, 5]],
[[0], [6], [1, 2], [1, 8], [2, 4], [3, 0], [3, 6], [4, 2], [4, 8], [5, 4]],
[[0], [7], [1, 4], [2, 1], [2, 8], [3, 5], [4, 2], [4, 9], [5, 6], [6, 3]],
[[0], [8], [1, 6], [2, 4], [3, 2], [4, 0], [4, 8], [5, 6], [6, 4], [7, 2]],
[[0], [9], [1, 8], [2, 7], [3, 6], [4, 5], [5, 4], [6, 3], [7, 2], [8, 1]],
];
Solution by Alexsey #11580
type Multiply<A extends string | number | bigint, B extends string | number | bigint, R extends string = `0`>
= `${A}` extends '0' ? '0'
: `${B}` extends `${infer L}0` ? Multiply<`${A}0`, L, R>
: `${B}` extends `${infer L}1` ? Multiply<`${A}0`, L, Sum<R, A>>
: `${B}` extends `${infer L}2` ? Multiply<`${A}0`, L, Sum<R, X2<A>>>
: `${B}` extends `${infer L}3` ? Multiply<`${A}0`, L, Sum<R, X3<A>>>
: `${B}` extends `${infer L}4` ? Multiply<`${A}0`, L, Sum<R, X4<A>>>
: `${B}` extends `${infer L}5` ? Multiply<`${A}0`, L, Sum<R, X5<A>>>
: `${B}` extends `${infer L}6` ? Multiply<`${A}0`, L, Sum<R, X6<A>>>
: `${B}` extends `${infer L}7` ? Multiply<`${A}0`, L, Sum<R, X7<A>>>
: `${B}` extends `${infer L}8` ? Multiply<`${A}0`, L, Sum<R, X8<A>>>
: `${B}` extends `${infer L}9` ? Multiply<`${A}0`, L, Sum<R, X9<A>>>
: R
type X2<A extends string | number | bigint> = Sum<A, A>
type X3<A extends string | number | bigint> = Sum<X2<A>, A>
type X4<A extends string | number | bigint> = X2<X2<A>>
type X5<A extends string | number | bigint>
= `${A}` extends `${infer L}0` ? `${X5<L>}0`
: `${A}` extends `${infer L}1` ? `${X5<L>}5`
: `${A}` extends `${infer L}2` ? `${Sum<X5<L>, 1>}0`
: `${A}` extends `${infer L}3` ? `${Sum<X5<L>, 1>}5`
: `${A}` extends `${infer L}4` ? `${Sum<X5<L>, 2>}0`
: `${A}` extends `${infer L}5` ? `${Sum<X5<L>, 2>}5`
: `${A}` extends `${infer L}6` ? `${Sum<X5<L>, 3>}0`
: `${A}` extends `${infer L}7` ? `${Sum<X5<L>, 3>}5`
: `${A}` extends `${infer L}8` ? `${Sum<X5<L>, 4>}0`
: `${A}` extends `${infer L}9` ? `${Sum<X5<L>, 4>}5`
: ''
type X6<A extends string | number | bigint> = Sum<X5<A>, A>
type X7<A extends string | number | bigint> = Sum<X5<A>, X2<A>>
type X8<A extends string | number | bigint> = X2<X4<A>>
type X9<A extends string | number | bigint> = Sum<X5<A>, X4<A>>
type Sum<A extends string | number | bigint, B extends string | number | bigint, P extends string = `${A}+${B}`>
= P extends Match<'00', infer C, infer D> ? `${Sum<C, D>}0`
: P extends Match<'01', infer C, infer D> ? `${Sum<C, D>}1`
: P extends Match<'02'|'11', infer C, infer D> ? `${Sum<C, D>}2`
: P extends Match<'03'|'12', infer C, infer D> ? `${Sum<C, D>}3`
: P extends Match<'04'|'13'|'22', infer C, infer D> ? `${Sum<C, D>}4`
: P extends Match<'05'|'14'|'23', infer C, infer D> ? `${Sum<C, D>}5`
: P extends Match<'06'|'15'|'24'|'33', infer C, infer D> ? `${Sum<C, D>}6`
: P extends Match<'07'|'16'|'25'|'34', infer C, infer D> ? `${Sum<C, D>}7`
: P extends Match<'08'|'17'|'26'|'35'|'44', infer C, infer D> ? `${Sum<C, D>}8`
: P extends Match<'09'|'18'|'27'|'36'|'45', infer C, infer D> ? `${Sum<C, D>}9`
: P extends Match<'19'|'28'|'37'|'46'|'55', infer C, infer D> ? `${Sum<1, Sum<C, D>>}0`
: P extends Match<'29'|'38'|'47'|'56', infer C, infer D> ? `${Sum<1, Sum<C, D>>}1`
: P extends Match<'39'|'48'|'57'|'66', infer C, infer D> ? `${Sum<1, Sum<C, D>>}2`
: P extends Match<'49'|'58'|'67', infer C, infer D> ? `${Sum<1, Sum<C, D>>}3`
: P extends Match<'59'|'68'|'77', infer C, infer D> ? `${Sum<1, Sum<C, D>>}4`
: P extends Match<'69'|'78', infer C, infer D> ? `${Sum<1, Sum<C, D>>}5`
: P extends Match<'79'|'88', infer C, infer D> ? `${Sum<1, Sum<C, D>>}6`
: P extends Match<'89', infer C, infer D> ? `${Sum<1, Sum<C, D>>}7`
: P extends Match<'99', infer C, infer D> ? `${Sum<1, Sum<C, D>>}8`
: `${A}${B}`
type Match<P extends string, C extends string, D extends string> = P extends `${infer X}${infer Y}` ? `${C}${X}+${D}${Y}` | `${C}${Y}+${D}${X}` : never
Solution by teamchong #11426
type ArrayL<L extends string, R extends unknown[] = []> =
`${R['length']}` extends L
? R
: ArrayL<L , [...R, unknown]>
type S2Arr<S extends string, R extends string[] = []> =
S extends `${infer X}${infer Y}`
? S2Arr<Y, [...R, X]>
: R
type BitAdd<X extends string, Y extends string, Flag extends string> =
`${[...ArrayL<X>, ...ArrayL<Y>, ...ArrayL<Flag>]['length'] & number}` extends `${infer A}${infer A1}${infer A2}`
? [A, A1] : ['0', `${[...ArrayL<X>, ...ArrayL<Y>, ...ArrayL<Flag>]['length'] & number}`]
type StrArr<X extends string[], Y extends string> = [...X, Y]
type _Sum<X extends string[], Y extends string[], R extends string = '', Flag extends string = '0'> =
X extends StrArr<infer X1, infer X2>
? Y extends StrArr<infer Y1, infer Y2>
? _Sum<X1, Y1, `${BitAdd<X2, Y2, Flag>[1]}${R}`, BitAdd<X2, Y2, Flag>[0]>
: _Sum<X1, [], `${BitAdd<X2, '0', Flag>[1]}${R}`, BitAdd<X2, '0', Flag>[0]>
: Y extends StrArr<infer Y1, infer Y2>
? _Sum<[], Y1, `${BitAdd<'0', Y2, Flag>[1]}${R}`, BitAdd<'0', Y2, Flag>[0]>
: Flag extends '1'
? `1${R}`
: R
type Sum<A extends string | number | bigint, B extends string | number | bigint> = _Sum<S2Arr<`${A}`>, S2Arr<`${B}`>>
type ArraySum<Arr extends string[], R extends string = '0'> =
Arr extends StrArr<infer X, infer Y>
? ArraySum<X, Sum<R, Y>>
: R
type TimeLess10<Num extends string, T extends string, Iter extends unknown[] = [], Res extends string = '0'> =
`${Iter['length']}` extends T
? Res
: TimeLess10<Num, T, [...Iter, unknown], Sum<Num, Res>>
type _Multiply<X extends string, Y extends string[], R extends string[] = [], Flag extends string = ''> =
X extends '0'
? '0'
: Y extends StrArr<infer Y1, infer Y2>
? _Multiply<X, Y1, [...R, TimeLess10<`${X}${Flag}`, Y2>], `${0}${Flag}`>
: ArraySum<R>
type Multiply<A extends string | number | bigint, B extends string | number | bigint> = _Multiply<`${A}`, S2Arr<`${B}`>>
Solution by fangyang921017 #10339
// from type Sum
type Computable = string | number | bigint
type NumberToTuple<T extends Computable, R extends any[] = []> = `${T}` extends `${number}`
? `${T}` extends `${R['length']}`
? R
: NumberToTuple<T, [...R, 1]>
: []
type Remaind10<T extends any[]> = T extends [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...infer R]
? {
number: R['length']
count: '1'
}
: {
number: T['length']
count: ''
}
type Reverse<T extends string> = T extends `${infer L}${infer R}` ? `${Reverse<R>}${L}` : ''
type HalfAdd<A extends Computable, B extends Computable, count extends string = ''> =
Remaind10<[...NumberToTuple<A>, ...NumberToTuple<B>, ...count extends '1' ? [1] : []]>
type StrAdd<A extends string, B extends string, count extends string = '0'> =
A extends `${infer AL}${infer AR}`
? B extends `${infer BL}${infer BR}`
? `${HalfAdd<AL, BL, count>['number'] & number}${StrAdd<AR, BR, HalfAdd<AL, BL, count>['count']>}`
: `${HalfAdd<AL, count>['number'] & number}${StrAdd<AR, '0', HalfAdd<AL, count>['count']>}`
: B extends `${infer BL}${infer BR}`
? `${HalfAdd<BL, count>['number'] & number}${StrAdd<'', BR, HalfAdd<BL, count>['count']>}`
: count
type Sum<A extends Computable, B extends Computable> = Reverse<StrAdd<Reverse<`${A}`>, Reverse<`${B}`>>>
// Sum end
type SimpleMutil<A extends string, B extends any[]> = B extends [infer _, ...infer R]
? Sum<A, SimpleMutil<A, R>>
: '0'
type Multi<A extends Computable, B extends Computable> = SimpleMutil<`${A}`, NumberToTuple<B>>
type Multiply<A extends Computable, B extends Computable, Res extends string = ''> =
`${B}` extends `${infer L}${infer R}`
? Multiply<A, R, Sum<`${Res}${Res extends '' ? '' : 0}`, Multi<A, L>>>
: TrimLeft<Res, '0'> extends '' ? '0' :TrimLeft<Res, '0'>
type TrimLeft<L extends string, R extends string> = L extends `${R}${infer S}` ? TrimLeft<S, R> : L
Solution by ch3cknull #8050
/**
* 4->[0,0,0,0]
*/
type numToTupl<
T extends string,
R extends any[] = []
> = `${R["length"]}` extends T ? R : numToTupl<T, [...R, 0]>;
type TenRes<base extends string, N extends string> = `${base}${N}`;
/**
* 9 + 1 = 10
* 8 + 8 = 16
*/
type SumTen<L extends string, R extends string> = [
...numToTupl<L>,
...numToTupl<R>
]["length"] extends NumberInferType<infer SumRes>
? `${SumRes}`
: never;
/**
* 个位数 * 个位数
* 2 * 9
*/
type MulTen<
L extends string,
R extends string,
Res extends string = "0"
> = numToTupl<L> extends [infer _, ...infer LN]
? MulTen<`${LN["length"]}`, R, SumTen<Res, R>>
: Res;
/**
* n位数 * 个位数
* 123 * 4
* 3 * 2
* 121021 * 5
*/
type Mul_N_AND_ONE<
L extends string,
R extends string,
Res extends string = "0"
> = L extends `${infer A}${infer B}`
? Mul_N_AND_ONE<B, R, Sum<`${Res}0`, MulTen<A, R>>>
: Res;
type NumberInferType<T extends number> = T;
type StringArrInferType<T extends string[], S extends string> = [...T, S];
type StringInferType<L extends string, R extends string> = `${L}${R}`;
/**
* "1234"->["1","2","3","4"]
*/
type ToStringArr<T extends string | number | bigint> =
`${T}` extends StringInferType<infer L, infer R>
? [L, ...ToStringArr<R>]
: [];
/**
* ["1","2","3","4"]->"1234"
* ["0","2"]->"02"
*/
type StringArrToString<T extends string[]> = T extends StringArrInferType<
infer L,
infer R
>
? `${StringArrToString<L>}${R}`
: "";
/**
* 012 -> 12
* 0 -> 0
* 101 -> 101
*/
type RemoveZero<T> = T extends `0${infer R}`
? RemoveZero<R>
: T extends ""
? "0"
: T;
/**
* ['1','2'] ['1'] long -> ['1','2']
* ['1','2'] ['1'] short -> ['1']
*/
type findArr<
T extends string[],
R extends string[],
type extends "long" | "short"
> = numToTupl<`${T["length"]}`> extends [
...numToTupl<`${R["length"]}`>,
...infer _
]
? type extends "long"
? T
: R
: type extends "long"
? R
: T;
type _Sum<
L extends string[],
R extends string[],
base extends string = "0",
Res extends string[] = []
> = L extends StringArrInferType<infer LL, infer LC>
? R extends StringArrInferType<infer RR, infer RC>
? SumTen<SumTen<LC, RC>, base> extends TenRes<infer A, infer B>
? B extends ""
? _Sum<LL, RR, "0", [A, ...Res]>
: _Sum<LL, RR, A, [B, ...Res]>
: never
: SumTen<SumTen<LC, "0">, base> extends TenRes<infer A, infer B>
? B extends ""
? _Sum<LL, [], "0", [A, ...Res]>
: _Sum<LL, [], A, [B, ...Res]>
: never
: base extends "1"
? ["1", ...Res]
: Res;
type Sum<
A extends string | number | bigint,
B extends string | number | bigint
> = RemoveZero<
StringArrToString<
_Sum<
findArr<ToStringArr<A>, ToStringArr<B>, "long">,
findArr<ToStringArr<A>, ToStringArr<B>, "short">
>
>
>;
type _Multiply<
L extends string,
R extends string,
Res extends string = "0"
> = R extends `${infer A}${infer B}`
? _Multiply<L, B, Sum<`${Res}0`, Mul_N_AND_ONE<L, A>>>
: Res;
type Multiply<
L extends string | number | bigint,
R extends string | number | bigint
> = _Multiply<`${L}`, `${R}`>;
Solution by baian1 #6059
// your answers
type Reverse<A> =
`${A}` extends `${infer AH}${infer AT}`
? `${Reverse<AT>}${AH}` : A
type Digs = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
type DigsNext<I = Digs, R = {}> =
I extends [infer Head, infer Next, ...infer Tail]
? DigsNext<[Next, ...Tail], R & Record<Head, Next>>
: {[K in keyof R]: R[K]}
type DigsPrev = {[K in keyof DigsNext as DigsNext[K]]: K}
type AddOne<A> =
A extends `${infer AH}${infer AT}`
? AH extends '9' ? `0${AddOne<AT>}` : `${DigsNext[AH]}${AT}`
: `1`
type SubOne<A> =
A extends `${infer AH}${infer AT}`
? AH extends '0' ? `9${SubOne<AT>}` : `${DigsPrev[AH]}${AT}`
: never
type Add<A, B> =
A extends `${infer AH}${infer AT}` ?
B extends `${infer BH}${infer BT}`
? BH extends '0' ? `${AH}${Add<AT, BT>}` : Add<AddOne<A>, SubOne<B>>
: A : B
type Mul<A, B, R = '0'> =
A extends '0' ? R :
B extends '0' ? R :
A extends `${infer AH}${infer AT}`
? AH extends '0' ? Mul<AT, `0${B}`, R> : Mul<SubOne<A>, B, Add<R, B>>
: R
type Multiply<A extends string | number | bigint, B extends string | number | bigint> =
Reverse<Mul<Reverse<A>, Reverse<B>>>
Solution by Sobes76rus #5814
// Makes a tuple of a given size
type Tuple<S extends string, U = never, A extends U[] = []> =
`${A['length']}` extends S ? A : Tuple<S, U, [...A, U]>
// Flattens a 2D array into a plain array (e.g. [[], [1, 1], [1]] => [1,1,1])
type Flatten<T extends U[][], U = never, A extends U[] = []> =
T extends [infer F, ...infer R] ? Flatten<R, U, [...A, ...F]> : A
// Gets rid of starting C characters in S string (e.g. '00012' => '12')
type TrimLeft<S extends string, C extends string> =
S extends `${C}${infer R}` ? TrimLeft<R, C> : S
// Converts a string to a reverse array of digits (e.g. 103 => ['3', '0', '1'])
type ToDigits<T extends string, A extends string[] = []> =
`${T}` extends `${infer F}${infer R}` ? ToDigits<R, [F, ...A]> : A
// Converts an inverted array of digits to a stringified number
type ToString<T extends string[], S extends string = ''> =
T extends [...infer R, infer L] ? ToString<R, `${S}${L}`> :
S extends '' ? '0' : S
// Summarizes 2 numbers, returns an inverted array of digits
type SumNumbers<A extends string, B extends string> =
ToDigits<`${[...Tuple<A>, ...Tuple<B>]['length']}`>
// Multiplies 2 numbers, returns an inverted array of digits
type MultiplyNumbers<A extends string, B extends string> =
ToDigits<`${[...Flatten<Tuple<A, Tuple<B>>>]['length']}`>
type SumDigits<A extends string[], B extends string[]> =
A extends [infer Fa, ...infer Ra] ?
B extends [infer Fb, ...infer Rb] ?
// Take both digits on the same position, sum them
SumNumbers<Fa, Fb> extends [infer Fs, ...infer Rs] ?
// Output the first digit, carry the rest to the next iteration
[Fs, ...SumDigits<Rs, SumDigits<Ra, Rb>>] : []
: A
: B extends [any, ...any[]] ?
B : []
type MultiplyNumberByDigits<A extends string, B extends string[]> =
B extends [infer Fb, ...infer Rb] ?
MultiplyNumbers<A, Fb> extends [infer Fs, ...infer Rs] ?
[Fs, ...SumDigits<Rs, MultiplyNumberByDigits<A, Rb>>] : []
: []
type MultiplyDigits<A extends string[], B extends string[]> =
A extends [infer Fa, ...infer Ra] ?
MultiplyNumberByDigits<Fa, B> extends [infer Fs, ...infer Rs] ?
[Fs, ...SumDigits<Rs, MultiplyDigits<Ra, B>] :
[]
: []
type Multiply<A extends string | number | bigint, B extends string | number | bigint> =
ToString<MultiplyDigits<
ToDigits<TrimLeft<`${A}`, '0'>>,
ToDigits<TrimLeft<`${B}`, '0'>>
>>
Solution by ssipak #4658
type N1 = [any];
type N2 = [any, any];
type N3 = [any, any, any];
type N4 = [any, any, any, any];
type N5 = [any, any, any, any, any];
type N6 = [any, any, any, any, any, any];
type N7 = [any, any, any, any, any, any, any];
type N8 = [any, any, any, any, any, any, any, any];
type N9 = [any, any, any, any, any, any, any, any, any];
type NumToTuple<N, L = N extends string | number ? `${N}` : ''> =
L extends `${N1['length']}`
? N1 : L extends `${N2['length']}`
? N2 : L extends `${N3['length']}`
? N3 : L extends `${N4['length']}`
? N4 : L extends `${N5['length']}`
? N5 : L extends `${N6['length']}`
? N6 : L extends `${N7['length']}`
? N7 : L extends `${N8['length']}`
? N8 : L extends `${N9['length']}`
? N9 : [];
type ToTuple<T extends bigint | string | number, S = `${T}`> = S extends `${infer F}${infer O}` ? [F, ...ToTuple<O>] : [];
type TuplePop<T extends any[]> = T extends [...any, infer O] ? O : '';
type TupleTail<T extends any[]> = T extends [...infer F, any] ? F : T;
type TensDigitSum<A, B, C = 0, R = [...NumToTuple<A>, ...NumToTuple<B>, ...NumToTuple<C>]['length']> = R extends number ? R : 0;
type SumToCarry<A, B, C, R extends string[] = ToTuple<TensDigitSum<A, B, C>>> = R extends [infer F, infer O] ? [F, O] : ['', R[0]];
type TupleToString<T extends any[]> = T extends [string, ...infer O] ? `${T[0]}${TupleToString<O>}` : '';
type Num = string | number | bigint;
type TupleSumTuple<A extends any[], B extends any[], R extends any[] = [], C extends any = ''> = A extends []
? (C extends '' ? [...B, ...R] : TupleSumTuple<B, [C], R>) : B extends []
? (C extends '' ? [...A, ...R] : TupleSumTuple<A, [C], R>) : SumToCarry<TuplePop<A>, TuplePop<B>, C> extends [infer C1, infer T]
? TupleSumTuple<TupleTail<A>, TupleTail<B>, [T, ...R], C1> : R;
type Cumulative<A extends any[], N extends Num, L extends any[] = [any], R extends any[] = A> = `${N}` extends `${L['length']}` ? R : Cumulative<A, N, [...L, any], TupleSumTuple<R, A>>;
type MultiplyByTuple<A extends any[], B extends any[], C extends any[] = [], R extends any[] = []> = B extends [] ? R : MultiplyByTuple<A, TupleTail<B>, [...C, '0'], TupleSumTuple<R, [...Cumulative<A, TuplePop<B>>, ...C]>>
type Multiply<A extends string | number | bigint, B extends string | number | bigint> = `${A}` extends '0'
? '0' : `${B}` extends '0'
? '0' : TupleToString<MultiplyByTuple<ToTuple<A>, ToTuple<B>>>;
Solution by venusliang #4535
ts
type arrElem = any
type arr = arrElem[];
type OpType = string | number | bigint
type Cast<T, U> = T extends U ? T : U;
type DeleteFirstElement<T extends arr> = T extends [arrElem, ...infer R] ? R : never
type ToArr<T extends string, R extends arr = []> = `${R['length']}` extends T
? R
: ToArr<T, [...R, arrElem]>
type ToArrNumber<T extends OpType, R extends arr = []> =
`${T}` extends `${infer FirstNumber}${infer RestNumbers}`
? ToArrNumber<RestNumbers, [ToArr<FirstNumber>, ...R]>
: R
type ToNumber<T extends arr, S extends string = ''> = T extends [infer FirstNumber, ...infer RestNumbers]
? ToNumber<RestNumbers, `${ FirstNumber extends arr ? FirstNumber['length'] : never }${S}`>
: S
type CombineArrNumber<
A1 extends arr, A2 extends arr, R extends arr = []
> = A1['length'] extends 0
? [...R, ...A2]
: A2['length'] extends 0
? [...R, ...A1]
: CombineArrNumber<
DeleteFirstElement<A1>,
DeleteFirstElement<A2>,
[...R, [...A1[0], ...A2[0]] ]
>
type GetRest<T extends arr, R extends arr = [[], []]> =
(R[1])['length'] extends 10
? [[arrElem], T]
: T['length'] extends 0
? [[], R[1]]
: GetRest< DeleteFirstElement<T>, [[], [arrElem, ...(R[1]) ]] >
type NormalizeArrNumber<T extends arr, R extends arr = []> = T['length'] extends 0
? R
: T['length'] extends 1
? [...R, GetRest<T[0]>[1], ...(GetRest<T[0]>[0]['length'] extends 1 ? [[arrElem]] : [])]
: NormalizeArrNumber<
[[ ...(T[1]), ...GetRest<T[0]>[0] ], ...DeleteFirstElement<DeleteFirstElement<T>>],
[...R, GetRest<T[0]>[1]]
>
type Sum<S1 extends OpType, S2 extends OpType> =
ToNumber<
Cast<NormalizeArrNumber<
Cast<CombineArrNumber<
ToArrNumber<S1>,
ToArrNumber<S2>
>, arr>
>, arr>
>
type MultiplyByNumber<M1 extends OpType, M2 extends string, R extends string = `0`, I extends arr = []> = `${I['length']}` extends M2
? R
: MultiplyByNumber<M1, M2, Sum<R, M1>, [arrElem, ...I]>
type SplitAndReverse<T extends string, R extends string[] = []> = T extends `${infer First}${infer Rest}`
? SplitAndReverse<Rest, [First, ...R]>
: R
type AddZeros<T extends arr, R extends string = ''> = T['length'] extends 0 ? R : AddZeros<DeleteFirstElement<T>, `${R}0`>
type Multiply<M1 extends OpType, Q extends OpType, M2 extends string[] = SplitAndReverse<`${Q}`>, R extends string = '', I extends arr = []> =
`${M1}` extends '0'
? '0'
: M2['length'] extends 0
? R
: Multiply<M1, Q, Cast<DeleteFirstElement<M2>, string[]>, Sum< `${MultiplyByNumber<M1, M2[0]>}${AddZeros<I>}` , R>, [arrElem, ...I]>
Solution by AlexeyDuybo #4309
type Type<Value> = Compute<Value> extends infer ComputedValue
? /* ... */ // ComputedValue gets reused deep down the conditional chain
: never
// #region Sum challenge solution
// See: https://github.com/type-challenges/type-challenges/issues/3749
type NumberLike = string | number | bigint
type NumericString = `${0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9}`
// #region Rightmost string extraction helpers
type SplitRightMost<Type> = Type extends NumberLike
? `${Type}` extends `${infer Rest}${NumericString}`
? `${Type}` extends `${Rest}${infer Right}`
? [Rest, Right]
: never
: ['', '']
: never
type SplitRest = 0
type SplitRight = 1
type SplitGet<
Splitted,
Key extends SplitRest | SplitRight
> = Splitted[Key & keyof Splitted]
type SplitGetRest<Splitted> = SplitGet<Splitted, SplitRest>
type SplitGetRight<Splitted> = SplitGet<Splitted, SplitRight>
// #endregion
// #region Digit to tuple helpers
type DigitToTupleMap<V = unknown> = {
'': [],
'0': [],
'1': [V],
'2': [V, V],
'3': [V, V, V],
'4': [V, V, V, V],
'5': [V, V, V, V, V],
'6': [V, V, V, V, V, V],
'7': [V, V, V, V, V, V, V],
'8': [V, V, V, V, V, V, V, V],
'9': [V, V, V, V, V, V, V, V, V],
}
type CreateTuple<Length> = DigitToTupleMap[Length & keyof DigitToTupleMap]
// #endregion
type IsFalsy<Type> = Type extends '' | 0 | false | null | undefined
? true
: false
type SumDigits<First, Second, Third = '0'> = [
...CreateTuple<First>,
...CreateTuple<Second>,
...CreateTuple<Third>
]['length']
type Sum<
First,
Second,
CarryOver = '0',
SplitFirst = SplitRightMost<First>,
FirstRight = SplitGetRight<SplitFirst>,
FirstRest = SplitGetRest<SplitFirst>,
SplitSecond = SplitRightMost<Second>,
SecondRight = SplitGetRight<SplitSecond>,
SecondRest = SplitGetRest<SplitSecond>,
> = SplitRightMost<
SumDigits<FirstRight, SecondRight, CarryOver>
> extends [infer CurrentCarryOver, infer Current]
? IsFalsy<FirstRest> extends true
? IsFalsy<SecondRest> extends true
// FirstRest = 0, SecondRest = 0
? `${CurrentCarryOver & string}${Current & string}`
// FirstRest = 0, SecondRest = x
: `${Sum<SecondRest, CurrentCarryOver>}${Current & string}`
: IsFalsy<SecondRest> extends true
// FirstRest = x, SecondRest = 0
? `${Sum<FirstRest, CurrentCarryOver>}${Current & string}`
// FirstRest = x, SecondRest = x
: `${Sum<FirstRest, SecondRest, CurrentCarryOver>}${Current & string}`
: never
// #endregion
// #region Multiplication challenge extension
type MultiplicationTable = [
['0', '0', '0', '0', '0', '0', '0', '0', '0', '0'],
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'],
['0', '2', '4', '6', '8', '10', '12', '14', '16', '18'],
['0', '3', '6', '9', '12', '15', '18', '21', '24', '27'],
['0', '4', '8', '12', '16', '20', '24', '28', '32', '36'],
['0', '5', '10', '15', '20', '25', '30', '35', '40', '45'],
['0', '6', '12', '18', '24', '30', '36', '42', '48', '54'],
['0', '7', '14', '21', '28', '35', '42', '49', '56', '63'],
['0', '8', '16', '24', '32', '40', '48', '56', '64', '72'],
['0', '9', '18', '27', '36', '45', '54', '63', '72', '81'],
]
type MultiplyDigits<
First,
Second,
> = MultiplicationTable[
CreateTuple<`${First & NumberLike}`>['length']
][
CreateTuple<`${Second & NumberLike}`>['length']
]
type Multiply<
First,
Second,
CarryOver = '0',
SplitFirst = SplitRightMost<First>,
FirstRight = SplitGetRight<SplitFirst>,
FirstRest = SplitGetRest<SplitFirst>,
SplitSecond = SplitRightMost<Second>,
SecondRight = SplitGetRight<SplitSecond>,
SecondRest = SplitGetRest<SplitSecond>,
> = '0' extends First | Second
? CarryOver
: SplitRightMost<
MultiplyDigits<FirstRight, SecondRight>
> extends [infer CurrentCarryOver, infer Current]
? IsFalsy<FirstRest> extends true
? IsFalsy<SecondRest> extends true
// FirstRest = 0, SecondRest = 0
? Sum<
`${CurrentCarryOver & string}${Current & string}`,
CarryOver
>
// FirstRest = 0, SecondRest = x
: Sum<
Current,
`${Multiply<FirstRight, SecondRest, CurrentCarryOver & string>}0`,
CarryOver
>
: IsFalsy<SecondRest> extends true
// FirstRest = x, SecondRest = 0
? Sum<
Current,
`${Multiply<FirstRest, SecondRight, CurrentCarryOver & string>}0`,
CarryOver
>
// FirstRest = x, SecondRest = x
: Sum<
Sum<
Current,
`${Multiply<FirstRight, SecondRest, CurrentCarryOver & string>}0`
>,
`${Multiply<FirstRest, Second>}0`,
CarryOver
>
: never
// #endregion
Solution by ianbunag #3758
Based on https://github.com/type-challenges/type-challenges/issues/515.
type NumberLike = string | number | bigint;
/**
* ToString<3> = '3'.
*/
type ToString<N extends NumberLike> = `${N}`;
/**
* Split<'foo'> = ['f', 'o', 'o'].
*/
type Split<S extends string> = S extends `${infer Letter}${infer Rest}`
? [Letter, ...Split<Rest>]
: [];
/**
* SumMod10[2][3] = 5.
* SumMod10[7][4] = 1.
*/
type SumMod10 = [
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9],
[1, 2, 3, 4, 5, 6, 7, 8, 9, 0],
[2, 3, 4, 5, 6, 7, 8, 9, 0, 1],
[3, 4, 5, 6, 7, 8, 9, 0, 1, 2],
[4, 5, 6, 7, 8, 9, 0, 1, 2, 3],
[5, 6, 7, 8, 9, 0, 1, 2, 3, 4],
[6, 7, 8, 9, 0, 1, 2, 3, 4, 5],
[7, 8, 9, 0, 1, 2, 3, 4, 5, 6],
[8, 9, 0, 1, 2, 3, 4, 5, 6, 7],
[9, 0, 1, 2, 3, 4, 5, 6, 7, 8],
];
/**
* TenOfSumOfTwoDigits[2][3] = 0.
* TenOfSumOfTwoDigits[4][8] = 1.
*/
type TenOfSumOfTwoDigits = [
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 1, 1],
[0, 0, 0, 0, 0, 0, 0, 1, 1, 1],
[0, 0, 0, 0, 0, 0, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 1, 1, 1, 1, 1, 1],
[0, 0, 0, 1, 1, 1, 1, 1, 1, 1],
[0, 0, 1, 1, 1, 1, 1, 1, 1, 1],
[0, 1, 1, 1, 1, 1, 1, 1, 1, 1],
];
type Digit = ToString<SumMod10[0][number]>;
type Tuple = readonly Digit[];
/**
* Last<['2', '3']> = '3'.
*/
type Last<T extends Tuple> = T extends []
? 0
: T extends [...infer Head, infer Element]
? Element extends Digit
? Element
: '0'
: '0';
/**
* Pop<['2', '3', '4']> = ['2', '3'].
*/
type Pop<T extends Tuple> = T extends [] ? [] : T extends [...infer Head, unknown] ? Head : [];
/**
* Join<['1', '2']> = '12'.
*/
type Join<T extends Tuple> = T extends [] ? '' : `${Join<Pop<T>>}${Last<T>}`;
/**
* TenOfSum<T, A, B> = (T + A + B) > 9 ? 1 : 0.
*/
type TenOfSum<
Ten extends 0 | 1,
A extends Digit,
B extends Digit
> = TenOfSumOfTwoDigits[A][B] extends 1 ? 1 : [SumMod10[A][B], Ten] extends [9, 1] ? 1 : 0;
/**
* TuplesAreEmpty<[], []> = true.
* TuplesAreEmpty<[], ['1']> = false.
*/
type TuplesAreEmpty<A extends Tuple, B extends Tuple> = A extends []
? B extends []
? true
: false
: false;
/**
* SumOfTuple<['2', '3'], ['9']> = ['3', '2'].
*/
type SumOfTuple<
A extends Tuple,
B extends Tuple,
Ten extends 0 | 1 = 0,
Result extends Tuple = []
> = TuplesAreEmpty<A, B> extends true
? Ten extends 1
? ['1', ...Result]
: Result
: SumOfTuple<
Pop<A>,
Pop<B>,
TenOfSum<Ten, Last<A>, Last<B>>,
[ToString<SumMod10[Ten][SumMod10[Last<A>][Last<B>]]>, ...Result]
>;
type MultiplyBy2<A> = A extends Tuple ? SumOfTuple<A, A> : [];
type MultiplyBy3<A> = A extends Tuple ? SumOfTuple<A, MultiplyBy2<A>> : [];
type MultiplyBy4<A> = A extends Tuple ? MultiplyBy2<MultiplyBy2<A>> : [];
type MultiplyBy5<A> = A extends Tuple ? SumOfTuple<A, MultiplyBy4<A>> : [];
type MultiplyBy6<A> = A extends Tuple ? MultiplyBy2<MultiplyBy3<A>> : [];
type MultiplyBy7<A> = A extends Tuple ? SumOfTuple<A, MultiplyBy6<A>> : [];
type MultiplyBy8<A> = A extends Tuple ? MultiplyBy2<MultiplyBy4<A>> : [];
type MultiplyBy9<A> = A extends Tuple ? MultiplyBy3<MultiplyBy3<A>> : [];
type MultiplyBy10<A> = A extends Tuple ? MultiplyBy2<MultiplyBy5<A>> : [];
type SumOf10AandB<A extends Tuple, B extends Tuple> = SumOfTuple<MultiplyBy10<A>, B>;
type MultiplyOfTuple<
A extends Tuple,
B extends Tuple,
LastA extends Digit = Last<A>,
PopA extends Tuple = Pop<A>
> = A extends []
? ['0']
: LastA extends '0'
? MultiplyBy10<MultiplyOfTuple<PopA, B>>
: LastA extends '1'
? SumOf10AandB<MultiplyOfTuple<PopA, B>, B>
: LastA extends '2'
? SumOf10AandB<MultiplyOfTuple<PopA, B>, MultiplyBy2<B>>
: LastA extends '3'
? SumOf10AandB<MultiplyOfTuple<PopA, B>, MultiplyBy3<B>>
: LastA extends '4'
? SumOf10AandB<MultiplyOfTuple<PopA, B>, MultiplyBy4<B>>
: LastA extends '5'
? SumOf10AandB<MultiplyOfTuple<PopA, B>, MultiplyBy5<B>>
: LastA extends '6'
? SumOf10AandB<MultiplyOfTuple<PopA, B>, MultiplyBy6<B>>
: LastA extends '7'
? SumOf10AandB<MultiplyOfTuple<PopA, B>, MultiplyBy7<B>>
: LastA extends '8'
? SumOf10AandB<MultiplyOfTuple<PopA, B>, MultiplyBy8<B>>
: LastA extends '9'
? SumOf10AandB<MultiplyOfTuple<PopA, B>, MultiplyBy9<B>>
: [];
/**
* Multiply<2, 3> = '6'.
*/
type Multiply<A extends NumberLike, B extends NumberLike> = Join<
MultiplyOfTuple<Split<ToString<A>>, Split<ToString<B>>>
>;
Solution by uid11 #840
// It is all about length of tuples
// Declare unique length filler to mimic numbers by length of arrays
type DeclareUniqueSymbol = { readonly 0: unique symbol }
type LF = DeclareUniqueSymbol[0];
// Programmatically mapping numbers from 0 to 9 to arrays of matching length
type CreateNumbersLikeMap0_9<
Arr extends any[] = []
> = `${Arr['length']}` extends `${any}${infer R}`
? R extends ''
? [Arr, ...CreateNumbersLikeMap0_9<[...Arr, LF]>]
: []
: never;
// Create the map
type NumbersLikeMap0_9 = CreateNumbersLikeMap0_9;
// Type of single digits in string
type DigitString = keyof NumbersLikeMap0_9 & `${number}`;
type Key0_1 = '0' | '1';
type DigitLike = LF[];
// NumberLike keep DigitsLike in reverse order
type NumberLike = DigitLike[];
type CarryingDigitLike = [] | [LF];
type PairOfNumbersLike = [NumberLike, NumberLike];
type PairsOfDigitsAndCaryingDigitsLikeArray = [DigitLike, CarryingDigitLike][];
type DigitLikeGuard<X extends DigitLike> = X;
type NumberLikeGuard<X extends NumberLike> = X;
type PairOfNumbersLikeGuard<X extends PairOfNumbersLike> = X;
type PairsOfDigitsAndCaryingDigitsLikeArrayGuard<
X extends PairsOfDigitsAndCaryingDigitsLikeArray
> = X;
// Implementation of sum of single digits converted into pair of DigitsLike and CaryingDigitsLike
type SumSingleDigits<
A extends DigitLike,
B extends DigitLike,
CD extends CarryingDigitLike
> = [...A, ...B, ...CD] extends infer Result
? Result extends [...NumbersLikeMap0_9[9], any, ...infer Over]
? [Over, [LF]]
: [Result, []]
: never;
// Having array of pairs of DigitsLike and CaryingDigitsLike we want to
// extract only given place members into separate array one of the following:
// DigitsLike array and CaryingDigitsLike array that are essentially NumbersLike
type ExtractArray<
Pairs extends PairsOfDigitsAndCaryingDigitsLikeArray,
Key extends Key0_1
> = {
[I in keyof Pairs]: Pairs[I] extends [DigitLike, CarryingDigitLike]
? Pairs[I][Key]
: never;
};
// Shift array of CarryingDigitsLike for the next sum iteration
type ShiftArray<Arr extends CarryingDigitLike[]> = Arr extends [...infer E, []]
? [[], ...E]
: [[], ...Arr];
// Separate pairs of DigitsLike and CaryingDigitsLike into two NumbersLike
// preparing for next iteration
type SeparateArrays<
Arr extends [DigitLike, CarryingDigitLike][],
U = [any, any]
> = {
[I in keyof U]: I extends '0'
? ExtractArray<Arr, I>
: I extends '1'
// Note to shift CarryingDigitsLike in array to comply of being next iteration summand
? ShiftArray<ExtractArray<Arr, I>>
: never;
};
// Iteratively perform sum until NumbersLike of carying digits is empty.
// Make sure to place shorter summand first
type SumImpl<Pair extends PairOfNumbersLike, A = Pair[0], B = Pair[1]> = {
[I in keyof B]: I extends keyof A
? [A[I], B[I]] extends [DigitLikeGuard<infer AI>, DigitLikeGuard<infer BI>]
? SumSingleDigits<AI, BI, []>
: never
: [B[I], []];
} extends PairsOfDigitsAndCaryingDigitsLikeArrayGuard<infer Iteration>
? SeparateArrays<Iteration> extends PairOfNumbersLikeGuard<infer NextPair>
// Examine if carrying digits number consists of zeroes to finish calculations
? NextPair[1] extends [][]
? NextPair[0]
: SumImpl<NextPair>
: never
: never;
// Prepare string for multiplication
// (divide string apart reverting and convert into NumbersLike)
type SplitStringReverting<
NL extends string | number | bigint,
S extends string = `${NL}`
> = S extends `${infer First}${infer Rest}`
? [...SplitStringReverting<Rest>, NumbersLikeMap0_9[First & DigitString]]
: [];
// Combine NumbersLike into string
type CombineArrayToString<Arr extends NumberLike> = Arr extends [
DigitLikeGuard<infer First>,
...NumberLikeGuard<infer Rest>
]
? `${CombineArrayToString<Rest>}${First['length']}`
: '';
// Sort out multiplying members placing the longer one first
type ArrangeArraysByLength<
Pair extends PairOfNumbersLike,
A = Pair[0],
B = Pair[1]
> = keyof A extends keyof A & keyof B ? [B, A] : Pair;
// Multiply NumberLike and DigitLike iteratively
type MultiplyByOneDigit<A extends NumberLike, M extends DigitLike> = M extends []
? [[]]
: M extends [any, ...DigitLikeGuard<infer MRest>]
? MRest extends []
? A
: SumImpl<[A, MultiplyByOneDigit<A, MRest>]>
: never;
// Iteratively perform multiplication extracting DigitsLike from second member one by one
type MultiplyImpl<
Pair extends PairOfNumbersLike,
A extends NumberLike = Pair[0],
B = Pair[1]
> = B extends [DigitLikeGuard<infer BNext>, ...NumberLikeGuard<infer BRest>]
? MultiplyByOneDigit<A, BNext> extends NumberLikeGuard<infer Iteration>
? BRest extends []
? Iteration
// Add tailing zero to result of next iteration and add it to intermediate result
: SumImpl<[Iteration, [[], ...MultiplyImpl<[A, BRest]>]]>
: never
: never;
type Multiply<
A extends string | number | bigint,
B extends string | number | bigint
> = CombineArrayToString<
MultiplyImpl<
// Sort multiplication members to achieve deeper possible recursion
ArrangeArraysByLength<[SplitStringReverting<A>, SplitStringReverting<B>]>
>
>;
Solution by turtleflyer #809
type Digits = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'];
type Digit = Digits[number];
type Tuple = readonly Digit[] | unknown[];
type Head<T extends Tuple> = T extends [infer F, ...infer _] ? F : '0';
type Tail<T extends Tuple> = T extends [infer _, ...infer R] ? R : [];
type RotateL<T extends Tuple> = T extends [infer F, ...infer R] ? [...R, F]: [];
type RotateR<T extends Tuple> = T extends [] ? [] : T extends [...infer I, infer L] ? [L, ...I] : never;
type prev = RotateR<Digits> & Record<string, never>
type SumMod10 = {
[d in Digit]: d extends '0' ? Digits : RotateL<SumMod10[prev[d]]>;
};
type mapZero<T extends [...Digit[]]> = {
[I in keyof T]: '0';
};
type Carry10 = {
[d in Digit]: d extends '0' ? mapZero<Digits> : [...Tail<Carry10[prev[d]]>, '1']
};
type addDigits<A extends Digit, B extends Digit> = {
current: SumMod10[A][B],
carry: Carry10[A][B],
};
type DigitAdded = { current: Digit; carry: Digit };
type DigitAddedInfer<Cur extends Digit, Car extends Digit> = { current: Cur; carry: Car };
type mapAddDigits<T extends [...Digit[]], D extends Digit> = {
[I in keyof T]: T[I] extends Digit ? addDigits<T[I], D> : never
};
type SumDigits = {
[d in Digit]: mapAddDigits<Digits, d>
};
type addAddedInMultiplyDigits<
A extends DigitAdded,
D extends Digit,
Current extends Digit = SumMod10[A['current']][D],
Carry extends Digit = SumMod10[Carry10[A['current']][D]][A['carry']] // assume not carry to hundred
> = DigitAddedInfer<Current, Carry>;
type addDigitsToDigitAdded<T extends any> = { // TODO restrict T
[I in Digit]:
I extends keyof T ?
T[I] extends infer DA ?
DA extends DigitAdded ?
addAddedInMultiplyDigits<DA, Digits[I]>
: never : never : never
};
type MultiplyDigits = {
[d in Digit]:
d extends '0' ? mapAddDigits<mapZero<Digits>, '0'> : addDigitsToDigitAdded<MultiplyDigits[prev[d]]>
};
type multiplyTupleDigit<T extends Tuple, D extends Digit, Carry extends Digit = '0'> =
T extends [] ?
Carry extends '0' ? [] : [Carry]
: addAddedInMultiplyDigits<MultiplyDigits[Head<T>][D], Carry> extends DigitAddedInfer<infer Cur, infer Car> ?
[Cur, ...multiplyTupleDigit<Tail<T>, D, Car>]
: never
;
type addTupleDigit<T extends Tuple, D extends Digit, Carry extends Digit = '0'> =
T extends [] ?
addDigits<D, Carry> extends DigitAddedInfer<infer Cur, infer Car> ?
Car extends '0' ? Cur extends '0' ? [] : [Cur] : [Cur, Car]
: never
: addAddedInMultiplyDigits<addDigits<Head<T>, D>, Carry> extends DigitAddedInfer<infer Cur, infer Car> ?
[Cur, ...addTupleDigit<Tail<T>, '0', Car>] : never
;
type addTuples<T1 extends Tuple, T2 extends Tuple, Carry extends Digit = '0'> =
T1 extends [] ? addTupleDigit<T2, Carry> :
T2 extends [] ? addTupleDigit<T1, Carry> :
addAddedInMultiplyDigits<addDigits<Head<T1>, Head<T2>>, Carry> extends DigitAddedInfer<infer Cur, infer Car> ?
[Cur, ...addTuples<Tail<T1>, Tail<T2>, Car>] : never
;
type MultiplyTuples<Multiplyee extends Tuple, Multiplyer extends Tuple, Carry extends Tuple = ['0']> =
Multiplyer extends [] ? Carry :
addTuples<multiplyTupleDigit<Multiplyee, Head<Multiplyer>>, Carry> extends infer Multiplyed ?
Multiplyed extends [infer F]
? [F, ...MultiplyTuples<Multiplyee, Tail<Multiplyer>, ['0']>]
: Multiplyed extends Tuple ? [Head<Multiplyed>, ...MultiplyTuples<Multiplyee, Tail<Multiplyer>, Tail<Multiplyed>>]
: never : never
;
type NumberLike = string | number | bigint;
type NumberLikeToString<N extends NumberLike> = `${N}`;
type SplitRevert<S extends string> = S extends `${infer Letter}${infer Rest}`
? [...SplitRevert<Rest>, Letter]
: [];
type ToTuple<N extends NumberLike> = SplitRevert<NumberLikeToString<N>>;
type JoinRevert<T extends Tuple> = T extends [] ? '' : `${JoinRevert<Tail<T>>}${Head<T>}`;
type RemoveHeadingZeros<T extends string> = T extends `0${infer R}` ? RemoveHeadingZeros<R> : T;
type TupleToString<T extends Tuple> = RemoveHeadingZeros<JoinRevert<T>> extends infer S ? S extends '' ? '0' : S : never;
type Multiply<A extends NumberLike, B extends NumberLike> =
TupleToString<MultiplyTuples<ToTuple<A>, ToTuple<B>>>
;
Solution by etoriet #704