While solving a problem using recursion, we break the given problem into smaller ones. Let's say we have a problem AA and we divided it into three smaller problems BB, CC and DD. Now it may be the case that the solution to AA does not depend on all the three subproblems, in fact we don't even know [...]
Given a list of n-1 integers and these integers are in the range of 1 to n. There are no duplicates in list. One of the integers is missing in the list. Find the missing integer. Missing number can be found as using XOR. (PARTIAL_SUM) XOR (MISSING_ELEMENT) = (TOTAL_SUM) => [...]
Let' there are coins from 1 to N and the sum you are trying to get is SUM. Problem is basically finding in how many ways we can make the sum SUM using coins that have numbers from 1 to N. This problem can be solved using dynamic programming. Instead of thinking about [...]
What’s the angle between the hour hand and the minute hand at 3:45 pm? The minute hand is at 9 that is at 270 degrees from 12. The hour hand is between 3 and 4. The hour hand covers 30 degrees in 60 minutes and so in 45 minutes it [...]
A child going up a staircase with n steps, can hop up 1, 2, or 3 steps at a time. How many ways can the child reach the top? If there are zero steps, then there is one way for the child to climb the steps (i.e., do nothing.) If [...]
Power set i.e all subset of a set can be found by Using Tree representation approach Using Bit manipulation approach Tree Representation Approach There are 2 possibilities for each item of a set, It will be either included in a subset or not included. Based on this fact, Lets [...]
The partition problem is the task of deciding whether a given set S of positive integers can be partitioned into two subsets S1 and S2 such that the sum of the numbers in S1 equals the sum of the numbers in S2. Given a set, find out if it can [...]
Prefix sum is the cumulative sum of a sequence of numbers a0, a1, ... . It is itself a sequence of numbers b0, b1, ... such that PreSum0 = a0 PreSum1 = a0 + a1 = PreSum0 + a1 PreSum2 = a0 + a1 + a2 = PreSum1 + a2 . . . . . . . . . PreSumn=PreSumn-1+an [...]
Dynamic programming, like the divide-and-conquer method, solves problems by combining the solutions to subproblems. Divide-and-conquer algorithms partition the problem into independent subproblems, solve the subproblems recursively, and then combine their solutions to solve the original problem. In contrast, dynamic programming is applicable when the subproblems are not independent, that is, [...]
Graph can be traversed using Depth First Traversal or DFS Breadth First Traversal or BFS Depth First Traversal The DFS algorithm is a recursive algorithm that uses the idea of backtracking. It involves exhaustive searches of all the nodes by going ahead, if possible, else by backtracking. Here, the word [...]