(200201_TIL) 'Collatz Conjecture'

▶ Collatz Conjecture

Collatz Conjecture

Collatz Conjecture

(Problem)

Introduction

The Collatz Conjecture or 3x+1 problem can be summarized as follows:

Take any positive integer n.

If n is even, divide n by 2 to get n / 2.

If n is odd, multiply n by 3 and add 1 to get 3n + 1.

 

Repeat the process indefinitely. The conjecture states that no matter which number you start with, you will always reach 1 eventually.

Given a number n, return the number of steps required to reach 1.

 

Examples

Starting with n = 12, the steps would be as follows:

1. 12
2. 6
3. 3
4. 10
5. 5
6. 16
7. 8
8. 4
9. 2
10. 1

Resulting in 9 steps. So for input n = 12, the return value would be 9.

 

- Collatz Conjecture (콜라츠 추측)은 주어진 값을 2로 나눌 수 있으면 나누거나 / 나누어지지 않는 경우에는 3을 곱하고 1을 더하는 과정을 무수히 거치면 1에 도착하게 된다는 것이다.

- 여기에서 1까지 도달하는 데 걸리는 step(단계)가 최종 value 값이 되는 것이다.

 

(Tip)

- 0 과 음수는 주어진 값으로 제공되면 안된다.

=> 처음에 if 문으로 >0 을 걸어주면 될 것으로 보인다.

- 마지막 반환값은 1까지 가는데 걸린 step이 되어야한다.

 

(Solution)

export const steps = (num) => {
    var step = 0;
    if(num<0){
        throw new Error('Only positive numbers are allowed');
    }
    while (num !== 1){
        if(num % 2 === 0){
            num = num/2;
            step++;
        }else{
            num = num * 3  + 1;
            step++;
        }
    }
    return step;
};
 

- step 이라는 변수를 0으로 잡고, num이 1이 될때까지 step++ 하면서, num이 1이 될때 step을 반환해주면 된다.

- 함수를 통해서 받는 num 은 0보다는 커야하기 때문에, 0보다 작은 경우에는 오류를 throw한다.

- while 조건문을 통해서, num이 1이 아니라면 if문을 통해서 ① 2로 나누어지는 경우 ② 2로 나누어지지 않는 경우를 분리하고 해당 조건에 따라서 ① num/2 , ② num*3 +1 을 num 값으로 넣는다.

- 해당 조건문들과 함께 step 을 더해준다. (step++)

- while 문의 조건이 해당될 때, 반복문을 끝내고 step 값을 반환한다.

 

📚 참고

 

developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Statements/while 

while - JavaScript | MDN