nikoo28

Given a number ‘n’, how to check if n is a Fibonacci number. A simple way is to generate Fibonacci numbers until the generated number is greater than or equal to ‘n’. Following is an interesting property about Fibonacci numbers that can also be used to check if a given number is Fibonacci or not. A number is Fibonacci if and only if one or both of 5n2+4 or 5×2-4 is a perfect square (Source: Wikipedia). Following is a simple program based on this concept. Output:- 1 is a Fibonacci…

Question: Suppose you are given a Linked List as 45-> 123-> 87-> 11-> 53-> 24-> 412-> 22. And we have to find the nth node from the end. Input:- n = 3 Output:- 24 BRUTE FORCE APPROACH:- In this method, start with the first node and count how many nodes are there after that node. If the number of nodes are < n-1, then return saying, “fewer number of nodes in the list.” If the number of nodes are > n-1 then go to the next node. Continue this until…

We covered some of the basic operations on a Linked List in this post. Basic operations on a Linked List However, in order to create a functional Linked List, we need even more operations before we can proceed further. Some of these operations are:- Inserting a node in the beginning of the Linked List. Inserting a node in the middle of a List. Inserting at a certain position Inserting after a specific node. Deleting a node from the Linked List. Deleting the entire Linked List. Inserting a node in the…

Here are some of the basic operations on a singly Linked List. Creating a new List Adding new elements Traversing a List Printing a List Basic functions to perform the above techniques have been defined in the code below. Creating a new list A new Linked List creation means that we do not have any elements in the list and we want to start fresh. This means allocating space in the memory for a node and then inserting the data into it. Since only a single node is created, the…

Linked List is a data structure used to store collections of data where successive elements are connected by pointers. It is really helpful to perform faster and memory efficient operations. This post gives you an introduction to all that with a video explanation.

So if you supply n = 4 in the function what you get as the output is this. 0000 1000 0100 1100 0010 1010 0110 1110 0001 1001 0101 1101 0011 1011 0111 1111 You can download the code here.

Backtracking is the method of exhaustive search using divide and conquer. Sometimes the best algorithm for a problem is to try all the possibilities. This is always slow, but there are standard tools that can be used for help. Tools: algorithms for generating basic objects, such as binary strings [2n possibilities for n-bit string], permutations [n!], combinations [n!/r!(n-r)!], general strings [k-ary strings of length  n has kn possibilities], etc… Backtracking speeds the exhaustive search by pruning. Example Algorithms of Backtracking Binary Strings: generating all binary strings Generating k-ary Strings. The…

The tower of Hanoi is a mathematical puzzle. It consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks on one rod in ascending order of size, the smallest at the top, thus making a conical shape. The objective of the puzzle is to move the entire stack to another rod, satisfying the following rules:- Only one disk can be moved at a time. Each move consists of taking the upper disk from one of the…

Each recursive call makes a new copy of that method (more specifically speaking ‘the variables’) in memory. Once a method ends (i.e returns some data), the copy of that returning method is removed from the memory. The recursive solutions look simple but visualization and tracing takes time. For better understanding, let us see the following example. For this example. if we call the print function with n = 4, visually our memory assignment may look like this:- Now, let us consider our factorial function. The visualization of this will be:-

What is Recursion? Any function which calls itself is called a recursive function. A recursive method solves a problem by calling a copy of itself to work on a smaller problem. This is called the recursion step. The recursion step can result in many more such recursive calls. It is important to ensure that the recursion terminates. Each time the function calls itself with a slightly simpler version of the original problem. The sequence of smaller problems must eventually converge on the base case. Why Recursion? Recursion is a useful…