티스토리 뷰

Algorithm/LeetCode

342. Power of Four

Jaime.Lee 2022. 8. 26. 10:30

소스 코드는 여기 있습니다.
문제는 여기 있습니다.

Problem

Given an integer n, return true if it is a power of four. Otherwise, return false.

An integer n is a power of four, if there exists an integer x such that n == 4x.

Example 1:

Input: n = 16
Output: true

Example 2:

Input: n = 5
Output: false

Example 3:

Input: n = 1
Output: true

Constraints:

-2^31 <= n <= 2^31 - 1

Solution

정수 n이 주어졌을 때 4의 제곱이면 true를 반환하는 문제입니다.

4의 제곱을 2진수로 표현하면 아래와 같습니다.

1   = 1
4   = 100
16  = 10000
64  = 1000000
256 = 10000000
...

1 이후 0이 두 개씩 증가하는 것을 확인할 수 있습니다.

따라서 1이 맨 앞에 한 개 존재하고 나머지가 0이며 0의 개수가 2의 배수이면 4의 제곱입니다.

public class Solution {

  public boolean isPowerOfFour(int num) {
    int numberOfZeros = 0;
    int numberOfOnes = 0;
    while (num > 0) {
      if ((num & 1) == 1) { // 마지막 자리 수가 1이면
        numberOfOnes++;
      } else { // 마지막 자리 수가 0이면
        numberOfZeros++;
      }
      num >>= 1; // 오른쪽으로 한 칸 bit shift
    }
    return numberOfOnes == 1 && (numberOfZeros % 2 == 0);
  }
}

Test

package io.lcalmsky.leetcode.power_of_four;

import static org.junit.jupiter.api.Assertions.assertAll;
import static org.junit.jupiter.api.Assertions.assertEquals;

import org.junit.jupiter.api.Test;

class SolutionTest {

  @Test
  void testAll() {
    assertAll(
        () -> test(16, true),
        () -> test(5, false),
        () -> test(1, true)
    );
  }

  private void test(int given, boolean expected) {
    // when
    Solution solution = new Solution();
    boolean actual = solution.isPowerOfFour(given);
    // then
    assertEquals(expected, actual);
  }
}

'Algorithm > LeetCode' 카테고리의 다른 글

383. Ransom Note  (0) 2022.08.29
326. Power of Three  (0) 2022.08.27
234. Palindrome Linked List  (0) 2022.08.25
871. Minimum Number of Refueling Stops  (0) 2022.08.20
1338. Reduce Array Size to The Half  (0) 2022.08.19
댓글