[Codewars] Last digit of a large number (5 kyu) / JavaScript

https://www.codewars.com/kata/5511b2f550906349a70004e1

Codewars - Achieve mastery through coding practice and developer mentorship

 

DESCRIPTION:

Define a function that takes in two non-negative integers \(a\) and \(b\) and returns the last decimal digit of \(a^b\). Note that \(a\) and \(b\) may be very large!

For example, the last decimal digit of \(9^7\) is \(9\), since \(9^{7} = 4782969\). The last decimal digit of \((2^{200})^{2^{300}}\), which has over \(10^{92}\) decimal digits, is \(6\). Also, please take \(0^{0}\) to be \(1\).

You may assume that the input will always be valid.

 

Examples

lastDigit("4", "1")            // returns 4
lastDigit("4", "2")            // returns 6
lastDigit("9", "7")            // returns 9    
lastDigit("10","10000000000")  // returns 0

 

Remarks

JavaScript, C++, R, PureScript, COBOL

Since these languages don't have native arbitrarily large integers, your arguments are going to be strings representing non-negative integers instead.

 

설명:

음이 아닌 두 정수 \(a\)와 \(b\)를 받아 \(a^b\)의 마지막 숫자를 반환하는 함수를 정의하세요. \(a\)와 \(b\)는 매우 클 수도 있으니 주의하세요!

예를 들어, \(9^7\) 는 \(9^{7} = 4782969\)이기 때문에 마지막 수는 \(9\) 입니다. \(10^{92}\) 개가 넘는 자리수를 가진 \((2^{200})^{2^{300}}\)의 마지막 자리수는 \(6\)입니다. 그리고 \(0^{0}\)는 \(1\)를 취합니다.

입력은 언제나 유효하다고 가정될 수 있습니다.

 

예시

lastDigit("4", "1")            // returns 4
lastDigit("4", "2")            // returns 6
lastDigit("9", "7")            // returns 9    
lastDigit("10","10000000000")  // returns 0

 

주목

JavaScript, C++, R, PureScript, COBOL

이 언어들은 임의로 큰 정수를 가지고 있지 않기 때문에, 인자는 음수가 아닌 정수 대신 문자열의 표현으로 주어집니다.

 

풀이

var lastDigit = function(str1, str2){
  if(str2 === '0') return 1;
  let result = parseInt(str1.slice(-1));
  let count = parseInt(str2.slice(-2)) % 4;
  if(count === 0) count = 4;
  return Math.pow(result, count) % 10;
}

 

곱셈은 다음과 같이 반복된다.

0	0
1	1
2	2	4	8	6
3	3	9	7	1
4	4	6
5	5
6	6
7	7	9	3	1
8	8	4	2	6
9	9	1

예를 들어 2를 1번 곱하면 2, 2번 곱하면 4, 3번 곱하면 8, 4번 곱하면 6 그리고 5번 곱하면 다시 2가 되고 이런 식으로 최대 4번 단위로 반복하게 된다.  그래서 result에 곱해야 하는 밑의 값으로 str1 문자열의 맨 마지막 숫자를 저장해 주고 지수인 count는 str2의 끝의 두 숫자를 저장해준다(100은 4의 배수이기 때문에 100의 자리 이상은 고려하지 않아도 된다). 그리고 그 수를 4로 나누어 남은 나머지를 count에 저장한다. 그리고 count가 0이면 4번 곱해진 것이기 때문에 count를 4로 바꾼다. 그리고 count의 수만큼 result를 곱한 결과를 10으로 나눈 나머지를 반환한다.

참고

https://www.geeksforgeeks.org/find-last-digit-of-ab-for-large-numbers/

Find Last Digit of a^b for Large Numbers - GeeksforGeeks