34
\$\begingroup\$

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)]

Leaderboard:

var QUESTION_ID=151130,OVERRIDE_USER=20260;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/151130/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

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

21 Answers 21

14
\$\begingroup\$

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
\$\endgroup\$
8
\$\begingroup\$

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), 64 55 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].join`0`)(a)*g(b))

Test cases

let f =

a=>b=>/^.(0.)*$/.test((g=n=>[...n].join`0`)(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.

\$\endgroup\$
  • \$\begingroup\$ Can... Can we have a basic explanation on the algorithm? \$\endgroup\$ – totallyhuman Dec 18 '17 at 23:16
  • \$\begingroup\$ @totallyhuman I've added an explanation. (Oops ... and also fixed a bug.) \$\endgroup\$ – Arnauld Dec 18 '17 at 23:28
  • 1
    \$\begingroup\$ Looks like you should be able to save 3 bytes by taking the inputs as strings. \$\endgroup\$ – Shaggy Dec 18 '17 at 23:36
  • 3
    \$\begingroup\$ 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) \$\endgroup\$ – Leaky Nun Dec 19 '17 at 0:10
  • \$\begingroup\$ @LeakyNun Nice find. Yes, it can theoretically overflow. \$\endgroup\$ – Arnauld Dec 19 '17 at 0:24
6
\$\begingroup\$

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)
k     Return to pushed address (end loop)
      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
\$\endgroup\$
4
\$\begingroup\$

MATL, 10 bytes

,j!U]Y+9>a

Outputs 0 for easy, 1 for hard.

Try it online! Or verify all test cases.

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
\$\endgroup\$
4
\$\begingroup\$

R, 135 110 109 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.

\$\endgroup\$
4
\$\begingroup\$

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)

\$\endgroup\$
  • \$\begingroup\$ Quick maffs version \$\endgroup\$ – Leaky Nun Dec 19 '17 at 1:49
  • \$\begingroup\$ len(`n+m`) would actually fail for 40, 30. \$\endgroup\$ – Dennis Dec 19 '17 at 1:51
  • \$\begingroup\$ len(`n+m`)+1? \$\endgroup\$ – Leaky Nun Dec 19 '17 at 1:51
  • \$\begingroup\$ That fails for 400, 300. len(`n`+`m`) should do though. \$\endgroup\$ – Dennis Dec 19 '17 at 1:53
4
+100
\$\begingroup\$

JavaScript (Node.js), 43 41 37 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.

\$\endgroup\$
  • \$\begingroup\$ Congrats on being the first to figure out to use base conversion, for which I give you the bounty! \$\endgroup\$ – xnor Dec 28 '17 at 19:32
3
\$\begingroup\$

Wolfram Language (Mathematica), 75 66 65 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

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

Python 2, 158 135 123 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

Try it online! or Try all test cases

\$\endgroup\$
  • \$\begingroup\$ Doesn't all(d[k]<10for k in d) work or is it just Python 3? \$\endgroup\$ – shooqie Dec 18 '17 at 23:13
  • 1
    \$\begingroup\$ @shooqie yes, it does, but now it's a list c: \$\endgroup\$ – Rod Dec 18 '17 at 23:17
  • \$\begingroup\$ 129 bytes \$\endgroup\$ – Leaky Nun Dec 18 '17 at 23:18
3
\$\begingroup\$

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.

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

Python 3, 58 3513 40 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!

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

SNOBOL4 (CSNOBOL4), 268 264 247 246 243 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
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 38 bytes

≔E⁺θη⁰ζFLθFLη§≔ζ⁺ικ⁺§ζ⁺ικ×I§θιI§ηκ‹⌈ζχ

Try it online! Link is to verbose version of code. Outputs a - when the numbers are easy to multiply. Explanation:

≔E⁺θη⁰ζ

Initialise z to a large enough (sum of lengths of inputs) array of zeros.

FLθFLη

Loop over the indices of the inputs q and h.

§≔ζ⁺ικ⁺§ζ⁺ικ×I§θιI§ηκ

Perform one step of the long multiplication.

‹⌈ζχ

Check for carries.

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

Pari/GP, 52 bytes

f(a,b)=vecmax(Vec(Pol(digits(a))*Pol(digits(b))))<10

Try it online!

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

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
\$\endgroup\$
  • \$\begingroup\$ Nice solution! I was looking for ways to get rid of the import, but they ended up even longer. \$\endgroup\$ – Laikoni Dec 20 '17 at 20:40
2
\$\begingroup\$

Haskell, 45 44 bytes

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
s=sum.map(read.pure).show

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.
\$\endgroup\$
1
\$\begingroup\$

Ruby, 69 bytes

->a,b{(0..a+b=~/$/).all?{|r|(0..r).sum{|w|a[w].to_i*b[r-w].to_i}<10}}

Try it online!

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

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.

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

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.

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

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).
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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