[LeetCode] 1404. Number of Steps to Reduce a Number in Binary Representation to One

https://leetcode.com/problems/number-of-steps-to-reduce-a-number-in-binary-representation-to-one/description/

leetcode - Number of Steps to Reduce a Number in Binary Representation to One

문제 유형 : 비트마스킹, 그리디

문제 난이도 : Medium

 

문제

Given the binary representation of an integer as a string s, return the number of steps to reduce it to 1 under the following rules:

• If the current number is even, you have to divide it by 2.
• If the current number is odd, you have to add 1 to it.

It is guaranteed that you can always reach one for all test cases.

 

s에 이진수 문자열이 주어진다.

연산은 다음과 같이 할 수 있다:

- 만약 현재 짝수이면, 2를 나눈다.

- 만약 현재 홀수이면, 1을 더한다.

s를 1로 만들기 위한 연산수를 구하시오.

 

풀이

짝수면 그냥 2로 나누는거지만, 홀수는 1을 더하고 2로 나누어야 한다.

그리고 홀수면, 다음 수로 캐리가 반드시 주어질 것이다.

현재 수가 짝수면, 그냥 연산수를 1 누적,

홀수면 캐리를 1로 조정시키고, 연산수를 2 누적시킨다.(1더함 + 1나눔)

이를 각 자릿수별로 하면 된다.

 

코드

C++

class Solution {
public:
    int numSteps(string s) {
        int n = s.size();
        int ans = 0;
        int carry = 0;

        for (int i = n - 1; i > 0; --i) {
            if ((s[i] - '0' + carry) % 2 == 0) { 
                ans++; 
            } else {
                carry = 1;
                ans += 2;
            }
        }
        return ans + carry; // if carry is 1, we need an extra step to add 1 to the most significant bit
    }
};