Power of Two Difference

Power of Two Difference

Power of Two Difference

Problem Description

Given an integer n, return true if it is a possible difference between powers of two. Otherwise, return false.

An integer n is a difference between powers of two if there exist two integers x and y, where x >= y >= 0, such that n == 2^x - 2^y.

Solution Approach

The problem can be solved using an elegant solution. We can observe that if n = 2^x - 2^y, then n = 2^y * (2^(x-y) - 1). Let's call y as M and x - y as N. Now, we observe that 2^N - 1 is a binary number of the form 111...111, where 1 is repeated N times. Multiplying a binary number by 2^M will add 0 M times to the right. Therefore, our result is of the form 11...1100...00, where 1 is repeated some times followed by 0 repeated some times or 0 times. For example, 0 is true, 7 is true because it's 111, 12 is true because it's 1100, whereas 5 is false because it's 101 and 13 is false because it's 1101.

To solve the problem, we need to find the binary expansion of N and check if it's of the form 11...1100...000.

Playground Link

You can access the playground link that includes the solution code.

Example Test Cases

Test Case 1:

Input:
n = 0

Output:
true

Explanation:
0 = 2^0 - 2^0

Test Case 2:

Input:
n = 12

Output:
true

Explanation:
12 = 2^4 - 2^2

Test Case 3:

Input:
n = 7

Output:
true

Explanation:
7 = 2^3 - 2^0

Test Case 4:

Input:
n = 5

Output:
false

Explanation:
It is not possible to represent 5 as a difference of powers of 2.

Tags

Math, Bit Manipulation

Comments

Post a Comment

Popular posts from this blog

Lazy Deletion in Heap: A Wrapper for Python heapq

Lazy Deletion in Heap: A Wrapper for Python heapq Lazy Deletion in Heap: A Wrapper for Python heapq In many programming scenarios, we often encounter situations where we need to maintain a heap data structure and perform operations such as insertion, deletion, and retrieval of the minimum element efficiently. Python provides a built-in module called heapq that offers heap operations. However, the standard heapq module does not provide direct support for lazy deletion, which can be useful in certain cases. In this article, we will explore a wrapper class, Heap , that extends the functionality of the Python heapq library to support lazy deletion in a heap. The Heap Class The Heap class is a wrapper that encapsulates the heapq module to enable lazy deletion in a heap. Let's go through its main methods and their functionalities: __init__(self) : Initializes the Heap instance by creating an empty heap and a defaultdict to track the deleted elements ...
Read more

Sliding Window GCD

Sliding Window GCD Sliding Window GCD Problem Description You are given an array of integers nums of length N . There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return an array of length N - k + 1 representing the GCD of each subarray of length k from left to right. Solution Approach The solution to this problem involves implementing a special queue data structure using two stacks. This special queue allows the push , pop , and GCD operations in O(1) amortized time complexity. The implementation of this queue is based on the combination of two existing techniques: implementing a queue using stacks and implementing a stack that stores GCD values. By using this special queue, we can efficiently calculate the GCD for each sliding window in O(N) time complexity. This technique is useful to understand the impl...
Read more

Degree of an Array

Given a non-empty array of non-negative integers nums , the degree of this array is defined as the maximum frequency of any one of its elements. Your task is to find the smallest possible length of a (contiguous) subarray of nums , that has the same degree as nums .   Example 1: Input: nums = [1,2,2,3,1] Output: 2 Explanation: The input array has a degree of 2 because both elements 1 and 2 appear twice. Of the subarrays that have the same degree: [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2] The shortest length is 2. So return 2. Example 2: Input: nums = [1,2,2,3,1,4,2] Output: 6 Explanation: The degree is 3 because the element 2 is repeated 3 times. So [2,2,3,1,4,2] is the shortest subarray, therefore returning 6.   Constraints: nums.length will be between 1 and 50,000. nums[i] will be an integer between 0 and 49,999. SOLUTION: from collections import defaultdict class Solution : def findShortestSubArr...
Read more