September 2017 – 블로그 이사갔어요! https://milooy.github.io/

Daily Codewars #31 Factorial Tail

Question

자연수 a의 팩토리얼 수를 b진수로 고쳤을 때 뒤에 0이 얼마나 붙는지 구하는 질문이다. 4kyu짜리 문제.

How many zeroes are at the end of the factorial of 10? 10! = 3628800, i.e. there are 2 zeroes. 16! in hexadecimal would be 0x130777758000, which has 3 zeroes.

Unfortunately, machine integer numbers has not enough precision for larger values. Floating point numbers drop the tail we need. We can fall back to arbitrary-precision ones – built-ins or from a library, but calculating the full product isn’t an efficient way to find just the tail of a factorial. Calculating 100’000! in compiled language takes around 10 seconds. 1’000’000! would be around 10 minutes, even using efficient Karatsuba algorithm

is to write a function, which will find the number of zeroes at the end of (number) factorial in arbitrary radix = base for larger numbers.

base is an integer from 2 to 256
number is an integer from 1 to 1’000’000

비하인드 스토리

점심 먹고 잠도 깰 겸 코드워즈를 틀었다. 처음엔 별 고민 없이 숫자.toString(몇진수)가 큰 수에서 overflow나길래 toString 없이 N진수로 고치는 코드를 짰다. 근데 그런 문제가 아니었음. 50 팩토리얼만 해도 콤퓨타에서 저장할 수 없으니… (팩토리얼로 변환가능해야 하는 범위는 100만까지다).
회사 옆자리 동료분께 “50!를 2진수로 바꿨을 때 뒤에 0이 얼마나 붙어요?” 여쭤보니 그건 수학 문제에 더 가깝고, ACM(대학생 프로그래밍 경시대회) 1번 문제 난이도라고 하였다(다른 분께선 그건 아니고 예선문제 정도 레베루라고…).

내가 계속 실마리를 못 잡으니 힌트를 주셨다.

h: 0의 의미를 생각해보세요
나: …
h: 50!를 10진수로 바꿨을 때 뒤에 0이 붙는 경우를 생각해보세요

My Answer

정말 실마리는 0의 의미에 있었다.
팩토리얼을 풀어해쳤을 때, 8!는 8*7*6*5*4*3*2*1 이다. 10진수가 0으로 끝나려면 2A * 5B나 10C가 저 안에 있으면 되지 않을까?
그럼 n진수 뒤의 0은 number(팩토리얼 당하는 수)를 풀어해친 수 속에 얼마나 base(진수)가 들어있는지 찾으면 되는구나.

처음엔 number를 무작정 base로 나눠갔다. 당연히 또 overflow가 났다. 나머지를 계속 곱하면서 저장하니 당연히…

function zeroes (base, number) {
  var answer = 0;
  var remain = 1;
  for (var i = number; i > 0; i--) {
    var newI = i;
    newI *= remain; // 나누고 난 나머지는 계속 곱해둠 -> overflow 원흉
    if(newI%base === 0) { // 나눠 떨어지면 answer를 증가시킴
      answer++;
      newI = Math.floor(newI/base);
    }
    remain = newI;
  }
  return answer;
}

그 다음은 base와 number 모두 소인수분해를 해서 이를 비교해보았다. 소인수분해 함수를 만들어서 돌려 썼다.

function zeroes (base, number) {
  function makePrime(num, obj) { // 소인수분해 하는 함수
    for (var i = 2; i <= num; i++) {
      var quantity = 0;
      while(num%i===0) {
        quantity++;
        num = Math.floor(num/i);
      }
      if(quantity>0){
        var originVal = obj[i];
        obj[i] = originVal? originVal + quantity : quantity;
      }
    }
    return obj;
  }

  var basePrime = makePrime(base, {});
  var numberPrime = {};
  for (var i = number; i >= 0; i--) { // 팩토리얼 for문 돌며 공용 object에 인수를 집어넣는다
    makePrime(i, numberPrime);
  }

  var answer = 0;
  var answerList = [];
  var baseLength = Object.keys(basePrime).length;
  for (var i = 0; i < baseLength; i++) { // 소인수분해한 두 object 비교
    var oName = Object.keys(basePrime)[i];
    if(!numberPrime[oName]) {
      answer = 0;
      break;
    }
    var result = Math.floor(numberPrime[oName] / basePrime[oName])
    answerList.push(result)
  }
  return Math.min.apply(null, answerList);
}

이 함수의 문제점은 zeroes(2, 524288)정도로 팩토리얼 할 수가 커지면 연산이 터지는 것이었다.
zeroes(2, 100000)크기의 연산도 4.8s나 걸린다.
자잘한 성능 최적화로는 안되고 연산 자체를 토막내야 되겠네…

더 생각해보니 number의 소인수를 굳이 모두 구할 필요 없이 base의 소인수로만 연산하면 되는거였다. base는 범위도 256까지밖에 안 된다. (e.g. base 소인수가 {2:2, 3:5}라면 number에서 2와 3의 갯수만 구하기)

function zeroes (base, number) {
  function makePrime(num, obj) { // base용 소인수분해
    for (var i = 2; i <= num; i++) {
      var quantity = 0;
      while(num%i===0) {
        quantity++;
        num = Math.floor(num/i);
      }
      if(quantity>0){
        var originVal = obj[i];
        obj[i] = quantity;
      }
    }
    return obj;
  }

  function makePrimeArray(num, obj, arr) { // number용 소인수분해: base의 키값만 돌며 인수를 구한다
    var length = arr.length;
    for (var i = 0; i < length; i++) {
      var arrKey = arr[i], quantity = 0;
      while(num>0 && num%arrKey===0) {
        quantity++;
        num = Math.floor(num/arrKey);
      }
      if(quantity>0){
        var originVal = obj[arrKey];
        obj[arrKey] = originVal? originVal + quantity : quantity;
      }
    }
    return obj;
  }

  var basePrime = makePrime(base, {}),
      numberPrime = {},
      basePrimeArr = Object.keys(basePrime),
      answer = Infinity,
      answerList = [],
      baseLength = Object.keys(basePrime).length;

  for (var i = number; i >= 0; i--) {
    makePrimeArray(i, numberPrime, basePrimeArr);
  }
  for (var prop in basePrime) {
    answer = Math.min(answer, Math.floor(numberPrime[prop] / basePrime[prop])) | 0;
  }
  return answer
}

그래서 base용, number용 소인수 구하는 함수를 나눴다.
굳이 하면 합칠 수 있겠는데… 이 때는 쫄보라서 최대한 속도 높이려고 함수 분리했음 흐훅

이렇게 바꿨더니 기존에 연산 죽던 524288이 0.2s만에 계산되더라. 오예!

pompeu2004’s Solution

이럴 줄 알았어… 남들은 엄청 짧은 코드로 풀 줄…

function zeroes (base, number) {
  var factors = {}, i = 1;
  while(++i <= base) while(base%i == 0) {
    base /= i; 
    factors[i] = (factors[i]||0) + 1;
  }
  return Math.min(...Object.keys(factors).map(factor => {
    var count = 0, i = 1;
    while((i *= factor) <= number) count += number/i>>0;
    return count/factors[factor]>>0;
  }));
}

결론

멍충 인증

Month: September 2017

[일일코딩 #31] 팩토리얼의 0꼬리 구하기

Question

비하인드 스토리

My Answer

pompeu2004’s Solution

결론