Arrays: Merge sorted array inplace
Problem Statement: You are given with 2 sorted arrays, you need to merge the array in-place. You may assume that the first array will have enough space to accomodate all the array elements. Example: Input: arr1 = [1,2,3] arr2 = [2,5,6] Output: [1,2,2,3,5,6] According to the question, we can assume that the first array will […]
Power Set
Problem Statement: You are given a set, you need to find all the subsets of that set. Example set = {a, b, c} Power set = {{}, {a}, {b}, {c}, {a, b}, {a,c}, {b, c}, {a, b, c}} Solution The solution is very simple. First we get the size of the power set. We get […]
Copy set bits in a range
Problem Statement: You are given 2 numbers x and y and a range [i,r] 1 <= l, r <= 32. You need to set bits of y in range [l, r] that are set bits in x. Example A = 10101110101 B = 10010011001 L = 3 R = 7 As we need to copy […]
Bitwise Set bit questions
Problem Statement: In this chapter we shall solve few problems related to Bitwise Set bit. 1. Find the total number of set bits from 1 to N 2. Find the position of the only set bit 3. Find if two numbers differ at one bit position only Find the total number of set bits from […]
Count number of bits to be flipped to convert A to B
Problem Statement: You are given 2 integers A and B. You need to findout the number of bits to be flipped to convert A to B. Example Input : a = 10, b = 20 Output : 4 Binary representation of a is 00001010 Binary representation of b is 00010100 a XOR b =00011110 The […]
Find the two non repeating numbers.
Problem Statement: You are given an array of repeating numbers(twice), but two numbers are not repeating. You need to find out those numbers. Example Input: {1, 1, 2, 3, 2, 3, 4, 5} Output: 4, 5 Solution The solution is very simple. Below are the steps we use to achieve the solution. We use XOR […]
Dynamic Programming: Equal Sum partition
Problem Statement: You are given an array. You need to return true if you are able to divide the array into 2 subsets such that the sum of the elements are same. Example Input: arr[] = {1, 5, 11, 5} Output: True We can partition array as {1, 5, 5} and {11} Solution This problem […]
Dynamic Programming: Unbounded Knapsack Problem
Problem Statement: You are given 2 arrays. Value array and corresponding weight associated with it. You need to calculate the maximum amount that could make up for the total knapsack weight W. The only difference from 0/1 knapsack problem is that, here the repetitions of the items are allowed. Example Input : W = 100 […]
Dynamic Programming: Subset sum problem
Problem Statement: You are given a non-negtive integers and a sum, you need to check if there is a subset with the sum equal to the given sum. Example Input: arr = {1, 2, 3, 4, 5} sum = 9 Output: True Because there is a subset {4, 5} with the sum = 9 Solution […]
Dynamic Programming: Get the nth catalan number
Problem Statement: You are given an integer “n”, you need to get the “nth” catalan number. What is a Catalan Number? A catalan number are a sequence of natural number that occur in a specific sequence. So the catalan number are: C(0) = 1 C(1) = 1 C(2) = 2 C(3) = 5 C(4) = […]