# Easy-to-multiply numbers

Your task is to determine whether two numbers are easy to multiply. This means that their base-10 long multiplication doesn't have any carrying (regrouping) between place values, looking at both the multiplication steps and the addition step. This happens when each pair of digits being multiplied gives 9 or less and the sum of each column is 9 or less.

For example, 331 and 1021 are easy to multiply:

331
x 1021
------
+  331
662
0
331
------
337951

And the same is true (as is always) if we multiply in the other order:

1021
x  331
------
+ 1021
3063
3063
------
337951

But, 431 and 1021 are not easy to multiply, with carries happening between the columns indicated:

431
x 1021
------
+  431
862
0
431
------
440051
^^^

Also, 12 and 16 are not easy to multiply because a carry-over happens when multiplying 12 * 6 to get 72, even though no carries happen in the addition step.

12
x 16
----
+ 72
12
----
192

Input: Two positive integers or their string representations. You may assume they will not overflow your language's integer type, nor will their product.

Output: One consistent value if they are easy to multiply, and another consistent value if not.

Test cases: The first 5 are easy to multiply, the last 5 are not.

331 1021
1021 331
101 99
333 11111
243 201

431 1021
12 16
3 4
3333 1111
310 13

[(331, 1021), (1021, 331), (101, 99), (333, 11111), (243, 201)]
[(431, 1021), (12, 16), (3, 4), (3333, 1111), (310, 13)]

• Can input for each number be a list of digits? Dec 18 '17 at 22:53
• @dylnan No, though a list of characters is valid by default for the string option.
– xnor
Dec 18 '17 at 22:55

# Jelly, 7 bytes

Dæc/>9Ẹ

Try it online!

Uses convolution (which I contributed to Jelly :D)

## How it works

Dæc/>9Ẹ
D        converts to decimal list
æc      convolution
>9Ẹ  checks if any number is greater than 9
• o wow convolution :D I think this is my first time seeing convolution used in a code-golf :D +1 Dec 18 '17 at 22:58
• @HyperNeutrino codegolf.stackexchange.com/search?q=matl Dec 18 '17 at 22:59
• codegolf.stackexchange.com/questions/114495/topple-the-sandpile/… Dec 18 '17 at 23:18
• @LuisMendo No, that's a different convolution. Dec 19 '17 at 12:03
• BTW You can replace the last 3 bytes with <⁵Ạ for output without a boolean NOT performed on it. Dec 19 '17 at 12:07

# JavaScript (ES6), 67 bytes

Takes input as 2 strings in currying syntax (a)(b). Returns false for easy or true for not easy.

a=>b=>[...a].some((x,i,a)=>[...b].some(y=>(a[-++i]=~~a[-i]+x*y)>9))

### Test cases

let f =

a=>b=>[...a].some((x,i,a)=>[...b].some(y=>(a[-++i]=~~a[-i]+x*y)>9))

console.log('[Easy]')
console.log(f('331')('1021'))
console.log(f('1021')('331'))
console.log(f('101')('99'))
console.log(f('333')('11111'))
console.log(f('243')('201'))

console.log('[Not so easy]')
console.log(f('431')('1021'))
console.log(f('12')('16'))
console.log(f('3')('4'))
console.log(f('3333')('1111'))
console.log(f('310')('13'))

# Alt. version (flawed), 6455 52 bytes

Saved 3 bytes by taking strings, as suggested by @Shaggy
As pointed out by @LeakyNun, this method would fail on some large specific integers

Takes input as 2 strings in currying syntax (a)(b). Returns true for easy or false for not easy.

a=>b=>/^.(0.)*$/.test((g=n=>[...n].join0)(a)*g(b)) ### Test cases let f = a=>b=>/^.(0.)*$/.test((g=n=>[...n].join0)(a)*g(b))

console.log('[Easy]')
console.log(f('331')('1021'))
console.log(f('1021')('331'))
console.log(f('101')('99'))
console.log(f('333')('11111'))
console.log(f('243')('201'))

console.log('[Not so easy]')
console.log(f('431')('1021'))
console.log(f('12')('16'))
console.log(f('3')('4'))
console.log(f('3333')('1111'))
console.log(f('310')('13'))

### How?

The idea here is to explicitly expose carries by inserting zeros before each digit of each factor.

Examples:

• 331 x 1021 becomes 30301 x 1000201, which gives 30307090501 instead of 337951. By adding a leading zero to the result and grouping all digits by 2, this can be written as 03 03 07 09 05 01. All groups are less than 10, meaning that there would not have been any carry in the standard multiplication.

• 431 x 1021 becomes 40301 x 1000201, which gives 40309100501 and can be written as 04 03 09 10 05 01. This time, we have a 10 which reveals a carry in the standard multiplication.

• Can... Can we have a basic explanation on the algorithm? Dec 18 '17 at 23:16
• @totallyhuman I've added an explanation. (Oops ... and also fixed a bug.) Dec 18 '17 at 23:28
• Looks like you should be able to save 3 bytes by taking the inputs as strings. Dec 18 '17 at 23:36
• It took me an eternity to find a (theoretical) counter-example which your algorithm will fail: tio.run/##y0rNyan8/9/l8LJk/f///… (the 108 in the middle messes up your algorithm) Dec 19 '17 at 0:10
• @LeakyNun Nice find. Yes, it can theoretically overflow. Dec 19 '17 at 0:24

# Alice, 30 bytes

/Q.\d3-&+k!*?-n/ o @
\ic/*2&w~

Try it online!

Outputs 1 for easy and 0 for hard.

The numbers are easy to multiply if and only if the digit sum of the product equals the product of the digit sums.

/i    Input both numbers as a single string
.     Duplicate this string
/*    Coerce into two integers and multiply
2&w   Push return address twice (do the following three times)
~\Q     Swap the top two stack entries, then reverse the stack
This produces a 3-cycle, and the first iteration coerces
the original input string into two integers
c       Convert into individual characters
\d3-&+  Add all numbers on the stack except the bottom two (i.e., add all digits)
At this point, all three numbers are replaced by their digit sums
!*?   Multiply the digit sums of the original two numbers
-     Subtract the digit sum of the product
n     Logical negate: convert to 1 or 0
/o@   Output as character and terminate

# MATL, 10 bytes

,j!U]Y+9>a

Outputs 0 for easy, 1 for hard.

### Explanation

,       % Do twice
j     %   Input as a string
!     %   Transpose into a column vector of characters
U     %   Convert each character to number. Gives a numeric column vector
]       % End
Y+      % Convolution, full size
9>      % Greatear than 1? Element-wise
a       % Any: true if there is some true entry. Implicitly display

# R, 135110109 86 bytes

function(m,n)any(convolve(m%/%10^(nchar(m):1-1)%%10,n%/%10^(1:nchar(n)-1)%%10,,"o")>9)

Try it online!

Takes input as strings.

It's ugly but it works™.

This now uses a convolution approach, as in Leaky Nun's answer, so it takes input as integers, and returns TRUE for hard to multiply numbers and FALSE for easy to multiply ones.

I have always had some trouble porting convolution approaches in the past, but today I finally read the documentation:

Note that the usual definition of convolution of two sequences x and y is given by convolve(x, rev(y), type = "o")

Which is just silly. So the digit extraction is reversed for n, and it resolves into a port of Leaky Nun's answer.

# Python 2, 88 bytes

lambda n,m:any(sum(n/10**(k-j)%10*(m/10**j%10)for j in range(k+1))>9for k in range(n+m))

Takes two integers as input and returns False (easy to multiply) or True (not).

Try it online! (too slow for one of the test cases)

• Quick maffs version Dec 19 '17 at 1:49
• len(n+m) would actually fail for 40, 30. Dec 19 '17 at 1:51
• len(n+m)+1? Dec 19 '17 at 1:51
• That fails for 400, 300. len(n+m) should do though. Dec 19 '17 at 1:53

# JavaScript (Node.js), 434137 36 bytes

Thanks @Dennis for the idea of using string interpolation in this answer and save 4 bytes!

Thanks @ØrjanJohansen for -1!

a=>b=>eval(0x${a}*0x${b}<0x${a*b}) Try it online! Of course when the destination base is less than the original base (like in my Jelly answer, the base is 2) the < must be flipped. • Congrats on being the first to figure out to use base conversion, for which I give you the bounty! – xnor Dec 28 '17 at 19:32 # Wolfram Language (Mathematica), 756665 56 bytes f:=#~FromDigits~x& g:=Max@CoefficientList[f@#2f@#,x]<=9& Try it online! Receiving 2 string inputs Explanation: f:=#~FromDigits~x& (* Turns the number to a polynomial with the digits as coefficients *) g:=Max@CoefficientList[f@#2f@#,x]<=9& (* Polynomial multiplication, and check whether all coefficients are smaller than 10 *) -9 for changing to use string as input -1 for using infix operator -9 Thanks @MartinEnder for the Max function # Python 2, 158135123 113 bytes -12 bytes thanks to Leaky Nun -10 bytes thanks to ovs a,b=input() e=enumerate l=[0,0]*len(a+b) for i,x in e(a): for j,y in e(b):l[i-~j]+=int(x)*int(y) print max(l)<10 • Doesn't all(d[k]<10for k in d) work or is it just Python 3? Dec 18 '17 at 23:13 • @shooqie yes, it does, but now it's a list c: – Rod Dec 18 '17 at 23:17 • 129 bytes Dec 18 '17 at 23:18 # Julia 0.6, 30 bytes ~x=any(conv(digits.(x)...).>9) Try it online! Input is a tuple of numbers, output is true for hard to multiply numbers and false for easy ones. . is element-wise function application. ... expands the tuple (of lists of integer digits) to two seperate inputs of the conv function. # Python 3, 58351340 39 bytes lambda n,m:eval(f'0x{n}*0x{m}<0x{n*m}') Looks like I had this idea two hours too late. Thanks to @ØrjanJohansen for golfing off 1 byte! Try it online! # SNOBOL4 (CSNOBOL4), 268264247246243 131 bytes DEFINE('D(A)') M =INPUT N =INPUT OUTPUT =EQ(D(M) * D(N),D(M * N)) 1 :(END) D A LEN(1) . X REM . A :F(RETURN) D =D + X :(D) END Try it online! Ports the approach by Nitrodon. I think this is the first time I've ever defined a function in SNOBOL, D for digit sum. DEFINE('D(A)') ;* function definition M =INPUT ;* read input N =INPUT ;* read input OUTPUT =EQ(D(M) * D(N),D(M * N)) 1 :(END) ;* if D(M)*D(N)==D(M*N), ;* print 1 else print nothing. Goto End D A LEN(1) . X REM . A :F(RETURN) ;* function body D =D + X :(D) ;* add X to D END ### old version, 243 bytes: M =INPUT N =INPUT P =SIZE(M) Q =SIZE(N) G =ARRAY(P + Q) Z OUTPUT =LE(P) :S(E) M LEN(P) LEN(1) . A J =Q Y GT(J) :F(D) N LEN(J) LEN(1) . B W =I + J X =G<W> + A * B G<W> =LE(A * B,9) LE(X,9) X :F(E) J =J - 1 :(Y) D P =P - 1 :(Z) E END Try it online! Input on STDIN separated by newlines, output to STDOUT: a single newline for easy to multiply, and no output for not easy to multiply. This isn't going to win any awards but it presents another approach (well, really this is the naive approach). I don't think I could write this up in cubix, but SNOBOL is tough enough to work with as it is. Since it takes input as a string, this will work for any input with less than 512 digits each; I'm not 100% sure how big ARRAYs in SNOBOL can be. INPUT is buffered in this version of SNOBOL to have a maximum width of 1024 characters; all other characters are then lost. It appears that an ARRAY can be quite large; well over the 2048 cells necessary. M =INPUT ;*read input N =INPUT ;*read input P =SIZE(M) ;*P = number of M's digits, also iteration counter for outer loop Q =SIZE(N) ;*Q = number of N's digits G =ARRAY(P + Q) ;*G is an empty array of length P + Q Z GE(P) :F(T) ;*if P<0, goto T (outer loop condition) M LEN(P) LEN(1) . A ;*A = P'th character of M J =Q ;*J is the iteration counter for inner loop Y GT(J) :F(D) ;*if J<=0, goto D (inner loop condition) N LEN(J) LEN(1) . B ;*B = J'th character of N W =I + J ;*W=I+J, column number in multiplication X =G<W> + A * B ;*X=G[W]+A*B, temp variable for golfing G<W> =LE(A * B,9) LE(X,9) X :F(END) ;*if A*B<=9 and X<=9, G[W]=X otherwise terminate with no output J =J - 1 :(Y) ;*decrement J, goto Y D P =P - 1 :(Z) ;*decrement P, goto Z T OUTPUT = ;*set output to ''; OUTPUT automatically prints a newline. END # Charcoal, 38 bytes ≔Ｅ⁺θη⁰ζＦＬθＦＬη§≔ζ⁺ικ⁺§ζ⁺ικ×Ｉ§θιＩ§ηκ‹⌈ζχ Try it online! Link is to verbose version of code. Outputs a - when the numbers are easy to multiply. Explanation: ≔Ｅ⁺θη⁰ζ Initialise z to a large enough (sum of lengths of inputs) array of zeros. ＦＬθＦＬη Loop over the indices of the inputs q and h. §≔ζ⁺ικ⁺§ζ⁺ικ×Ｉ§θιＩ§ηκ Perform one step of the long multiplication. ‹⌈ζχ Check for carries. # Pari/GP, 52 bytes f(a,b)=vecmax(Vec(Pol(digits(a))*Pol(digits(b))))<10 Try it online! ## Haskell, 82 81 bytes q=map$read.pure
f a=any(>9).concat.scanr((.(0:)).zipWith(+).(<$>q a).(*))(0<$a).q

The numbers a taken as strings. Returns False if the numbers are easy to multiply and True otherwise.

Try it online!

I think it's different enough from @Laikoni's answer. How it works:

q                    -- helper function to turn a string into a list of digits

f a =                -- main function, first number is parameter 'a'
scanr    .q    -- fold the following function from the right (and collect
-- the intermediate results in a list) into the list of
-- digits of the second number
0<$a -- starting with as many 0s as there are digits in 'a' -- the function is, translated to non-point free: \n c->zipWith(+)((*n)<$>q a)$0:c -- 'n': next digit of 'b'; 'c': value so far (*n)<$>a     --    multiplay each digit in 'a' with 'n'
0:c          --    prepend a 0 to 'c'
zipWith(+)   --    add both lists element wise
--    (this shifts out the last digit of 'c' in every step)
concat            -- flatten the collected lists into a single list
any(>9)             -- check if any number is >9
• Nice solution! I was looking for ways to get rid of the import, but they ended up even longer. Dec 20 '17 at 20:40

Edit:

• -1 byte changing == to <.

I thought of this before looking at the other answers, then discovered that the Alice one used the same basic idea. Posting anyway since it's shorter than the other Haskell answers.

? takes two integers and returns a Bool. Use as 331?1021. False means the multiplication is easy.

a?b=s(a*b)<s a*s b

Try it online!

• s is a function that calculates the sum of the digits of an integer. (read.pure converts a single digit character to an integer.)
• If a pair of numbers is easy to multiply, the digit sum of the product is equal to the product of the digit sums.
• Conversely, any carry during the long multiplication will reduce the digit sum of the product from that ideal.

->a,b{(0..a+b=~/$/).all?{|r|(0..r).sum{|w|a[w].to_i*b[r-w].to_i}<10}} Try it online! # Haskell, 123 bytes import Data.List r=read.pure a%b|l<-transpose[reverse$map((*r d).r)b++(0<$e)|d:e<-scanr(:)""a]=all(<10)$concat l++map sum l

Try it online! Example usage: "331" % "1021" yields True.

# Perl 5, 100 + 2 (-F) = 102 bytes

push@a,[reverse@F]}{map{for$j(@{$a[0]}){$b[$i++].='+'.$_*$j}$i=++$c}@{$a[1]};map$\||=9>eval,@b;say\$\

Try it online!

outputs false for easy, true for not easy.

# Jelly, 8 bytes

;PDḄµṪ⁼P

Try it online!

A port of my Javascript answer. Not shorter than the existing Jelly answer because Jelly have powerful convolution built-in.

Take input as a list of two numbers. Returns 1 for easy, 0 for not easy.

Explanation:

;PDḄµṪ⁼P     Main link. Let input = [101, 99]
;P           Concatenate with product. Get [101, 99, 9999]
D          Convert to decimal. Get [[1,0,1], [9,9], [9,9,9,9]]
Ḅ         Convert from binary. Get [1 * 2^2 + 0 * 2^1 + 1 * 2^0,
9 * 2^1 + 9 * 2^0, 9 * 2^3 + 9 * 2^2 + 9 * 2^1 + 9 * 2^0]
= [5, 27, 135]
µ        With that value,
Ṫ       Take the tail from that value. Get 135, have [5, 27] remain.
⁼      Check equality with...
P       The product of the remaining numbers (5 and 17).

# C (gcc), 104 bytes

Basically do a multiplication "by hand" into r[] and set return value if any column gets higher than 9, since that would mean a carry has occurred.

Surprisingly, this was shorter than my first attempt which took strings as arguments.

f(a,b){int*q,r[10]={0},*p=r,R=0,B;for(;a;a/=10)for(q=p++,B=b;B;B/=10)R|=(*q+++=a%10*(B%10))>9;return R;}

Try it online!

# Husk, 10 bytes

§§=¤o*oΣd

Try it online! Outputs 1 if the arguments are easy to multiply, and 0 otherwise. A port of Nitrodon's answer.

# CJam, 18 bytes

{_{Ab:+}:T/*\:*T=}

Try it online!

Takes input on the stack in the form of [1021 331]. Checks that the product of the sum of the digits and the sum of the digits of the product are equal.

To take input as a space-delimited string, remove the outer curly braces and prepend with q~].

## Alternate 18-byter

{{'0*i}/*);-2%i!}

Try it online!

Takes input on the stack in the form of ["1021" "331"]. A port of Arnauld's fantastic answer.

To take input as a space-delimited string, remove the outer curly braces and prepend with qS/.