[Recursive] isTwoPower?

[Recursive] isTwoPower?

https://www.acmicpc.net/problem/11966

문제

자연수 N이 주어졌을 때, 2의 제곱수면 1을 아니면 0을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 230)이 주어진다.

출력

N이 2의 제곱수면 1을 아니면 0을 출력하는 프로그램을 작성하시오.

재귀를 이용한 2의 제곱수 찾기.

1 <= N < 2^30 까지 들어올 수 있다.

N을 반으로 줄이면서 푸는 방법을 생각했다.

시간 복잡도: O(LogN)

공간 복잡도: O(LogN) 따로 메모리를 사용하지 않았지만, 함수 호출 스택 갯수이다.

#include <iostream>
using namespace std;

int isTwoPower(int n) {
    if(n == 1) return 1;
    else if(n % 2 == 1) {
        return 0;
    }
    return isTwoPower(n/2);
}

int main() {
    int n;

    cin >> n;
    cout << isTwoPower(n) << endl;
    return 0;
}