Binary Representation Palindrome

Easy

Given a positive integer n, determine if its binary representation is a palindrome. Return true if it is a palindrome and false otherwise.

Example 1

Input

[
  1
]

Output

true

Explanation. The binary representation of `1` is `1`, which is a palindrome.

Example 2

Input

[
  5
]

Output

true

Explanation. The binary representation of `5` is `101`, which is a palindrome.

Example 3

Input

[
  12
]

Output

false

Explanation. The binary representation of `12` is `1100`, which is not a palindrome.

Example 4

Input

[
  22
]

Output

false

Explanation. The binary representation of `22` is `10110`, which is not a palindrome.

Example 5

Input

[
  255
]

Output

true

Explanation. The binary representation of `255` is `11111111`, which is a palindrome.

Follow-up: Can you solve the problem without converting the integer to a binary string?

Constraints:

The input integer will always be a positive number.

Solution