N-Parasitic Numbers Ending in N

날짜

2022/02/20

속성

코드워즈

https://en.wikipedia.org/wiki/Parasitic_number

Parasitic Number(기생수)란?

기생수를 찾는 공식

Solution

parasitic 개념 자체는 어렵지만 푸는 방법은 간단하다.

n으로 끝나는 기생수를 구하는 공식

\dfrac{n}{10n -1}

으로 순환소수를 구하고 반복되는 부분을 구하면 된다.

다만 나눗셈, 곱셈 연산 시 너무 길이가 긴 수는 언어 자체에서 잘라버리므로 나눗셈을 직접 구현해야 한다. 따라서 이 솔루션은 8, 10, 16진법의 나눗셈을 구현하는 방법이다.

// find parasitic number ending in n
function calculateSpecial(n, base) {
  let curr=n, decimalStr='', dn=base*n-1,remainder;
  do {
    decimalStr += (~~(curr/dn)).toString(base)
    if (dn <= curr) {
      curr = remainder = curr%dn
    }
    curr *= base
  } while (remainder !== n)
  return decimalStr.slice(1) // excludes integer part
}
JavaScript
복사

•

dn은 denominator(분모)의 약자, remainder는 나머지, period는 반복되는 수의 개수를 의미한다.

•

dn은 기생수의 공식에 따라 10n -1이 된다. 단 여기서는 8, 10, 16진법 모두 구현해야 하므로 base를 곱해준다. base*n - 1

•

parseInt(curr/dn).toString(base) 어제 풀었던 코드에서 16진법 기생수에서 계속 에러가 났는데 이부분 때문이었다. 16진법일 때 몫에서 10이 넘어가는 구간은 a,b,c,d,e 로 바꿔줘야 한다. Math.floor, parseInt, ~~ 연산자로 몫을 구할 수 있는데 구글링을 해보니 ~~ (tlide 연산자)가 제일 빠르다고 한다. (~~(curr/dn)).toString(base) 이렇게 바꿔보았다.

•

do 부분은 나눗셈을 구현한 부분이다. decimalStr에 몫에 해당하는 문자열들을 집어넣는다. 나머지가 다시 처음 수와 같아지면 (remainder===n) 이때부터는 같은 부분이 반복되기 때문에 여기서 break하면 된다.

•

decimalStr.slice(1) parasitic number는 0.xxxx와 같은 형태이다. 정수부를 버리기 위해 slice한다.

Best Practice

const calculateSpecial = (t, i) => {
    let l = 0,
        n = t,
        o = t.toString(i);
    do {
        o += (n = (l = n * t + ~~(l / i)) % i).toString(i)
    } while (l != t);
    return o.slice(1)
}
JavaScript
복사

•

i는 base. n은 현재 수(나눗셈 과정을 거치고 있는 수), t는 입력받은 숫자, l은 나머지, o는 몫에 해당한다. 

•

음.. 왜 이렇게 나온거지? 간결하긴 한데 왜 이렇게 된 건지 모르겠다.