Skip to main content

Posts

Array Rotation

 To  Write a function rotate(ar[], d, n) that rotates arr[] of size n by d elements.  To rotate by one, store arr[0] in a temporary variable temp, move arr[1] to arr[0], arr[2] to arr[1] …and finally temp to arr[n-1] Let us take the same example arr[] = [1, 2, 3, 4, 5, 6, 7], d = 2  Rotate arr[] by one 2 times  We get [2, 3, 4, 5, 6, 7, 1] after first rotation and [ 3, 4, 5, 6, 7, 1, 2] after second rotation. Below is the implementation of the above approach :  LinkedList is not passing from the arrauyhjicheichdsbcjshjbj cjechkcbndkbckjnk // C++ program to rotate an array by // d elements #include <bits/stdc++.h> using namespace std; /*Function to left Rotate arr[] of size n by 1*/ void leftRotatebyOne(int arr[], int n) { int temp = arr[0], i; for (i = 0; i < n - 1; i++) arr[i] = arr[i + 1]; arr[n-1] = temp; } /*Function to left rotate arr[] of size n by d*/ void leftRotate(int arr[], int d, int n) { for (int i = 0; i < d; i++) leftRotatebyOne(arr, n); } /* ut

What is Array

  An array is a collection of items stored at contiguous memory locations. The idea is to store multiple items of the same type together. This makes it easier to calculate the position of each element by simply adding an offset to a base value, i.e., the memory location of the first element of the array (generally denoted by the name of the array). The base value is index 0 and the difference between the two indexes is the offset. For simplicity, we can think of an array as a fleet of stairs where on each step is placed a value (let’s say one of your friends). Here, you can identify the location of any of your friends by simply knowing the count of the step they are on.  Remember: “Location of next index depends on the data type we use”.  The above image can be looked at as a top-level view of a staircase where you are at the base of the staircase. Each element can be uniquely identified by its index in the array (in a similar way as you could identify your friends by the step on which

About Us

       A team of dedicated and experienced software engineers sharing their knowledge and experience on a regular basis.

Optimal Substructure Property in Dynamic Programming

  As we discussed in   Set 1 , following are the two main properties of a problem that suggest that the given problem can be solved using Dynamic programming:  1) Overlapping Subproblems  2) Optimal Substructure  We have already discussed Overlapping Subproblem property in the  Set 1 . Let us discuss Optimal Substructure property here.  2) Optimal Substructure:  A given problems has Optimal Substructure Property if optimal solution of the given problem can be obtained by using optimal solutions of its subproblems.  For example, the Shortest Path problem has following optimal substructure property:  If a node x lies in the shortest path from a source node u to destination node v then the shortest path from u to v is combination of shortest path from u to x and shortest path from x to v. The standard All Pair Shortest Path algorithm like  Floyd–Warshall  and Single Source Shortest path algorithm for negative weight edges like  Bellman–Ford  are typical examples of Dynamic Programming.  O

Overlapping Subproblems Property in Dynamic Programming

  Dynamic Programming is an algorithmic paradigm that solves a given complex problem by breaking it into subproblems and stores the results of subproblems to avoid computing the same results again. Following are the two main properties of a problem that suggests that the given problem can be solved using Dynamic programming. In this post, we will discuss the first property (Overlapping Subproblems) in detail. The second property of Dynamic programming is discussed in the next post i.e.  Set 2 . 1)  Overlapping Subproblems  2)  Optimal Substructure 1) Overlapping Subproblems:   Like Divide and Conquer, Dynamic Programming combines solutions to sub-problems. Dynamic Programming is mainly used when solutions of the same subproblems are needed again and again. In dynamic programming, computed solutions to subproblems are stored in a table so that these don’t have to be recomputed. So Dynamic Programming is not useful when there are no common (overlapping) subproblems because there is no po