14
\$\begingroup\$

In this task you will be given A (less than 10000 digits long) and B (less than 2^64), and you will need to compute the last digit of (A · A · A · ... · A (B times)).

The inputs A and B are given in a single line separated by a blank; the inputs are terminated by EOF.

Input

34543232321323243242434544533445343432434311112223454323232132324324243454453344534343243431111222345432323213232432424345445334453434324343111122234543232321323243242434544533445343432434311112223454323232132324324243454453344534343243431111222345432323213232432424345445334453434324343111122234543232321323243242434544533445343432434311112223454323232132324324243454453344534343243431111222 22337254775808
38758436543765743875437656358764347568437658743658743454354645645543532487548758475847684756897548758457843758437584758478574857438758436587436587436587643875643856783478743658743658764387564387564378658437658743658743687564387564387564765746576475647564756475465746574675647654765476547534587545689475689748574385743765874585743857843765893748643587438957458754376543265874387564384764367584375874758943267632487564357 54545454123
6777744348435743587643756438765436574587564354375674365645643675 23232    
3875843654376574357 54545454

Output

6
3
5
9

Constraints

  • Don't use any inbuilt function or overloaded operators to compute AB (you don't really need to compute that at all).
  • Shortest solution wins!
\$\endgroup\$
  • 2
    \$\begingroup\$ Is it allowed to use the exponentiation operator to compute things other than A**B? \$\endgroup\$ – Lowjacker Mar 28 '11 at 0:13
  • \$\begingroup\$ I presume that both A and B are non-negative? \$\endgroup\$ – aaaaaaaaaaaa Mar 28 '11 at 14:05

10 Answers 10

9
\$\begingroup\$

J - 52 characters

wd,.10|(^12+12&|)/"1(".@{:`".;._2@,&'x ');._2(1!:1)3

Passes all tests given, though only if the trailing spaces on the third input are removed (I'm guessing this was unintentional).

Solution will work in j602 in console mode (e.g. in terminal, emacs j-shell, etc.). It will not work in j701 (no wd).

Explanation & Mathiness:

The 'magic number' 12 is the LCM of the lengths of the "last digit" tables found in the other answers. All digits repeat with periods 1,2,3 or 4 so they will also repeat with period 12. Adding twelve to that fixes cases where b mod 12 = 0. My solution computes (Last digit of A)^(12+(B mod 12)), giving a number with the same last digit. (I considered a sneaky broken solution eliminating the three characters '12+' by using e.g. B mod 96 where no examples were likely to collide...)

\$\endgroup\$
6
\$\begingroup\$

Python 125 107 Chars

O(1) solution

while 1:a,b=map(int,raw_input().split());d=1;exec"d*=a;"*(b%4);c=a%5and d%5;print b/~b+1or c+[0,5][c%2-a%2]
\$\endgroup\$
  • \$\begingroup\$ Nice +1. \$\endgroup\$ – Quixotic Mar 26 '11 at 14:45
6
\$\begingroup\$

GolfScript 21

~]2/{~.(4%)and?10%n}/

This basically calculate A^C mod 10 where C is in the range [1,4] and C mod 4 = B mod 4, except if B is 0, then C is also 0.

This shortcut is possible because A^(B+4) mod 10 = A^B mod 10 for any non-negative integer A and positive integer B.

\$\endgroup\$
5
\$\begingroup\$

J, 79

,._2(4 :'10|x^(+y&(|~))x{10$1 1 4 4 2')/\x:".(]_1&{.`];._2~(' ',LF)e.~])(1!:1)3
\$\endgroup\$
  • \$\begingroup\$ Wow that's ugly! Remind me not to learn this language. +1 for putting up with it. \$\endgroup\$ – Caleb Apr 12 '11 at 12:12
5
\$\begingroup\$

Ruby, 97 93 72 71 67 61 60

Also handles the case where b == 0.

#!ruby -nl
~/ /
p eval"#$`%10*"*($'>?0?($'.to_i-1)%4+1:0)+?1

Guess it's actually worse to use a lookup table.

\$\endgroup\$
  • \$\begingroup\$ It gives 1 as output on giving 2 5 as input and does not even give correct output for sample cases above. ideone.com/2cOPy \$\endgroup\$ – fR0DDY Mar 27 '11 at 4:07
  • 1
    \$\begingroup\$ @fR0DDY: It works perfectly on my system, with 1.9.2 too. \$\endgroup\$ – Lowjacker Mar 27 '11 at 9:52
4
\$\begingroup\$

Windows PowerShell, 85

O(1) solution. Taken a hint from Lowjacker's Ruby solution ;-)

$input|%{$a,$b=-split$_
'0000111162481397646455556666179368421919'[4*$a[-1]%48+$b%4]}
\$\endgroup\$
3
\$\begingroup\$

Python 149 Chars

p=[[0],[1],[6,2,4,8],[1,3,9],[6,4],[5],[6],[1,7,9,3],[6,8,4,2],[1,9]]
while 1:a,b=map(int,raw_input().split());print b/~b+1or p[a%10][b%len(p[a%10])]
\$\endgroup\$
3
\$\begingroup\$

Python (119 134 109)

I trust the prohibition against built-in functions doesn't apply to I/O.

import sys
p=lambda b,e:e and p(b*b%10,e/2)*(~e&1or b)%10or 1
for l in sys.stdin:print p(*map(int,l.split()))

Edit: remove use of Python's exponentiation operator.

Edit: Replaced ternary operators with short-circuited boolean operators.

\$\endgroup\$
  • \$\begingroup\$ Yes you can/must use I/O functions for taking the inputs but you are not supposed to use '**' for this task. \$\endgroup\$ – Quixotic Mar 26 '11 at 8:11
  • \$\begingroup\$ This would work though but I don't really intend this task for a brute-forced modular exponentiation solution,actually there is an O(1) algorithm and it's very short too :-) \$\endgroup\$ – Quixotic Mar 26 '11 at 8:18
2
\$\begingroup\$

Python 3k

121 Chars

def p(a,b):
  if b<1:return 1
  return p(a*a%10,b//2)*[1,a][b%2]%10
while 1:
  a,b=map(int,input().split())
  print(p(a%10,b))

The (a*a)%10 is not necessary but it speeds it up, so decided to keep it.

Edit: Apparently, the parentheses are not required.

Meanwhile, thinking about the O(1) Solution. :)

\$\endgroup\$
  • \$\begingroup\$ Won't the loop error after the EOF? \$\endgroup\$ – Hoa Long Tam Mar 26 '11 at 10:37
2
\$\begingroup\$

Javascript ( 117 84 79 60 chars)

Reached 60 chars with the suggested improvements from @JiminP and @NoOneIsHere. Thank you!

d=function(s,n){a=Math.pow(s[s.length-1],n%4==0?1:n%4)+'';return a[a.length-1]}

d=(s,n)=>{return(Math.pow(s.slice(-1),n%4||1)+'').slice(-1)}

To test:

console.log(d('243242434544533445343432434311112223454323232132324324243454453344534343243431111222345432323213232432424345445334453434324343111122234543232321323243242434544533445343432434311112223454323232132324324243454453344534343243431111222345432323213232432424345445334453434324343111122234543232321323243242434544533445343432434311112223454323232132324324243454453344534343243431111222', 22337254775808));
console.log(d('38758436543765743875437656358764347568437658743658743454354645645543532487548758475847684756897548758457843758437584758478574857438758436587436587436587643875643856783478743658743658764387564387564378658437658743658743687564387564387564765746576475647564756475465746574675647654765476547534587545689475689748574385743765874585743857843765893748643587438957458754376543265874387564384764367584375874758943267632487564357', 54545454123));
console.log(d('6777744348435743587643756438765436574587564354375674365645643675', 23232));
console.log(d('3875843654376574357', 54545454));

Results:

2
3
5
9
\$\endgroup\$
  • 1
    \$\begingroup\$ d=function(s,n){return(Math.pow(s.slice(-1),n%4||1)+'').slice(-1)} :P \$\endgroup\$ – JiminP Mar 28 '12 at 16:46
  • 1
    \$\begingroup\$ I don't use JavaScript much, but couldn't you use d=s,n=>(Math.pow(s.slice(-1),n%4||1)+'').slice(-1) or use => at all? \$\endgroup\$ – NoOneIsHere Feb 29 '16 at 22:09

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.