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

Encrypt and Decrypt Strings

You are given a character array keys containing unique characters and a string array values containing strings of length 2. You are also given another string array dictionary that contains all permitted original strings after decryption. You should implement a data structure that can encrypt or decrypt a 0-indexed string. A string is encrypted with the following process: For each character c in the string, we find the index i satisfying keys[i] == c in keys . Replace c with values[i] in the string. Note that in case a character of the string is not present in keys , the encryption process cannot be carried out, and an empty string "" is returned. A string is decrypted with the following process: For each substring s of length 2 occurring at an even index in the string, we find an i such that values[i] == s . If there are multiple valid i , we choose any one of them. This means a string could have multiple possible strings it can decrypt t...
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

Minimum Sum of Four Digit Number After Splitting Digits

You are given a positive integer num consisting of exactly four digits. Split num into two new integers new1 and new2 by using the digits found in num . Leading zeros are allowed in new1 and new2 , and all the digits found in num must be used. For example, given num = 2932 , you have the following digits: two 2 's, one 9 and one 3 . Some of the possible pairs [new1, new2] are [22, 93] , [23, 92] , [223, 9] and [2, 329] . Return the minimum possible sum of new1 and new2 .   Example 1: Input: num = 2932 Output: 52 Explanation: Some possible pairs [new1, new2] are [29, 23], [223, 9], etc. The minimum sum can be obtained by the pair [29, 23]: 29 + 23 = 52. Example 2: Input: num = 4009 Output: 13 Explanation: Some possible pairs [new1, new2] are [0, 49], [490, 0], etc. The minimum sum can be obtained by the pair [4, 9]: 4 + 9 = 13.   Constraints: 1000 <= num <= 9999 SOLUTION: class Solution : def minimumSum ( self,...
Read more