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

Daily Codewars #31 Factorial Tail

Question

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

codewars link

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 * 5B10C가 저 안에 있으면 되지 않을까?
그럼 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;
}

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

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;
  }));
}

결론

멍충 인증

Advertisements

[일일코딩 #30] javascript IP validation

Daily Codewars #30

Question

codewars link
Write an algorithm that will identify valid IPv4 addresses in dot-decimal format. Input to the function is guaranteed to be a single string.

Examples of valid inputs: 1.2.3.4 123.45.67.89

Examples of invalid inputs: 1.2.3 1.2.3.4.5 123.456.78.90 123.045.067.089

ip주소 validation을 하는 문제다. 참고로 0<=숫자 이게 왜 4kyu이지? 그리고 이제 honor가 113정도 되니 4큐 풀어봤자 2밖에 안오르네. 흑흑

my Solution

function isValidIP(str) {
  var arr = str.split('.');
  if(arr.length == 4) {
    return validLen = arr.filter(function(x) {
      return x !== (+x).toString() ? false : x>=0 && x<=255 ? true : false;
    }).length == arr.length;
  }
  return false;
}

split으로 나눠서 삼항연산자로 비교했다.
지금 보니 arr.length랑 filter로 나온 length를 비교할 필요 없이 그냥 4면 되는건데 바보바보 인증.

ryanzyy’s Solution

function isValidIP(str) {
  return /^(([1-9]?d|1dd|2[0-4]d|25[0-5])(.(?!$)|$)){4}$/.test(str);
}

으익 나도 정규식으로 풀걸. 그리 복잡하지 않았을텐데!

yaphi1’s Solution

function isValidIP(str) {
  return str.split('.').filter(function(v){return v==Number(v).toString() && Number(v)<256}).length==4;
}

앗 맞아(+x)라고 할필요 없었는데! 그리고 3항연산도 할필요 없었는데!
바보바보 인증

[일일코딩 #29] javascript 배열의 언덕 꼭대기 구하기

Daily Codewars #29

Question

codewars link
In this kata, you will create an object that returns the positions and the values of the “peaks” (or local maxima) of a numeric array.

For example, the array arr = [ 0 , 1 , 2 , 5 , 1 , 0 ] has a peak in position 3 with a value of 5 (arr[3] = 5)

The output will be returned as an object with two properties: pos and peaks. Both of these properties should be arrays. If there is no peak in the given array, then the output should be {pos: [], peaks: []}.

Example: pickPeaks([3,2,3,6,4,1,2,3,2,1,2,3]) returns {pos:[3,7],peaks:[6,3]}

All input arrays will be valid numeric arrays (although it could still be empty), so you won’t need to validate the input.

The first and last elements of the array will not be considered as peaks (in the context of a mathematical function, we don’t know what is after and before and therefore, we don’t know if it is a peak or not).

Also, beware of plateaus !!! [1,2,2,2,1] has a peak while [1, 2, 2, 2, 3] does not. In case of a plateau-peak, please only return the position and value of the beginning of the plateau. For example: pickPeaks([1,2,2,2,1]) returns {pos:[1],peaks:[2]}

have fun!

배열에서 언덕을 찾아 그 수와 index를 찾는 문제이다.
고원이면 고원이 생긴 처음 수와 index를 반환한다.

My Solution

function pickPeaks(arr){
  var pSlope = 0, pi = 0;
  var result = {pos:[],peaks:[]};
  if(arr.length==0) return result;

  arr.reduce(function(p, c, i) {
    if(pSlope>0 && c-p<0) {
      result.peaks.push(p);
      result.pos.push(pi);
    }
    if(c-p != 0){
      pi = i;
      pSlope = c-p;
    }
    return c;
  });
 return result;
}

Array.reduce로 current-prev 기울기를 저장했다.
기울기가 양수에서 음수로 바뀌면 그 때를 result에 저장한다.
0이 아닐때만 i와 previous Slope를 저장한다.

manvel7650’s Solution

function pickPeaks(arr){
  var result = {pos: [], peaks: []};
  if(arr.length > 2) {
    var pos = -1;
    for(var i=1; i<arr.length;i++){
      if(arr[i] > arr[i-1]) {
        pos = i;
      } else if(arr[i] < arr[i-1] && pos != -1) {
        result.pos.push(pos);
        result.peaks.push(arr[pos]);
        pos = -1;
      }
    }
  }
  return result;
}

for문을 돌려서 풀었구낭.

[일일코딩 #28] javascript 배열에서 소인수 뽑아내기

Daily Codewars #28

Question

codewars link
Given an array of positive or negative integers

I= [i1,..,in]

you have to produce a sorted array P of the form

[ [p, sum of all ij of I for which p is a prime factor (p positive) of ij] ...]

P will be sorted by increasing order of the prime numbers. The final result has to be given as a string in Java or C# and as an array of arrays in other languages.

Example:

I = [12, 15] 
result = [[2, 12], [3, 27], [5, 15]]

[2, 3, 5] is the list of all prime factors of the elements of I, hence the result.

Note: It can happen that a sum is 0 if some numbers are negative!

Example: I = [15, 30, -45] 5 divides 15, 30 and (-45) so 5 appears in the result, the sum of the numbers for which 5 is a factor is 0 so we have [5, 0] in the result amongst others.

소인수를 구하고, 공통된 소인수를 가진 수들을 더해 각각 반환하는 문제다.

My Solution

function sumOfDivided(lst) {
  var commonArr = [];
  var pfsArr = [];

  for(i in lst) {
    var num = lst[i];
    var pfArr = [];
    var pf = 2;

    function recur(n) {
      if(n%pf==0) {
        if(pfArr.indexOf(pf)<0) pfArr.push(pf);
        if(commonArr.indexOf(pf)<0) commonArr.push(pf);
        n = n/pf;
        pf=2;
      } else pf++;
      if(pf>Math.abs(n))return;
      recur(n);
    }

    recur(num);
    pfsArr.push(pfArr);
  }

  return commonArr.sort(function(a,b){return a-b;}).map(function(cPf){
    var sum = 0;
    pfsArr.forEach(function(pPf, pIdx){
      if(pPf.indexOf(cPf)>=0) sum+=lst[pIdx];
    });
    return [cPf, sum];
  });
}

배열을 세개 만들었다.
– pfArr: 주어진 배열 인자의 소인수 배열
– commonArr: 그 소인수들을 중복 없이 모은 배열
– pfsArr: pfArr들이 들어가있는 배열
여기서 commonArr에 map을 돌려 pfsArr에 특정 소인수가 있는지 판별하고, 있으면 더해서 두번째 인자에 넣어준다.
배고프다. 저녁 안먹음.

@Hex-a’s Solution

function sumOfDivided(lst) {
    if(lst.length == 0) { return []; }
    var m = Math.max.apply(null, lst.map(Math.abs)),
        primes = [],
        marked = Array(m+1);

    for(var i = 2; i <= m; ++i) {
        if(marked[i]) continue;

        var sum = 0, isMul = false;
        lst.forEach(function(n) { if(n % i == 0) { sum += n; isMul = true; } });
        if(isMul) primes.push([i, sum]);

        for(var j = 2*i; j <= m; j += i) {
            marked[j] = true;
        }
    }

    return primes;
}

@7nik’s Solution

function sumOfDivided(lst) {
  console.log(lst);
  var max = lst.reduce(function(m,v){return m>v?m:v;}, lst[0]);
  var min = lst.reduce(function(m,v){return m<v?m:v;}, lst[0]);
  max = Math.max(max, -min);
  console.log(max);
  var primes = [];
  for (var i = 2; i <= max; i++) {
    if (primes.every( function (prime) { return i % prime; }) &&
        lst.some(function (val) { return !(val % i); })) {
      primes.push(i);
    }
  }
  console.log(primes);
  var result = primes.map(function(prime) {
      return [prime, lst.reduce(function(sum, num) {
          return sum + (num % prime ? 0 : num);
        }, 0)];
    });
  return result;
} 

다들 많이 다르게 풀었네.

[일일코딩 #27] javascript Array 값으로 초기화하기

Daily Codewars #27

Question

codewars link
Create the function prefill that returns an array of n elements that all have the same value v. See if you can do this without using a loop.

You have to validate input:

v can be anything (primitive or otherwise)
if v is ommited, fill the array with undefined
if n is 0, return an empty array
if n is anything other than an integer or integer-formatted string (e.g. ‘123’) that is >=0, throw a TypeError
When throwing a TypeError, the message should be n is invalid, where you replace n for the actual value passed to the function.

Code Examples

prefill(3,1) --> [1,1,1]

prefill(2,"abc") --> ['abc','abc']

prefill("1", 1) --> [1]

prefill(3, prefill(2,'2d'))
  --> [['2d','2d'],['2d','2d'],['2d','2d']]

prefill("xyz", 1)
  --> throws TypeError with message "xyz is invalid"

1번째 인자만큼 2번째 인자로 배열을 채우는 문제이다.

My Solution

function prefill(n, v) {
  try {
    var arr = Array.apply(null, Array(typeof n=='boolean'? parseInt(n): +n));
    return arr.map(function() {
      return v;
    });
  } catch (e) {
    throw new TypeError(n+' is invalid');
  }
}

try catch문을 직접 써본건 처음이다!
Array.apply(null, Array(5))와 같이 배열을 초기화한다.
그냥 new Array(3)하면 length는 3이지만 생긴건 []인 배열이 나오니까.
그리고 맵 돌려줬다.

@abhiaiyer91’s Solution

function prefill(num, value) {
  if(typeof num === 'boolean' || ~~num != num || +num < 0) throw new TypeError(num + ' is invalid')
  return Array.apply(null, Array(+num)).map(function (d,i) { return value })
}

같은 방식으로 map을 돌려주되, 앞에 boolean, float등을 처리하는 if를 넣어주었다 . 그냥 throw를 던지면 되는구나.

@handyCAPS's Solution

function prefill(n, v) {
  if (/\D/g.test(n) || n < 0) {throw new TypeError(n + ' is invalid')}
  return Array.apply(null, new Array(parseInt(n, 10))).map(function() {return v;});
}

이사람은 정규표현식으로 처리!


레벨 빨리 올려본다고 3kyu짜리 문제 풀다가 gg치고 다시 돌아왔다.
실력이 많이 부족하구나. 무엇이든 꾸준히.

[일일코딩 #26] javascript 이상한 Hello World! 출력 (미해결)

Daily Codewars #26

Question

codewars link
In order to stop too much communication from happening, your overlords declare that you are no longer allowed to use certain functionality in your code!

Disallowed functionality:

  • Strings
  • Numbers
  • Regular Expressions
  • Functions named “Hello”, “World”, “HelloWorld” or anything similar.
  • Object keys named “Hello”, “World”, “HelloWorld” or anything similar.
    Without using the above, output the string “Hello World!” to prove that there is always a way.

String, Numbers, Regex, 그리고 hello world랑 비슷한 문자가 들어가는 function, object key를 쓰지 말고 Hello world!를 출력하는 문제이다.

My Solution

var abc = function() {
  var obj = {
    dlroW:x, olleH:hello}
  var x = new String();
  String.constructor = Object.keys(obj).shift();
  console.log(x.constructor);
  var w1 = Object.keys(obj).shift();
}
var helloWorld = abc;

object의 키값으로 넣고, 그걸 reverse하는 식으로 해볼까 했는데.
계속 걸림돌이 되는 ‘!’의 문제.
결국 이 문제는 잠시 keep해놓기로… ㅠㅠ 빠가야로

[일일코딩 #25] javascript String에서 String 찾기

Daily Codewars #25

Question

codewars link
Complete the solution so that it returns the number of times the search_text is found within the full_text.

searchSubstr( fullText, searchText, allowOverlap = true )

so that overlapping solutions are (not) counted. If the searchText is empty, it should return “0”. Usage examples:

searchSubstr('aa_bb_cc_dd_bb_e', 'bb') # should return 2 since bb shows up twice
searchSubstr('aaabbbcccc', 'bbb') # should return 1
searchSubstr( 'aaa', 'aa' ) # should return 2
searchSubstr( 'aaa', '' ) # should return 0
searchSubstr( 'aaa', 'aa', false ) # should return 1

My Solution

function searchSubstr(fullText, searchText, allowOverlap ){
  var count=0, sIdx=0;
  for(i in fullText){
    var cIdx = fullText.indexOf(searchText, sIdx);
    sIdx = allowOverlap==false? cIdx+searchText.length+1 : cIdx+1;
    if(cIdx<0) return count;
    count++;
  }
  return 0;
}

최대로 fullText.length만큼 for를 돈다.
거기서 allowOverlap에 따라 String.indexOf의 두번째 인자에 시작위치를 바꿔줘가며 돌린다.

@Azuaron’s Solution

function searchSubstr(fullText, searchText, allowOverlap) {
  if(searchText == '') return 0;
  var re = new RegExp(searchText, 'g');
  if(allowOverlap) {
    var count = 0;
    while(re.exec(fullText)) {count++; re.lastIndex -= searchText.length - 1;}
    return count;
  } else return (fullText.match(re) || []).length || 0;
}

false일땐 일단 정규표현식으로 간단히 리턴하고,
true면 re.lastIndex -= searchText.length - 1로 lastIndex를 바꿔준다.

@kumorig’s Solution

function searchSubstr( t, s, o ){
  return(t.length===0||s.length===0)?0:t.match(new RegExp((o||(o==undefined))?"(?=("+s+"))":t,"g")).length; 
}

헤헤…정규식…이전 회사에 다녔던 분 이름인 정규식…