Find The Maximum Sum in Triangle From Top to Bottom (Euler Problem).

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Brute Force

When answering the problem with a brute force solution, it is pretty simple to go through the steps, we just need to try all combinations. Since we have a binary choice each time. We can iterate through all possibilities with a normal integer counter, and use the bits of the number to pick the direction left or right. While running through the path, we sum up the numbers and check if they are larger than the current maximum found.It is not possible to try every route to solve this problem (where the base of the triangle has 100 numbers), as there are 2^(99) altogether! If you could check one trillion (10^(12)) routes every second it would take over twenty billion years to check them all.

Dynamic Programming

 
Standing at the top of the triangle we have to choose between going left and right. In order to make the optimal choice (which maximizes the sum), we would have to know how large a sum we can get if we go either way. We have to solve the two smaller problems which I have marked with blue and the orange in the figure to the right.


We can break each of the sub-problems down in a similar way, and we can continue to do so until we reach a sub-problem at the bottom line consisting of only one number, then the answer is the number it self. Once that question is answered we can move up one line, and answer the questions posed there with a solution which is a + max(b,c).
Once we know the answer to all 3 sub-problems on the next to last line, we can move up and answer the posed sub-problems by the same formula already applied. And we can continue to do so until we reach the original question of whether to go left or right

Savings with Dynamic Programming

If we want to solve the small problem with brute force, we would need to test all 8 paths, each resulting in 3 additions, in total 24 additions.
If we use dynamic programming, the first iteration would require 3 maximum comparison operations and 3 additions. The next line would require 2 maximum comparison operations and 2 additions, and the first line would require one of each. So a total of 6 maximum comparison operations and 6 additions.

Dynamic Programming – The Algorithm

We can make a short-cut with the algorithm, as we don’t have to break the problem into sub-problems, but can start from the bottom and work the way up through the triangle until we reach the top and the algorithm spits out a number.
We start with a triangle that looks like

3
7 4
2 4 6
8 5 9 3

Applying the algorithm to the small problem we will need three iterations. The first iteration we apply the rule a + max(b,c) which creates a new triangle which looks as

3
7 4
10 13 15

Making the second iteration of the algorithm makes the triangle look

3
20 19

And if we run the algorithm once more, the triangle collapses to one number – 23 – which is the answer to the question.

Program:

#include<stdio.h>
int main(void)
{
    int j,t,n,i,a[100][100];
    printf("hi\n");
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
            for(j=0;j<=i;j++)
            {
                scanf("%d",&a[i][j]);
            }
        }
        for(i=n-2;i>=0;i--)
        {
            for(j=0;j<=i;j++)
            {
                a[i][j]+=a[i+1][j]>a[i+1][j+1]?a[i+1][j]:a[i+1][j+1];
            }
        }
        printf("%d\n",a[0][0]);
    }
    return 0;
}
Time complexity:O(n^2) where n is the number of rows.
we traverse through  n-1  elements on (n-2)th line, (n-2) elements on (n-3)th line and so on till 1 element in first line, a total of 1+2+..+(n-1) elements i.e. (n-1)n/2 or O(n^2) eelments.
At each element, an adition and comparision operation is performed in O(1) time.

Given an array of of size n and a number k, finds all elements that appear more than n/k times

Given an array of size n, find all elements in array that appear more than n/k times. For example, if the input arrays is {3, 1, 2, 2, 1, 2, 3, 3} and k is 4, then the output should be [2, 3]. Note that size of array is 8 (or n = 8), so we need to find all elements that appear more than 2 (or 8/4) times. There are two elements that appear more than two times, 2 and 3.
A simple method is to pick all elements one by one. For every picked element, count its occurrences by traversing the array, if count becomes more than n/k, then print the element. Time Complexity of this method would be O(n²).
A better solution is to use sorting. First, sort all elements using a O(nLogn) algorithm. Once the array is sorted, we can find all required elements in a linear scan of array. So overall time complexity of this method is O(nLogn) + O(n) which is O(nLogn).
Following is an interesting O(nk) solution:
We can solve the above problem in O(nk) time using O(k-1) extra space. Note that there can never be more than k-1 elements in output (Why?). There are mainly three steps in this algorithm.
1) Create a temporary array of size (k-1) to store elements and their counts (The output elements are going to be among these k-1 elements). Following is structure of temporary array elements.

struct eleCount {
    int element;
    int count;
}; 
struct eleCount temp[]; 

This step takes O(k) time.
2) Traverse through the input array and update temp[] (add/remove an element or increase/decrease count) for every traversed element. The array temp[] stores potential (k-1) candidates at every step. This step takes O(nk) time.
3) Iterate through final (k-1) potential candidates (stored in temp[]). or every element, check if it actually has count more than n/k. This step takes O(nk) time.
The main step is step 2, how to maintain (k-1) potential candidates at every point?  
We increment the count of an element if it is already present in array, else if there is an empty position we nsert it there and set the count to 1,else we decrement count of all elements by 1.

Consider k = 4, n = 9 
Given array: 3 1 2 2 2 1 4 3 3 

i = 0
         3 _ _
temp[] has one element, 3 with count 1

i = 1
         3 1 _
temp[] has two elements, 3 and 1 with 
counts 1 and 1 respectively

i = 2
         3 1 2
temp[] has three elements, 3, 1 and 2 with
counts as 1, 1 and 1 respectively.

i = 3
         - - 2 
         3 1 2
temp[] has three elements, 3, 1 and 2 with
counts as 1, 1 and 2 respectively.

i = 4
         - - 2 
         - - 2 
         3 1 2
temp[] has three elements, 3, 1 and 2 with
counts as 1, 1 and 3 respectively.

i = 5
         - - 2 
         - 1 2 
         3 1 2
temp[] has three elements, 3, 1 and 2 with
counts as 1, 2 and 3 respectively. 

Now the question arises, what to do when temp[] is full and we see a new element – we remove the bottom row from stacks of elements, i.e., we decrease count of every element by 1 in temp[]. We ignore the current element.

i = 6
         - - 2 
         - 1 2 
temp[] has two elements 1 and 2 with
counts as 1 and 2 respectively.

i = 7
         - - 2 
         3 1 2 
temp[] has three elements, 3, 1 and 2 with
counts as 1, 1 and 2 respectively.

i = 8
 
         3 - 2
         3 1 2 
temp[] has three elements, 3, 1 and 2 with
counts as 2, 1 and 2 respectively.

Finally, we have at most k-1 numbers in temp[]. The elements in temp are {3, 1, 2}. Note that the counts in temp[] are useless now, the counts were needed only in step 2. Now we need to check whether the actual counts of elements in temp[] are more than n/k (9/4) or not. The elements 3 and 2 have counts more than 9/4. So we print 3 and 2.
Note that the algorithm doesn’t miss any output element. There can be two possibilities, many occurrences are together or spread across the array. If occurrences are together, then count will be high and won’t become 0. If occurrences are spread, then the element would come again in temp[]. Following is C++ implementation of above algorithm.

// A C++ program to print elements with count more than n/k #include<iostream> using namespace std; // A structure to store an element and its current count struct eleCount { int e; // Element int c; // Count }; // Prints elements with more than n/k occurrences in arr[] of // size n. If there are no such elements, then it prints nothing. void moreThanNdK(int arr[], int n, int k) { // k must be greater than 1 to get some output if (k < 2) return; /* Step 1: Create a temporary array (contains element and count) of size k-1. Initialize count of all elements as 0 */ struct eleCount temp[k-1]; for (int i=0; i<k-1; i++) temp[i].c = 0; /* Step 2: Process all elements of input array */ for (int i = 0; i < n; i++) { int j; /* If arr[i] is already present in the element count array, then increment its count */ for (j=0; j<k-1; j++) { if (temp[j].e == arr[i]) { temp[j].c += 1; break; } } /* If arr[i] is not present in temp[] */ if (j == k-1) { int l; /* If there is position available in temp[], then place arr[i] in the first available position and set count as 1*/ for (l=0; l<k-1; l++) { if (temp[l].c == 0) { temp[l].e = arr[i]; temp[l].c = 1; break; } } /* If all the position in the temp[] are filled, then decrease count of every element by 1 */ if (l == k-1) for (l=0; l<k; l++) temp[l].c -= 1; } } /*Step 3: Check actual counts of potential candidates in temp[]*/ for (int i=0; i<k-1; i++) { // Calculate actual count of elements int ac = 0; // actual count for (int j=0; j<n; j++) if (arr[j] == temp[i].e) ac++; // If actual count is more than n/k, then print it if (ac > n/k) cout << "Number:" << temp[i].e << " Count:" << ac << endl; } } /* Driver program to test above function */ int main() { cout << "First Test\n"; int arr1[] = {4, 5, 6, 7, 8, 4, 4}; int size = sizeof(arr1)/sizeof(arr1[0]); int k = 3; moreThanNdK(arr1, size, k); cout << "\nSecond Test\n"; int arr2[] = {4, 2, 2, 7}; size = sizeof(arr2)/sizeof(arr2[0]); k = 3; moreThanNdK(arr2, size, k); cout << "\nThird Test\n"; int arr3[] = {2, 7, 2}; size = sizeof(arr3)/sizeof(arr3[0]); k = 2; moreThanNdK(arr3, size, k); cout << "\nFourth Test\n"; int arr4[] = {2, 3, 3, 2}; size = sizeof(arr4)/sizeof(arr4[0]); k = 3; moreThanNdK(arr4, size, k); return 0; }

Output:

First Test
Number:4 Count:3

Second Test
Number:2 Count:2

Third Test
Number:2 Count:2

Fourth Test
Number:2 Count:2
Number:3 Count:2

Time Complexity: O(nk)
Auxiliary Space: O(k)
Generally asked variations of this problem are, find all elements that appear n/3 times or n/4 times in O(n) time complexity.

print only one line in a pascal's triangle

time complexity:O(n)

We know that ith entry in a line number line is Binomial Coefficient C(line, i) and all lines start with value 1. The idea is to calculate C(line, i) using C(line, i-1). It can be calculated in O(1) time using the following.

C(line, i)   = line! / ( (line-i)! * i! )
C(line, i-1) = line! / ( (line - i + 1)! * (i-1)! )
We can derive following expression from above two expressions.
C(line, i) = C(line, i-1) * (line - i + 1) / i

So C(line, i) can be calculated from C(line, i-1) in O(1) time

Program:
#include<stdio.h>
int main(void)
{
int t;
scanf("%d",&t);
while(t--)
{
int n,i,c;
scanf("%d",&n);
c=1;
for(i=1;i<=n+1;i++)
{
printf("%d ",c);
c=c*(n-i+1)/i;
}
printf("\n");
}
return 0;
}

Mirror of a Tree: Mirror of a Binary Tree T is another Binary Tree M(T) with left and right children of all non-leaf nodes interchanged.

Algorithm - Mirror(tree):

(1)  Call Mirror for left-subtree    i.e., Mirror(left-subtree)
(2)  Call Mirror for right-subtree  i.e., Mirror(left-subtree)
(3)  Swap left and right subtrees.
          temp = left-subtree
          left-subtree = right-subtree
          right-subtree = temp

Program:

#include<stdio.h> #include<stdlib.h> /* A binary tree node has data, pointer to left child and a pointer to right child */ struct node { int data; struct node* left; struct node* right; }; /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ struct node* newNode(int data) { struct node* node = (struct node*) malloc(sizeof(struct node)); node->data = data; node->left = NULL; node->right = NULL; return(node); } /* Change a tree so that the roles of the left and right pointers are swapped at every node. So the tree... 4 / \ 2 5 / \ 1 3 is changed to... 4 / \ 5 2 / \ 3 1 */ void mirror(struct node* node) { if (node==NULL) return; else { struct node* temp; /* do the subtrees */ mirror(node->left); mirror(node->right); /* swap the pointers in this node */ temp = node->left; node->left = node->right; node->right = temp; } } /* Helper function to test mirror(). Given a binary search tree, print out its data elements in increasing sorted order.*/ void inOrder(struct node* node) { if (node == NULL) return; inOrder(node->left); printf("%d ", node->data); inOrder(node->right); } /* Driver program to test mirror() */ int main() { struct node *root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); /* Print inorder traversal of the input tree */ printf("\n Inorder traversal of the constructed tree is \n"); inOrder(root); /* Convert tree to its mirror */ mirror(root); /* Print inorder traversal of the mirror tree */ printf("\n Inorder traversal of the mirror tree is \n"); inOrder(root); getchar(); return 0; }

Stock Buy Sell to Maximize Profit

The cost of a stock on each day is given in an array, find the max profit that you can make by buying and selling in those days. For example, if the given array is {10, 18, 26, 31, 4, 53, 69}, the maximum profit can earned by buying on day 0, selling on day 3. Again buy on day 4 and sell on day 6. If the given array of prices is sorted in decreasing order, then profit cannot be earned at all.
If we are allowed to buy and sell only once, then we can use following algorithm: Maximum difference between two elements. Here we are allowed to buy and sell multiple times. Following is algorithm for this problem.
1. Find the local minima and store it as starting index. If not exists, return.
2. Find the local maxima. and store it as ending index. If we reach the end, set the end as ending index.
3. Update the solution (Increment count of buy sell pairs)
4. Repeat the above steps if end is not reached.

// Program to find best buying and selling days #include <stdio.h> // solution structure struct Interval { int buy; int sell; }; // This function finds the buy sell schedule for maximum profit void stockBuySell(int price[], int n) { // Prices must be given for at least two days if (n == 1) return; int count = 0; // count of solution pairs // solution vector Interval sol[n/2 + 1]; // Traverse through given price array int i = 0; while (i < n-1) { // Find Local Minima. Note that the limit is (n-2) as we are // comparing present element to the next element. while ((i < n-1) && (price[i+1] <= price[i])) i++; // If we reached the end, break as no further solution possible if (i == n-1) break; // Store the index of minima sol[count].buy = i++; // Find Local Maxima. Note that the limit is (n-1) as we are // comparing to previous element while ((i < n) && (price[i] >= price[i-1])) i++; // Store the index of maxima sol[count].sell = i-1; // Increment count of buy/sell pairs count++; } // print solution if (count == 0) printf("There is no day when buying the stock will make profit\n"); else { for (int i = 0; i < count; i++) printf("Buy on day: %d\t Sell on day: %d\n", sol[i].buy, sol[i].sell); } return; } // Driver program to test above functions int main() { // stock prices on consecutive days int price[] = {100, 180, 260, 310, 40, 535, 695}; int n = sizeof(price)/sizeof(price[0]); // fucntion call stockBuySell(price, n); return 0; }

Output:

Buy on day : 0   Sell on day: 3
Buy on day : 4   Sell on day: 6

Time Complexity: The outer loop runs till i becomes n-1. The inner two loops increment value of i in every iteration. So overall time complexity is O(n)

Given n dice each with m faces, numbered from 1 to m, find the number of ways to get sum X. X is the summation of values on each face when all the dice are thrown.

The Naive approach is to find all the possible combinations of values from n dice and keep on counting the results that sum to X.

This problem can be efficiently solved using Dynamic Programming (DP).

Let the function to find X from n dice is: Sum(m, n, X)
The function can be represented as:
Sum(m, n, X) = Finding Sum (X - 1) from (n - 1) dice plus 1 from nth dice
               + Finding Sum (X - 2) from (n - 1) dice plus 2 from nth dice
               + Finding Sum (X - 3) from (n - 1) dice plus 3 from nth dice
                  ...................................................
                  ...................................................
                  ...................................................
              + Finding Sum (X - m) from (n - 1) dice plus m from nth dice

So we can recursively write Sum(m, n, x) as following
Sum(m, n, X) = Sum(m, n - 1, X - 1) + 
               Sum(m, n - 1, X - 2) +
               .................... + 
               Sum(m, n - 1, X - m)

Sum(6, 3, 8) = Sum(6, 2, 7) + Sum(6, 2, 6) + Sum(6, 2, 5) +
               Sum(6, 2, 4) + Sum(6, 2, 3) + Sum(6, 2, 2)

To evaluate Sum(6, 3, 8), we need to evaluate Sum(6, 2, 7) which can
recursively written as following:
Sum(6, 2, 7) = Sum(6, 1, 6) + Sum(6, 1, 5) + Sum(6, 1, 4) + Sum(6, 1, 3) + Sum(6, 1, 2) + Sum(6, 1, 1)

We also need to evaluate Sum(6, 2, 6) which can recursively written
as following:
Sum(6, 2, 6) = Sum(6, 1, 5) + Sum(6, 1, 4) + Sum(6, 1, 3) + Sum(6, 1, 2) + Sum(6, 1, 1)
..............................................
..............................................
Sum(6, 2, 2) = Sum(6, 1, 1)

Please take a closer look at the above recursion. The sub-problems in RED are solved first time and sub-problems in BLUE are solved again (exhibit overlapping sub-problems). Hence, storing the results of the solved sub-problems saves time

// C++ program to find number of ways to get sum 'x' with 'n'

// dice where every dice has 'm' faces

#include <iostream>

#include <string.h>

using namespace std;

// The main function that returns number of ways to get sum 'x'

// with 'n' dice and 'm' with m faces.

int findWays(int m, int n, int x)

{

// Create a table to store results of subproblems. One extra

// row and column are used for simpilicity (Number of dice

// is directly used as row index and sum is directly used

// as column index). The entries in 0th row and 0th column

// are never used.

int table[n + 1][x + 1];

memset(table, 0, sizeof(table)); // Initialize all entries as 0

// Table entries for only one dice

for (int j = 1; j <= m && j <= x; j++)

table[1][j] = 1;

// Fill rest of the entries in table using recursive relation

// i: number of dice, j: sum

for (int i = 2; i <= n; i++)

for (int j = 1; j <= x; j++)

for (int k = 1; k <= m && k < j; k++)

table[i][j] += table[i-1][j-k];

/* Uncomment these lines to see content of table

for (int i = 0; i <= n; i++)

{

for (int j = 0; j <= x; j++)

cout << table[i][j] << " ";

cout << endl;

} */

return table[n][x];

}

// Driver program to test above functions

int main()

{

cout << findWays(4, 2, 1) << endl;

cout << findWays(2, 2, 3) << endl;

cout << findWays(6, 3, 8) << endl;

cout << findWays(4, 2, 5) << endl;

cout << findWays(4, 3, 5) << endl;

return 0;

}