EvenNumbers

https://codefights.com/challenge/4HANW3Rbjcs9TZmMM/main

Author 

gamezovladislav

2000

Number X is called twice even if it is divisible by 2, and number X / 2 is also divisible by 2, yet X / 2 / 2 is not. For example, X = 12 is twice even, since 12 / 2 = 6 - even, and 6 / 2 = 3 is not even.

You're given two numbers: N and P. Find the largest number X, such that 1 ≤ X ≤ P and X is divisible by 2 exactly N times. If there's no such number, return -1instead.

Example

For N = 2 and P = 15, the output should be
EvenNumbers(N, P) = 12.

12 / 2 = 6 and 6 / 2 = 3, which is not even.

Input/Output

• [time limit] 500ms (cpp)

• [input] integer N

  Constraints:
  0 ≤ N ≤ 30.

• [input] integer P

  Constraints:
  1 ≤ P ≤ 2 · 109.

• [output] integer

  The largest number X, such that 1 ≤ X ≤ P and X is divisible by 2 exactlyN times. If this number does not exist return -1 instead.

* 이 문제에 주목하는 이유 *

문제 유형중에 이런 유형이 많다.

"어떤 정수 P가 주어졌을때, P보다 크지 않으면서 ~~~조건을 만족하는 최대의 정수를 찾아라."

당장 떠오르는 해결방법은 P에서 하나씩 값을 감소해나가면서 조건을 만족하는지 계속 검사하는 것인데

이 방법으로 풀면 시간 제한때문에 번번히 실패한다.

실제로 이 문제를 해결하기 위해 다음과 같이 코드를 짰지만 시간 제한 초과로 실패했다.

int EvenNumbers(int N, int P) {

    int n = int(pow(2,N));

    while (P>0) {

        if(P%n ==0 && (P/n)%2 != 0) return P;            

        P--;

    }

    

    return -1;

}

그럼 어떤 식으로 해야하는걸까?

예제 답안1)

int EvenNumbers(int N, int P) {

    int t = pow(2,N);

    for(int i=P/t; i>=1; i--){

        if(i%2!=0){

            return i*t;

        }

    }

    return -1;

}

조금의 수학적인 계산으로 for문의 범위를 확실하게 줄였다.