Problem Given a (decimal – e.g. 3.72) number that is passed in as a string, print the binary representation. If the number can not be represented accurately in binary, print “ERROR”. Examples Example 1: Input: num = 3.625 Output: 11.101 Example 2: Input: num = 3.26 Output: ERROR Explanation: There are accuracy issues with floating point numbers. ...
Problem Given a set of distinct integers/characters, S, return all possible subsets. OR Given an integer array nums of unique elements, return all possible subsets (the power set). Examples If we’re given a set of integers such that S = {1, 2, 3}, how can we find all the subsets of that set? For example, given S, the set of all subsets i.e. P(S) we get are {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, and {1, 2, 3}. Here is {} is empty set denoted by Φ. ...
Problem Given an array of integers, every element appears twice except for one. Find that single one. Examples Example 1: Input: nums = [2,2,1] Output: 1 Example 2: Input: nums = [4,1,2,1,2] Output: 4 Example 3: Input: nums = [1] Output: 1 ...
Problem An array A[1..n] contains all the integers from 0 to n except for one number which is missing. In this problem, we cannot access an entire integer in A with a single operation. The elements of A are represented in binary, and the only operation we can use to access them is ”fetch the jth bit of A[i]”, which takes constant time. Write code to find the missing integer. Can you do it in O(n) time? ...
Problem Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order. You must write an algorithm that runs in linear runtime complexity and uses only constant extra space. Examples Example 1: Input: nums = [1,2,1,3,2,5] Output: [3,5] Explanation: [5, 3] is also a valid answer. ...
Problem Explain what the following code does: ((n & (n-1)) == 0). Solution When we have A & B == 0, it means that A and B have no common 1s, i.e. any two bits at the same positions of A and B are either different from each other, or two 0s. It works because a binary power of two is of the form 1000…000 and subtracting one will give you 111…111. Then, when you AND those together, you get zero, such as with: ...
Problem Given an integer n, return true if it is a power of two. Otherwise, return false. An integer n is a power of two, if there exists an integer x such that n == 2^x. Examples Example 1: Input: n = 1 Output: true Explanation: 20 = 1 Example 2: ...
What is x - 1 wrt x x - 1 is derived from x by flipping all bits to the right of (and including) the rightmost set bit (1) in x to 0s. Examples x = 4 (100 in binary), x - 1 = 3 (011 in binary). x = 6 (110 in binary), x - 1 = 5 (101 in binary). What is X & (x-1)? x & (x - 1) results in a value with all bits from x remaining the same except for the rightmost set bit (1), which becomes 0. ...
Problem Write a function that takes the binary representation of a positive integer and returns the number of set bits it has (also known as the Hamming weight). Note: Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer’s internal binary representation is the same, whether it is signed or unsigned. In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 3, the input represents the signed integer. -3. Examples Example 1: ...
Problem Write a function to swap two number in place without temporary variables. Solution Method1 - The XOR or Exclusive trick In C this should work: a ^= b ^= a ^= b; to simplify : a=a^b; b=a^b; a=a^b; ...