Open In App

Memoization (1D, 2D and 3D)

Last Updated : 10 Aug, 2022
Summarize
Comments
Improve
Suggest changes
Like Article
Like
Save
Share
Report
News Follow

Most of the Dynamic Programming problems are solved in two ways:  

  1. Tabulation: Bottom Up
  2. Memoization: Top Down

One of the easier approaches to solve most of the problems in DP is to write the recursive code at first and then write the Bottom-up Tabulation Method or Top-down Memoization of the recursive function. The steps to write the DP solution of Top-down approach to any problem is to:  

  1. Write the recursive code
  2. Memoize the return value and use it to reduce recursive calls.

1-D Memoization
The first step will be to write the recursive code. In the program below, a program related to recursion where only one parameter changes its value has been shown. Since only one parameter is non-constant, this method is known as 1-D memoization. E.g., the Fibonacci series problem to find the N-th term in the Fibonacci series. The recursive approach has been discussed here.
Given below is the recursive code to find the N-th term:  

C++




// C++ program to find the Nth term
// of Fibonacci series
#include <bits/stdc++.h>
using namespace std;
 
// Fibonacci Series using Recursion
int fib(int n)
{
 
    // Base case
    if (n <= 1)
        return n;
 
    // recursive calls
    return fib(n - 1) + fib(n - 2);
}
 
// Driver Code
int main()
{
    int n = 6;
    printf("%d", fib(n));
    return 0;
}


Java




// Java program to find the
// Nth term of Fibonacci series
import java.io.*;
 
class GFG
{
     
// Fibonacci Series
// using Recursion
static int fib(int n)
{
 
    // Base case
    if (n <= 1)
        return n;
 
    // recursive calls
    return fib(n - 1) +
           fib(n - 2);
}
 
// Driver Code
public static void main (String[] args)
{
    int n = 6;
    System.out.println(fib(n));
}
}
 
// This code is contributed
// by ajit


Python3




# Python3 program to find the Nth term
# of Fibonacci series
 
# Fibonacci Series using Recursion
def fib(n):
 
 
    # Base case
    if (n <= 1):
        return n
 
    # recursive calls
    return fib(n - 1) + fib(n - 2)
 
# Driver Code
if __name__=='__main__':
    n = 6
    print (fib(n))
  
# This code is contributed by
# Shivi_Aggarwal


C#




// C# program to find
// the Nth term of
// Fibonacci series
using System;
 
class GFG
{
     
// Fibonacci Series
// using Recursion
static int fib(int n)
{
    // Base case
    if (n <= 1)
        return n;
 
    // recursive calls
    return fib(n - 1) +
           fib(n - 2);
}
// Driver Code
static public void Main ()
{
    int n = 6;
    Console.WriteLine(fib(n));
}
}
 
// This code is contributed
// by akt_mit


Javascript




<script>
// Javascript program to find the Nth term
// of Fibonacci series
 
// Fibonacci Series using Recursion
function fib(n)
{
 
    // Base case
    if (n <= 1)
        return n;
 
    // recursive calls
    return fib(n - 1) + fib(n - 2);
}
 
// Driver Code
let n = 6;
document.write(fib(n));
 
// This code is contributed by subhammahato348.
</script>


PHP




<?php
// PHP program to find
// the Nth term of
// Fibonacci series
// using Recursion
 
function fib($n)
{
 
    // Base case
    if ($n <= 1)
        return $n;
 
    // recursive calls
    return fib($n - 1) +
           fib($n - 2);
}
 
// Driver Code
$n = 6;
echo fib($n);
 
// This code is contributed
// by ajit
?>


Output: 

8

 

Time Complexity: O(2^n)

As at every stage we need to take 2 function calls and the height of the tree will be of the order of n.

Auxiliary Space: O(n)

The extra space is used due to recursion call stack.

A common observation is that this implementation does a lot of repeated work (see the following recursion tree). So this will consume a lot of time for finding the N-th Fibonacci number if done.  

                            fib(5)   
                     /                 \        
               fib(4)                  fib(3)   
             /      \                /       \
         fib(3)      fib(2)         fib(2)    fib(1)
        /   \          /    \       /      \ 
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  /    \ 
fib(1) fib(0) 

In the above tree fib(3), fib(2), fib(1), fib(0) all are called more than once.

The following problem has been solved using the Tabulation method. 
In the program below, the steps to write a Top-Down approach program have been explained. Some modifications in the recursive program will reduce the complexity of the program and give the desired result. If fib(x) has not occurred previously, then we store the value of fib(x) in an array term at index x and return term[x]. By memoizing the return value of fib(x) at index x of an array, reduce the number of recursive calls at the next step when fib(x) has already been called. So without doing further recursive calls to compute the value of fib(x), return term[x] when fib(x) has already been computed previously to avoid a lot of repeated work as shown in the tree. 
Given below is the memoized recursive code to find the N-th term.  

C++




// CPP program to find the Nth term
// of Fibonacci series
#include <bits/stdc++.h>
using namespace std;
int term[1000];
// Fibonacci Series using memoized Recursion
int fib(int n)
{
    // base case
    if (n <= 1)
        return n;
 
    // if fib(n) has already been computed
    // we do not do further recursive calls
    // and hence reduce the number of repeated
    // work
    if (term[n] != 0)
        return term[n];
 
    else {
 
        // store the computed value of fib(n)
        // in an array term at index n to
        // so that it does not needs to be
        // precomputed again
        term[n] = fib(n - 1) + fib(n - 2);
 
        return term[n];
    }
}
 
// Driver Code
int main()
{
    int n = 6;
    printf("%d", fib(n));
    return 0;
}


Java




// Java program to find
// the Nth term of
// Fibonacci series
import java.io.*;
 
class GFG
{
 
static  int []term = new int [1000];
// Fibonacci Series using
// memoized Recursion
static int fib(int n)
{
    // base case
    if (n <= 1)
        return n;
 
    // if fib(n) has already
    // been computed we do not
    // do further recursive
    // calls and hence reduce
    // the number of repeated
    // work
    if (term[n] != 0)
        return term[n];
 
    else
    {
 
        // store the computed value
        // of fib(n) in an array
        // term at index n to so that
        // it does not needs to be
        // precomputed again
        term[n] = fib(n - 1) +
                  fib(n - 2);
 
        return term[n];
    }
}
 
// Driver Code
public static void main (String[] args)
{
    int n = 6;
    System.out.println(fib(n));
}
}
 
// This code is contributed by ajit


Python3




# Python program to find the Nth term
# of Fibonacci series
term = [0 for i in range(1000)]
 
# Fibonacci Series using memoized Recursion
def fib(n):
   
  # base case
  if n <= 1:
    return n
 
  # if fib(n) has already been computed
  # we do not do further recursive calls
  # and hence reduce the number of repeated
  # work
  if term[n] != 0:
    return term[n]
 
  else:
     
    # store the computed value of fib(n)
    # in an array term at index n to
    # so that it does not needs to be
    # precomputed again
    term[n] = fib(n - 1) + fib(n - 2)
    return term[n]
 
# Driver Code
n = 6
print(fib(n))
 
# This code is contributed by rohitsingh07052


C#




// C# program to find
// the Nth term of
// Fibonacci series
 
using System;
class GFG
{
      
// Fibonacci Series using
// memoized Recursion
static int fib(int n)
{
    int[] term = new int [1000];
      
    // base case
    if (n <= 1)
        return n;
  
    // if fib(n) has already
    // been computed we do not
    // do further recursive
    // calls and hence reduce
    // the number of repeated
    // work
    if (term[n] != 0)
        return term[n];
  
    else
    {
  
        // store the computed value
        // of fib(n) in an array
        // term at index n to so that
        // it does not needs to be
        // precomputed again
        term[n] = fib(n - 1) +
                  fib(n - 2);
  
        return term[n];
    }
}
  
// Driver Code
public static void Main ()
{
    int n = 6;
    Console.Write(fib(n));
}
}


Javascript




<script>
    // Javascript program to find
    // the Nth term of
    // Fibonacci series
     
    // Fibonacci Series using
    // memoized Recursion
    function fib(n)
    {
        let term = new Array(1000);
        term.fill(0);
 
        // base case
        if (n <= 1)
            return n;
 
        // if fib(n) has already
        // been computed we do not
        // do further recursive
        // calls and hence reduce
        // the number of repeated
        // work
        if (term[n] != 0)
            return term[n];
 
        else
        {
 
            // store the computed value
            // of fib(n) in an array
            // term at index n to so that
            // it does not needs to be
            // precomputed again
            term[n] = fib(n - 1) +
                      fib(n - 2);
 
            return term[n];
        }
    }
 
    let n = 6;
    document.write(fib(n));
     
    // This code is contributed by mukesh07.
</script>


Output: 

8

 

Time Complexity: O(n)

As we have to calculate values for all function calls just once and there will be n values of arguments so the complexity will reduce to O(n).

Auxiliary Space: O(n)

The extra space is used due to recursion call stack.

If the recursive code has been written once, then memoization is just modifying the recursive program and storing the return values to avoid repetitive calls of functions that have been computed previously.
 

2-D Memoization
In the above program, the recursive function had only one argument whose value was not constant after every function call. Below, an implementation where the recursive program has two non-constant arguments has been shown. 
For e.g., Program to solve the standard Dynamic Problem LCS problem when two strings are given. The general recursive solution of the problem is to generate all subsequences of both given sequences and find the longest matching subsequence. The total possible combinations will be 2n. Hence, the recursive solution will take O(2n). The approach to writing the recursive solution has been discussed here. 
Given below is the recursive solution to the LCS problem: 

C++




// A Naive recursive implementation of LCS problem
#include <bits/stdc++.h>
 
int max(int a, int b);
 
// Returns length of LCS for X[0..m-1], Y[0..n-1]
int lcs(char* X, char* Y, int m, int n)
{
    if (m == 0 || n == 0)
        return 0;
    if (X[m - 1] == Y[n - 1])
        return 1 + lcs(X, Y, m - 1, n - 1);
    else
        return max(lcs(X, Y, m, n - 1),
                  lcs(X, Y, m - 1, n));
}
 
// Utility function to get max of 2 integers
int max(int a, int b)
{
    return (a > b) ? a : b;
}
 
// Driver Code
int main()
{
    char X[] = "AGGTAB";
    char Y[] = "GXTXAYB";
 
    int m = strlen(X);
    int n = strlen(Y);
 
    printf("Length of LCS is %dn", lcs(X, Y, m, n));
 
    return 0;
}


Java




// A Naive recursive implementation of LCS problem
import java.io.*;
class GFG
{
 
    // Utility function to get max of 2 integers
    static int max(int a, int b) { return (a > b) ? a : b; }
 
    // Returns length of LCS for X[0..m-1], Y[0..n-1]
    static int lcs(String X, String Y, int m, int n)
    {
        if (m == 0 || n == 0)
            return 0;
        if (X.charAt(m - 1) == Y.charAt(n - 1))
            return 1 + lcs(X, Y, m - 1, n - 1);
        else
            return max(lcs(X, Y, m, n - 1),
                       lcs(X, Y, m - 1, n));
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        String X = "AGGTAB";
        String Y = "GXTXAYB";
 
        int m = X.length();
        int n = Y.length();
 
        System.out.print("Length of LCS is "
                         + lcs(X, Y, m, n));
    }
}
 
// This code is contributed by subhammahato348


Python3




# A Naive recursive implementation of LCS problem
 
# Returns length of LCS for X[0..m-1], Y[0..n-1]
def lcs(X, Y, m, n):
    if (m == 0 or n == 0):
        return 0;
    if (X[m - 1] == Y[n - 1]):
        return 1 + lcs(X, Y, m - 1, n - 1);
    else:
        return max(lcs(X, Y, m, n - 1),
                  lcs(X, Y, m - 1, n));
 
# Driver Code
if __name__=='__main__':
    X = "AGGTAB";
    Y = "GXTXAYB";
    m = len(X);
    n = len(Y);
    print("Length of LCS is {}n".format(lcs(X, Y, m, n)))
 
# This code is contributed by rutvik_56.


C#




// A Naive recursive implementation of LCS problem
using System;
class GFG
{
 
  // Utility function to get max of 2 integers
  static int max(int a, int b) { return (a > b) ? a : b; }
 
  // Returns length of LCS for X[0..m-1], Y[0..n-1]
  static int lcs(string X, string Y, int m, int n)
  {
    if (m == 0 || n == 0)
      return 0;
    if (X[m - 1] == Y[n - 1])
      return 1 + lcs(X, Y, m - 1, n - 1);
    else
      return max(lcs(X, Y, m, n - 1),
                 lcs(X, Y, m - 1, n));
  }
 
  // Driver Code
  public static void Main()
  {
    string X = "AGGTAB";
    string Y = "GXTXAYB";
 
    int m = X.Length;
    int n = Y.Length;
 
    Console.Write("Length of LCS is "
                  + lcs(X, Y, m, n));
  }
}
 
// This code is contributed by subhammahato348


Javascript




<script>
// A Naive recursive implementation of LCS problem
 
    // Utility function to get max of 2 integers
    function max(a,b)
    {
         return (a > b) ? a : b;
    }
     
    // Returns length of LCS for X[0..m-1], Y[0..n-1]
    function lcs(X,Y,m,n)
    {
        if (m == 0 || n == 0)
            return 0;
        if (X[m-1] == Y[n-1])
            return 1 + lcs(X, Y, m - 1, n - 1);
        else
            return max(lcs(X, Y, m, n - 1),
                       lcs(X, Y, m - 1, n));
    }
     
    // Driver Code
    let X = "AGGTAB";
    let Y = "GXTXAYB";
    let m = X.length;
    let n = Y.length;
    document.write("Length of LCS is "
                         + lcs(X, Y, m, n));
     
     
 
// This code is contributed by avanitrachhadiya2155
</script>


Output:

Length of LCS is 4

Considering the above implementation, the following is a partial recursion tree for input strings “AXYT” and “AYZX” 
 

                  lcs("AXYT", "AYZX")
                       /                 \
         lcs("AXY", "AYZX")            lcs("AXYT", "AYZ")
         /           \                   /               \
lcs("AX", "AYZX") lcs("AXY", "AYZ")   lcs("AXY", "AYZ") lcs("AXYT", "AY")

In the above partial recursion tree, lcs(“AXY”, “AYZ”) is being solved twice. On drawing the complete recursion tree, it has been observed that there are many subproblems that are solved again and again. So this problem has Overlapping Substructure property and recomputation of same subproblems can be avoided by either using Memoization or Tabulation. The tabulation method has been discussed here. 
A common point of observation to use memoization in the recursive code will be the two non-constant arguments M and N in every function call. The function has 4 arguments, but 2 arguments are constant which does not affect the Memoization. The repetitive calls occur for N and M which have been called previously. So use a 2-D array to store the computed lcs(m, n) value at arr[m-1][n-1] as the string index starts from 0. Whenever the function with the same argument m and n are called again, we do not perform any further recursive call and return arr[m-1][n-1] as the previous computation of the lcs(m, n) has already been stored in arr[m-1][n-1], hence reducing the recursive calls that happen more than once. 
Below is the implementation of the Memoization approach of the recursive code.  

C++




// C++ program to memoize
// recursive implementation of LCS problem
#include <bits/stdc++.h>
int arr[1000][1000];
int max(int a, int b);
 
// Returns length of LCS for X[0..m-1], Y[0..n-1] */
// memoization applied in recursive solution
int lcs(char* X, char* Y, int m, int n)
{
    // base case
    if (m == 0 || n == 0)
        return 0;
 
    // if the same state has already been
    // computed
    if (arr[m - 1][n - 1] != -1)
        return arr[m - 1][n - 1];
 
    // if equal, then we store the value of the
    // function call
    if (X[m - 1] == Y[n - 1]) {
 
        // store it in arr to avoid further repetitive
        // work in future function calls
        arr[m - 1][n - 1] = 1 + lcs(X, Y, m - 1, n - 1);
        return arr[m - 1][n - 1];
    }
    else {
        // store it in arr to avoid further repetitive
        // work in future function calls
        arr[m - 1][n - 1] = max(lcs(X, Y, m, n - 1),
                                lcs(X, Y, m - 1, n));
        return arr[m - 1][n - 1];
    }
}
 
// Utility function to get max of 2 integers
int max(int a, int b)
{
    return (a > b) ? a : b;
}
 
// Driver Code
int main()
{
    memset(arr, -1, sizeof(arr));
    char X[] = "AGGTAB";
    char Y[] = "GXTXAYB";
 
    int m = strlen(X);
    int n = strlen(Y);
 
    printf("Length of LCS is %d", lcs(X, Y, m, n));
 
    return 0;
}


Java




// Java program to memoize
// recursive implementation of LCS problem
import java.io.*;
import java.lang.*;
class GFG
{
  public static int arr[][] = new int[1000][1000];
 
  // Returns length of LCS for X[0..m-1], Y[0..n-1] */
  // memoization applied in recursive solution
  public static int lcs(String X, String Y, int m, int n)
  {
 
    // base case
    if (m == 0 || n == 0)
      return 0;
 
    // if the same state has already been
    // computed
    if (arr[m - 1][n - 1] != -1)
      return arr[m - 1][n - 1];
 
    // if equal, then we store the value of the
    // function call
    if ( X.charAt(m - 1) == Y.charAt(n - 1))
    {
 
      // store it in arr to avoid further repetitive
      // work in future function calls
      arr[m - 1][n - 1] = 1 + lcs(X, Y, m - 1, n - 1);
      return arr[m - 1][n - 1];
    }
    else
    {
 
      // store it in arr to avoid further repetitive
      // work in future function calls
      arr[m - 1][n - 1] = max(lcs(X, Y, m, n - 1),
                              lcs(X, Y, m - 1, n));
      return arr[m - 1][n - 1];
    }
  }
 
  // Utility function to get max of 2 integers
  public static int max(int a, int b)
  {
    return (a > b) ? a : b;
  }
 
  // Driver code
  public static void main (String[] args)
  {
    for(int i = 0; i < 1000; i++)
    {
      for(int j = 0; j < 1000; j++)
      {
        arr[i][j] = -1;
      }
    }
    String X = "AGGTAB";
    String Y = "GXTXAYB";
 
    int m = X.length();
    int n = Y.length();
 
    System.out.println("Length of LCS is " + lcs(X, Y, m, n));
  }
}
 
// This code is contributed by manupathria.


Python3




# Python3 program to memoize
# recursive implementation of LCS problem
 
# Returns length of LCS for X[0..m-1], Y[0..n-1]
# memoization applied in recursive solution
def lcs(X, Y, m, n):
 
    global arr
 
    # base case
    if (m == 0 or n == 0):
        return 0
 
    # if the same state has already been
    # computed
    if (arr[m - 1][n - 1] != -1):
        return arr[m - 1][n - 1]
 
    # if equal, then we store the value of the
    # function call
    if (X[m - 1] == Y[n - 1]):
 
        # store it in arr to avoid further repetitive
        # work in future function calls
        arr[m - 1][n - 1] = 1 + lcs(X, Y, m - 1, n - 1)
        return arr[m - 1][n - 1]
 
    else:
 
        # store it in arr to avoid further repetitive
        # work in future function calls
        arr[m - 1][n - 1] = max(lcs(X, Y, m, n - 1),
                                lcs(X, Y, m - 1, n))
        return arr[m - 1][n - 1]
 
 
# Driver code
 
arr = [[0]*1000]*1000
 
for i in range(0, 1000):
    for j in range(0, 1000):
        arr[i][j] = -1
 
X = "AGGTAB"
Y = "GXTXAYB"
 
m = len(X)
n = len(Y)
 
print("Length of LCS is ", lcs(X, Y, m, n))
 
# This code is contributed by Dharanendra L V.


C#




// C# program to memoize
// recursive implementation of LCS problem
using System;
public class GFG
{
 
  public static int[, ] arr = new int[1000, 1000];
 
  // Returns length of LCS for X[0..m-1], Y[0..n-1] */
  // memoization applied in recursive solution
  public static int lcs(String X, String Y, int m, int n)
  {
 
    // base case
    if (m == 0 || n == 0)
      return 0;
 
    // if the same state has already been
    // computed
    if (arr[m - 1, n - 1] != -1)
      return arr[m - 1, n - 1];
 
    // if equal, then we store the value of the
    // function call
    if ( X[m - 1] == Y[n - 1])
    {
 
      // store it in arr to avoid further repetitive
      // work in future function calls
      arr[m - 1, n - 1] = 1 + lcs(X, Y, m - 1, n - 1);
      return arr[m - 1, n - 1];
    }
    else
    {
 
      // store it in arr to avoid further repetitive
      // work in future function calls
      arr[m - 1, n - 1] = max(lcs(X, Y, m, n - 1),
                              lcs(X, Y, m - 1, n));
      return arr[m - 1, n - 1];
    }
  }
 
  // Utility function to get max of 2 integers
  public static int max(int a, int b)
  {
    return (a > b) ? a : b;
  }
 
  // Driver code
  static public void Main (){
 
    for(int i = 0; i < 1000; i++)
    {
      for(int j = 0; j < 1000; j++)
      {
        arr[i, j] = -1;
      }
    }
    String X = "AGGTAB";
    String Y = "GXTXAYB";
 
    int m = X.Length;
    int n = Y.Length;
 
    Console.WriteLine("Length of LCS is " + lcs(X, Y, m, n));
  }
}
 
// This code is contributed by Dharanendra L V.


Javascript




<script>
// Javascript program to memoize
// recursive implementation of LCS problem
     
    let arr=new Array(1000);
    for(let i=0;i<1000;i++)
    {
        arr[i]=new Array(1000);
        for(let j=0;j<1000;j++)
        {
            arr[i][j]=-1;
        }
    }
     
    // Returns length of LCS for X[0..m-1], Y[0..n-1] */
  // memoization applied in recursive solution
    function lcs(X,Y,m,n)
    {
        // base case
    if (m == 0 || n == 0)
      return 0;
  
    // if the same state has already been
    // computed
    if (arr[m - 1][n - 1] != -1)
        return arr[m - 1][n - 1];
  
    // if equal, then we store the value of the
    // function call
    if ( X[m-1] == Y[n-1])
    {
  
      // store it in arr to avoid further repetitive
      // work in future function calls
      arr[m - 1][n - 1] = 1 + lcs(X, Y, m - 1, n - 1);
      return arr[m - 1][n - 1];
    }
    else
    {
  
      // store it in arr to avoid further repetitive
      // work in future function calls
      arr[m - 1][n - 1] = Math.max(lcs(X, Y, m, n - 1),
                              lcs(X, Y, m - 1, n));
      return arr[m - 1][n - 1];
    }
    }
     
     
     
    // Driver code
    let X = "AGGTAB";
    let Y = "GXTXAYB";
    let m = X.length;
    let n = Y.length;
    document.write("Length of LCS is " + lcs(X, Y, m, n));
 
     
     
// This code is contributed by rag2127
</script>


Output: 

Length of LCS is 4

 

3-D Memoization

In the above program, the recursive function had only two arguments whose values were not constant after every function call. Below, an implementation where the recursive program has three non-constant arguments is done. 
For e.g., Program to solve the standard Dynamic Problem LCS problem for three strings. The general recursive solution of the problem is to generate all subsequences of both given sequences and find the longest matching subsequence. The total possible combinations will be 3n. Hence, a recursive solution will take O(3n)
Given below is the recursive solution to the LCS problem:  

C++




// A recursive implementation of LCS problem
// of three strings
#include <bits/stdc++.h>
int max(int a, int b);
 
// Returns length of LCS for X[0..m-1], Y[0..n-1]
int lcs(char* X, char* Y, char* Z, int m, int n, int o)
{
    // base case
    if (m == 0 || n == 0 || o == 0)
        return 0;
 
    // if equal, then check for next combination
    if (X[m - 1] == Y[n - 1] and Y[n - 1] == Z[o - 1]) {
 
        // recursive call
        return 1 + lcs(X, Y, Z, m - 1, n - 1, o - 1);
    }
    else {
 
        // return the maximum of the three other
        // possible states in recursion
        return max(lcs(X, Y, Z, m, n - 1, o),
                   max(lcs(X, Y, Z, m - 1, n, o),
                       lcs(X, Y, Z, m, n, o - 1)));
    }
}
 
// Utility function to get max of 2 integers
int max(int a, int b)
{
    return (a > b) ? a : b;
}
 
// Driver Code
int main()
{
 
    char X[] = "geeks";
    char Y[] = "geeksfor";
    char Z[] = "geeksforge";
    int m = strlen(X);
    int n = strlen(Y);
    int o = strlen(Z);
    printf("Length of LCS is %d", lcs(X, Y, Z, m, n, o));
 
    return 0;
}


Java




// A recursive implementation of LCS problem
// of three strings
class GFG
{
  // Utility function to get max of 2 integers
  static int max(int a, int b)
  {
    return (a > b) ? a : b;
  }
 
  // Returns length of LCS for X[0..m-1], Y[0..n-1]
  static int lcs(char[] X, char[] Y, char[] Z,
                 int m, int n, int o)
  {
 
    // base case
    if (m == 0 || n == 0 || o == 0)
      return 0;
 
    // if equal, then check for next combination
    if (X[m - 1] == Y[n - 1] && Y[n - 1] == Z[o - 1])
    {
 
      // recursive call
      return 1 + lcs(X, Y, Z, m - 1, n - 1, o - 1);
    }
    else
    {
 
      // return the maximum of the three other
      // possible states in recursion
      return Math.max(lcs(X, Y, Z, m, n - 1, o),
                      Math.max(lcs(X, Y, Z, m - 1, n, o),
                               lcs(X, Y, Z, m, n, o - 1)));
    }
  }
 
  // Driver code
  public static void main(String[] args)
  {
    char[] X = "geeks".toCharArray();
    char[] Y = "geeksfor".toCharArray();
    char[] Z = "geeksforge".toCharArray();
    int m = X.length;
    int n = Y.length;
    int o = Z.length;
    System.out.println("Length of LCS is " + lcs(X, Y, Z, m, n, o));
  }
}
 
// This code is contributed by divyesh072019.


Python3




# A recursive implementation of LCS problem of three strings
 
# Returns length of LCS for X[0..m-1], Y[0..n-1]
def lcs(X, Y, Z, m, n, o):
    # base case
    if m == 0 or n == 0 or o == 0:
      return 5
     
    # if equal, then check for next combination
    if X[m - 1] == Y[n - 1] and Y[n - 1] == Z[o - 1]:
      # recursive call
      return 1 + lcs(X, Y, Z, m - 1, n - 1, o - 1)
    else:
      # return the maximum of the three other
      # possible states in recursion
      return max(lcs(X, Y, Z, m, n - 1, o), max(lcs(X, Y, Z, m - 1, n, o), lcs(X, Y, Z, m, n, o - 1)))
 
X = "geeks".split()
Y = "geeksfor".split()
Z = "geeksforge".split()
m = len(X)
n = len(Y)
o = len(Z)
print("Length of LCS is", lcs(X, Y, Z, m, n, o))
 
# This code is contributed by rameshtravel07.


C#




// A recursive implementation of LCS problem
// of three strings
using System;
class GFG {
     
    // Utility function to get max of 2 integers
    static int max(int a, int b)
    {
        return (a > b) ? a : b;
    }
 
    // Returns length of LCS for X[0..m-1], Y[0..n-1]
    static int lcs(char[] X, char[] Y, char[] Z, int m, int n, int o)
    {
       
        // base case
        if (m == 0 || n == 0 || o == 0)
            return 0;
      
        // if equal, then check for next combination
        if (X[m - 1] == Y[n - 1] && Y[n - 1] == Z[o - 1])
        {
      
            // recursive call
            return 1 + lcs(X, Y, Z, m - 1, n - 1, o - 1);
        }
        else
        {
      
            // return the maximum of the three other
            // possible states in recursion
            return Math.Max(lcs(X, Y, Z, m, n - 1, o),
                       Math.Max(lcs(X, Y, Z, m - 1, n, o),
                           lcs(X, Y, Z, m, n, o - 1)));
        }
    }
 
  // Driver code
  static void Main()
  {
    char[] X = "geeks".ToCharArray();
    char[] Y = "geeksfor".ToCharArray();
    char[] Z = "geeksforge".ToCharArray();
    int m = X.Length;
    int n = Y.Length;
    int o = Z.Length;
    Console.WriteLine("Length of LCS is " + lcs(X, Y, Z, m, n, o));
  }
}
 
// This code is contributed by divyeshrabadiya07


Javascript




<script>
 
// A recursive implementation of LCS problem
// of three strings
     
    // Returns length of LCS for X[0..m-1], Y[0..n-1]
    function lcs(X,Y,Z,m,n,o)
    {
        // base case
    if (m == 0 || n == 0 || o == 0)
      return 0;
  
    // if equal, then check for next combination
    if (X[m - 1] == Y[n - 1] && Y[n - 1] == Z[o - 1])
    {
  
      // recursive call
      return 1 + lcs(X, Y, Z, m - 1, n - 1, o - 1);
    }
    else
    {
  
      // return the maximum of the three other
      // possible states in recursion
      return Math.max(lcs(X, Y, Z, m, n - 1, o),
                      Math.max(lcs(X, Y, Z, m - 1, n, o),
                               lcs(X, Y, Z, m, n, o - 1)));
    }
    }
     
    // Driver code
    let X = "geeks".split("");
    let Y = "geeksfor".split("");
    let Z = "geeksforge".split("");
    let m = X.length;
    let n = Y.length;
    let o = Z.length;
    document.write(
    "Length of LCS is " + lcs(X, Y, Z, m, n, o)
    );
     
 
// This code is contributed by unknown2108
 
</script>


Output: 

Length of LCS is 5

 

The tabulation method has been shown here. On drawing the recursion tree completely, it has been noticed that there are many overlapping sub-problems which are been calculated multiple times. Since the function parameter has three non-constant parameters, hence a 3-D array will be used to memorize the value that was returned when lcs(x, y, z, m, n, o) for any value of m, n, and o was called so that if lcs(x, y, z, m, n, o) is again called for the same value of m, n, and o then the function will return the already stored value as it has been computed previously in the recursive call. arr[m][n][o] stores the value returned by the lcs(x, y, z, m, n, o) function call. The only modification that needs to be done in the recursive program is to store the return value of (m, n, o) state of the recursive function. The rest remains the same in the above recursive program. 
Below is the implementation of the Memoization approach of the recursive code:  

C++




// A memoize recursive implementation of LCS problem
#include <bits/stdc++.h>
int arr[100][100][100];
int max(int a, int b);
 
// Returns length of LCS for X[0..m-1], Y[0..n-1] */
// memoization applied in recursive solution
int lcs(char* X, char* Y, char* Z, int m, int n, int o)
{
    // base case
    if (m == 0 || n == 0 || o == 0)
        return 0;
 
    // if the same state has already been
    // computed
    if (arr[m - 1][n - 1][o - 1] != -1)
        return arr[m - 1][n - 1][o - 1];
 
    // if equal, then we store the value of the
    // function call
    if (X[m - 1] == Y[n - 1] and Y[n - 1] == Z[o - 1]) {
 
        // store it in arr to avoid further repetitive work
        // in future function calls
        arr[m - 1][n - 1][o - 1] = 1 + lcs(X, Y, Z, m - 1,
                                            n - 1, o - 1);
        return arr[m - 1][n - 1][o - 1];
    }
    else {
 
        // store it in arr to avoid further repetitive work
        // in future function calls
        arr[m - 1][n - 1][o - 1] =
                               max(lcs(X, Y, Z, m, n - 1, o),
                                 max(lcs(X, Y, Z, m - 1, n, o),
                                    lcs(X, Y, Z, m, n, o - 1)));
        return arr[m - 1][n - 1][o - 1];
    }
}
 
// Utility function to get max of 2 integers
int max(int a, int b)
{
    return (a > b) ? a : b;
}
 
// Driver Code
int main()
{
    memset(arr, -1, sizeof(arr));
    char X[] = "geeks";
    char Y[] = "geeksfor";
    char Z[] = "geeksforgeeks";
    int m = strlen(X);
    int n = strlen(Y);
    int o = strlen(Z);
    printf("Length of LCS is %d", lcs(X, Y, Z, m, n, o));
 
    return 0;
}


Java




// A memoize recursive implementation of LCS problem
import java.io.*;
class GFG
{
   
  public static int[][][] arr = new int[100][100][100];
 
  // Returns length of LCS for X[0..m-1], Y[0..n-1] */
  // memoization applied in recursive solution
  static int lcs(String X, String Y, String Z,
                 int m, int n, int o)
  {
     
      // base case
      if (m == 0 || n == 0 || o == 0)
          return 0;
 
      // if the same state has already been
      // computed
      if (arr[m - 1][n - 1][o - 1] != -1)
          return arr[m - 1][n - 1][o - 1];
 
      // if equal, then we store the value of the
      // function call
      if (X.charAt(m - 1) == Y.charAt(n - 1) &&
          Y.charAt(n - 1) == Z.charAt(o - 1)) {
 
          // store it in arr to avoid further repetitive work
          // in future function calls
          arr[m - 1][n - 1][o - 1] = 1 + lcs(X, Y, Z, m - 1,
                                              n - 1, o - 1);
          return arr[m - 1][n - 1][o - 1];
      }
      else
      {
 
          // store it in arr to avoid further repetitive work
          // in future function calls
          arr[m - 1][n - 1][o - 1] =
                                 max(lcs(X, Y, Z, m, n - 1, o),
                                   max(lcs(X, Y, Z, m - 1, n, o),
                                      lcs(X, Y, Z, m, n, o - 1)));
          return arr[m - 1][n - 1][o - 1];
      }
  }
 
  // Utility function to get max of 2 integers
  static int max(int a, int b)
  {
      return (a > b) ? a : b;
  }
 
  // Driver Code
  public static void main (String[] args)
  
    for(int i = 0; i < 100; i++)
    {
      for(int j = 0; j < 100; j++)
      {
        for(int k = 0; k < 100; k++)
        {
          arr[i][j][k] = -1;
        }
      }
    }
     
    String X = "geeks";
    String Y = "geeksfor";
    String Z = "geeksforgeeks";
    int m = X.length();
    int n = Y.length();
    int o = Z.length();
    System.out.print("Length of LCS is " + lcs(X, Y, Z, m, n, o));
  }
}
 
// This code is contributed by Dharanendra L V.


Python3




# A memoize recursive implementation of LCS problem
 
# Returns length of LCS for X[0..m-1], Y[0..n-1] */
# memoization applied in recursive solution
def lcs(X, Y, Z, m, n, o):
    global arr
 
    # base case
    if(m == 0 or n == 0 or o == 0):
        return 0
 
    # if the same state has already been
    # computed
    if (arr[m - 1][n - 1][o - 1] != -1):
        return arr[m - 1][n - 1][o - 1]
 
    # if equal, then we store the value of the
    # function call
    if (X[m - 1] == Y[n - 1] and
            Y[n - 1] == Z[o - 1]):
 
        # store it in arr to avoid further repetitive work
        # in future function calls
        arr[m - 1][n - 1][o - 1] = 1 + lcs(X, Y, Z, m - 1,
                                           n - 1, o - 1)
        return arr[m - 1][n - 1][o - 1]
 
    else:
 
        # store it in arr to avoid further repetitive work
        # in future function calls
        arr[m - 1][n - 1][o - 1] = max(lcs(X, Y, Z, m, n - 1, o),
                                       max(lcs(X, Y, Z, m - 1, n, o), lcs(X, Y, Z, m, n, o - 1)))
        return arr[m - 1][n - 1][o - 1]
 
# Driver Code
arr = [[[0 for k in range(100)] for j in range(100)] for i in range(100)]
 
for i in range(100):
    for j in range(100):
        for k in range(100):
            arr[i][j][k] = -1
 
X = "geeks"
Y = "geeksfor"
Z = "geeksforgeeks"
m = len(X)
n = len(Y)
o = len(Z)
print("Length of LCS is ", lcs(X, Y, Z, m, n, o))
 
# This code is contributed by Dharanendra L V.


C#




// A memoize recursive implementation of LCS problem
using System;
public class GFG{
 
  public static int[, , ] arr = new int[100, 100, 100];
 
  // Returns length of LCS for X[0..m-1], Y[0..n-1] */
  // memoization applied in recursive solution
  static int lcs(String X, String Y, String Z, int m, int n, int o)
  {
      // base case
      if (m == 0 || n == 0 || o == 0)
          return 0;
 
      // if the same state has already been
      // computed
      if (arr[m - 1, n - 1, o - 1] != -1)
          return arr[m - 1, n - 1, o - 1];
 
      // if equal, then we store the value of the
      // function call
      if (X[m - 1] == Y[n - 1] &&
          Y[n - 1] == Z[o - 1]) {
 
          // store it in arr to avoid further repetitive work
          // in future function calls
          arr[m - 1, n - 1, o - 1] = 1 + lcs(X, Y, Z, m - 1,
                                              n - 1, o - 1);
          return arr[m - 1, n - 1, o - 1];
      }
      else {
 
          // store it in arr to avoid further repetitive work
          // in future function calls
          arr[m - 1, n - 1, o - 1] =
                                 max(lcs(X, Y, Z, m, n - 1, o),
                                   max(lcs(X, Y, Z, m - 1, n, o),
                                      lcs(X, Y, Z, m, n, o - 1)));
          return arr[m - 1, n - 1, o - 1];
      }
  }
 
  // Utility function to get max of 2 integers
  static int max(int a, int b)
  {
      return (a > b) ? a : b;
  }
 
  // Driver Code
  static public void Main (){
 
    for(int i = 0; i < 100; i++) {
      for(int j = 0; j < 100; j++) {
        for(int k = 0; k < 100; k++) {
          arr[i, j, k] = -1;
        }
      }
    }
     
    String X = "geeks";
    String Y = "geeksfor";
    String Z = "geeksforgeeks";
    int m = X.Length;
    int n = Y.Length;
    int o = Z.Length;
    Console.WriteLine("Length of LCS is " + lcs(X, Y, Z, m, n, o));
  }
}
 
// This code is contributed by Dharanendra L V.


Javascript




<script>
// A memoize recursive implementation of LCS problem
     
    let arr=new Array(100);
    for(let i=0;i<100;i++)
    {
        arr[i]=new Array(100);
        for(let j=0;j<100;j++)
        {
            arr[i][j]=new Array(100);
            for(let k=0;k<100;k++)
            {
                arr[i][j][k]=-1;
            }
        }
    }
     
    // Returns length of LCS for X[0..m-1], Y[0..n-1] */
  // memoization applied in recursive solution
    function lcs(X,Y,Z,m,n,o)
    {
        // base case
      if (m == 0 || n == 0 || o == 0)
          return 0;
  
      // if the same state has already been
      // computed
      if (arr[m - 1][n - 1][o - 1] != -1)
          return arr[m - 1][n - 1][o - 1];
  
      // if equal, then we store the value of the
      // function call
      if (X[m-1] == Y[n-1] &&
          Y[n-1] == Z[o-1]) {
  
          // store it in arr to avoid further repetitive work
          // in future function calls
          arr[m - 1][n - 1][o - 1] = 1 + lcs(X, Y, Z, m - 1,
                                              n - 1, o - 1);
          return arr[m - 1][n - 1][o - 1];
      }
      else
      {
  
          // store it in arr to avoid further repetitive work
          // in future function calls
          arr[m - 1][n - 1][o - 1] =
                                 max(lcs(X, Y, Z, m, n - 1, o),
                                   max(lcs(X, Y, Z, m - 1, n, o),
                                      lcs(X, Y, Z, m, n, o - 1)));
          return arr[m - 1][n - 1][o - 1];
      }
    }
     
    // Utility function to get max of 2 integers
    function max(a,b)
    {
         return (a > b) ? a : b;
    }
     
    // Driver Code
    let X = "geeks";
    let Y = "geeksfor";
    let Z = "geeksforgeeks";
    let m = X.length;
    let n = Y.length;
    let o = Z.length;
    document.write("Length of LCS is " + lcs(X, Y, Z, m, n, o));
     
     
 
 
// This code is contributed by patel2127
</script>


Output: 

Length of LCS is 5

 

Note: The array used to Memoize is initialized to some value (say -1) before the function call to mark if the function with the same parameters has been previously called or not.
 



Similar Reads

Edit Distance | DP using Memoization
Given two strings str1 and str2 and below operations that can be performed on str1. Find the minimum number of edits (operations) required to convert 'str1' into 'str2'. InsertRemoveReplace All of the above operations are of equal cost. Examples: Input: str1 = "geek", str2 = "gesek" Output: 1 We can convert str1 into str2 by inserting a 's'. Input:
15+ min read
Water Jug Problem using Memoization
Given two jugs with the maximum capacity of m and n liters respectively. The jugs don't have markings on them which can help us to measure smaller quantities. The task is to measure d liters of water using these two jugs. Hence our goal is to reach from initial state (m, n) to final state (0, d) or (d, 0). Examples: Input: 4 3 2 Output: (0, 0) --
9 min read
Longest Common Subsequence | DP using Memoization
Given two strings s1 and s2, the task is to find the length of the longest common subsequence present in both of them. Examples: Input: s1 = “ABCDGH”, s2 = “AEDFHR” Output: 3 LCS for input Sequences “AGGTAB” and “GXTXAYB” is “GTAB” of length 4. Input: s1 = “striver”, s2 = “raj” Output: 1 The naive solution for this problem is to generate all subseq
13 min read
Tabulation vs Memoization
Tabulation and memoization are two techniques used in dynamic programming to optimize the execution of a function that has repeated and expensive computations. Although both techniques have similar goals, there are some differences between them. Memoization is a top-down approach where we cache the results of function calls and return the cached re
10 min read
Numbers of Length N having digits A and B and whose sum of digits contain only digits A and B
Given three positive integers N, A, and B. The task is to count the numbers of length N containing only digits A and B and whose sum of digits also contains the digits A and B only. Print the answer modulo 109 + 7.Examples: Input: N = 3, A = 1, B = 3 Output: 1 Possible numbers of length 3 are 113, 131, 111, 333, 311, 331 and so on... But only 111 i
15 min read
Count ways to generate pairs having Bitwise XOR and Bitwise AND equal to X and Y respectively
Given two integers X and Y, the task is to find the total number of ways to generate a pair of integers A and B such that Bitwise XOR and Bitwise AND between A and B is X and Y respectively Examples: Input: X = 2, Y = 5Output: 2Explanation:The two possible pairs are (5, 7) and (7, 5).Pair 1: (5, 7)Bitwise AND = 5 & 7 = 2Bitwise XOR = 5 ^ 7 = 5P
7 min read
Sum of Bitwise AND of sum of pairs and their Bitwise AND from a given array
Given an array arr[] consisting of N integers, the task is to find the sum of Bitwise AND of (arr[i] + arr[j]) and Bitwise AND of arr[i] and arr[j] for each pair of elements (arr[i], arr[j]) from the given array. Since the sum can be very large, print it modulo (109 + 7). Examples: Input: arr[] = {8, 9}Output: 0Explanation: The only pair from the a
9 min read
Max count of N using digits of M such that 2 and 5, and, 6 and 9 can be treated as same respectively
Given an integer N, and the string integer M, the task is to find the total count to make N by using the digits of string M. Also, digit 2 can be treated as digit 5, and digit 6 can be treated as digit 9 and vice versa and each digit from the string M can be used at most once. Examples: Input: N = 6, M = "245769"Output: 2Explanation: Digits 5 and 6
12 min read
Reduce Array and Maximize sum by deleting one occurrence of A[i] and all occurrences of A[i]+1 and A[i]-1
Given an array A[] having N positive integers, the task is to perform the following operations and maximize the sum obtained while reducing the array: Select an array element (say A[i]) and delete one occurrence of that element and add A[i] to the sum.Delete all the occurrences of A[i]-1 and A[i]+1.Perform these operations until the array is empty.
8 min read
Multiply two integers without using multiplication, division and bitwise operators, and no loops
By making use of recursion, we can multiply two integers with the given constraints. To multiply x and y, recursively add x y times. Approach: Since we cannot use any of the given symbols, the only way left is to use recursion, with the fact that x is to be added to x y times. Base case: When the numbers of times x has to be added becomes 0. Recurs
9 min read
Count of Ways to Choose N People With at Least X Men and Y Women from P Men and Q Women | Set 2
Given integers N, P, Q, X, and Y, the task is to find the number of ways to form a group of N people having at least X men and Y women from P men and Q women, where (X + Y ≤ N, X ≤ P and Y ≤ Q). Examples: Input: P = 4, Q = 2, N = 5, X = 3, Y = 1Output: 6Explanation: Suppose given pool is {m1, m2, m3, m4} and {w1, w2}. Then possible combinations are
7 min read
Python counter and dictionary intersection example (Make a string using deletion and rearrangement)
Given two strings, find if we can make first string from second by deleting some characters from second and rearranging remaining characters. Examples: Input : s1 = ABHISHEKsinGH : s2 = gfhfBHkooIHnfndSHEKsiAnG Output : Possible Input : s1 = Hello : s2 = dnaKfhelddf Output : Not Possible Input : s1 = GeeksforGeeks : s2 = rteksfoGrdsskGeggehes Outpu
2 min read
Rearrange array such that arr[i] >= arr[j] if i is even and arr[i]<=arr[j] if i is odd and j < i
Given an array of n elements. Our task is to write a program to rearrange the array such that elements at even positions are greater than all elements before it and elements at odd positions are less than all elements before it.Examples: Input : arr[] = {1, 2, 3, 4, 5, 6, 7} Output : 4 5 3 6 2 7 1 Input : arr[] = {1, 2, 1, 4, 5, 6, 8, 8} Output : 4
11 min read
Find speed of man from speed of stream and ratio of time with up and down streams
Program to find the speed of man in km/hr, given the speed of stream in km/hr. Assume that the man takes n times (where n > 1) as long to row upstream as to row downstream the river.Examples: Input : 5.5 4 Output : speed of man is 9.16667 km/hr Input : 4 3 Output : speed of man is 8 km/hr Approach Used :Let speed of the man in still water = x km
4 min read
Substrings starting with vowel and ending with consonants and vice versa
Given a string s, count special substrings in it. A Substring of S is said to be special if either of the following properties is satisfied. It starts with a vowel and ends with a consonant.It starts with a consonant and ends with a vowel. Examples: Input : S = "aba" Output : 2 Substrings of S are : a, ab, aba, b, ba, a Out of these only 'ab' and '
15+ min read
Comparison of an Array and Hash table in terms of Storage structure and Access time complexity
Arrays and Hash Tables are two of the most widely used data structures in computer science, both serving as efficient solutions for storing and accessing data in Java. They have different storage structures and time complexities, making them suitable for different use cases. In this article, we will explore the differences between arrays and hash t
3 min read
Reach A and B by multiplying them with K and K^2 at every step
We are given two numbers A and B, we need to write a program to determine if A and B can be reached starting from (1, 1) following the given steps. Start from (1, 1) and at every step choose a random number K and multiply K to any one of the two numbers obtained in the previous step and K2 to the other number. Examples: Input: A = 3, B = 9 Output:
6 min read
Queries to insert, delete one occurrence of a number and print the least and most frequent element
Given Q queries of type 1, 2, 3 and 4 as described below. Type-1: Insert a number to the list.Type-2: Delete only one occurrence of a number if exists.Type-3: Print the least frequent element, if multiple elements exist then print the greatest among them.Type-4: Print the most frequent element, if multiple elements exist then print the smallest amo
14 min read
Maximize the sum of X+Y elements by picking X and Y elements from 1st and 2nd array
Given two arrays of size N, and two numbers X and Y, the task is to maximize the sum by considering the below points: Pick x values from the first array and y values from the second array such that the sum of X+Y values is maximum.It is given that X + Y is equal to N. Examples: Input: arr1[] = {1, 4, 1}, arr2[] = {2, 5, 3}, N = 3, X = 2, Y = 1 Outp
12 min read
Sum of elements in range L-R where first half and second half is filled with odd and even numbers
Given a number N, create an array such the first half of the array is filled with odd numbers till N, and the second half of the array is filled with even numbers. Also given are L and R indices, the task is to print the sum of elements in the array in the range [L, R]. Examples: Input: N = 12, L = 1, R = 11 Output: 66 The array formed thus is {1,
15+ min read
Segregating negative and positive maintaining order and O(1) space
Segregation of negative and positive numbers in an array without using extra space, and maintaining insertion order and in O(n^2) time complexity. Examples: Input :9 12 11 -13 -5 6 -7 5 -3 -6 Output :-13 -5 -7 -3 -6 12 11 6 5 Input :5 11 -13 6 -7 5 Output :-13 -7 11 6 5 We have discussed this problem below posts. ers-beginning-positive-end-constant
7 min read
Split array to three subarrays such that sum of first and third subarray is equal and maximum
Given an array of N integers, the task is to print the sum of the first subarray by splitting the array into exactly three subarrays such that the sum of the first and third subarray elements are equal and the maximum. Note: All the elements must belong to a subarray and the subarrays can also be empty. Examples: Input: a[] = {1, 3, 1, 1, 4} Output
13 min read
Queries to add, remove and return the difference of maximum and minimum.
Given Q queries. The queries are of three types and are described below: Add the number num to the list.Remove the number num from the list.Return the difference between the maximum and minimum number in the list. The task is to write a program the performs the above queries. Note: The numbers are distinct and at every call of query-3, there will b
6 min read
Number of solutions for x < y, where a <= x <= b and c <= y <= d and x, y are integers
Given four integers a, b, c, d ( upto 10^6 ). The task is to Find the number of solutions for x < y, where a <= x <= b and c <= y <= d and x, y integers. Examples: Input: a = 2, b = 3, c = 3, d = 4 Output: 3 Input: a = 3, b = 5, c = 6, d = 7 Output: 6 Approach: Let’s iterate explicitly over all possible values of x. For one such fixe
6 min read
Sum and Product of minimum and maximum element of an Array
Given an array. The task is to find the sum and product of the maximum and minimum elements of the given array. Examples: Input : arr[] = {12, 1234, 45, 67, 1} Output : Sum = 1235 Product = 1234 Input : arr[] = {5, 3, 6, 8, 4, 1, 2, 9} Output : Sum = 10 Product = 9 Take two variables min and max to store the minimum and maximum elements of the arra
13 min read
Sum and Product of maximum and minimum element in Binary Tree
Given a Binary Tree. The task is to find the sum and product of the maximum and minimum elements in it. For example, sum of the maximum and minimum elements in the following binary tree is 10 and the product is 9. The idea is to traverse the tree and find the maximum and minimum elements in the tree and print their product and sum. To find the maxi
12 min read
Sum and Product of minimum and maximum element of Binary Search Tree
Given a Binary Search Tree. The task is to find the sum and product of the maximum and minimum value of the tree. For the above tree, the sum and product of the maximum and minimum values of the tree are 26 and 88 respectively. Approach: For the node with the minimum value: Find the leftmost leaf nodeFor the node with the maximum value: Find the ri
8 min read
Find subsequences with maximum Bitwise AND and Bitwise OR
Given an array of n elements. The task is to print the maximum sum by selecting two subsequences of the array (not necessarily different) such that the sum of bitwise AND of all elements of the first subsequence and bitwise OR of all the elements of the second subsequence is maximum. Examples: Input: arr[] = {3, 5, 6, 1} Output: 13 We get maximum A
4 min read
Sum and product of k smallest and k largest composite numbers in the array
Given an integer k and an array of integers arr, the task is to find the sum and product of k smallest and k largest composite numbers in the array. Assume that there are at least k composite numbers in the array. Examples: Input: arr[] = {2, 5, 6, 8, 10, 11}, k = 2 Output: Sum of k-minimum composite numbers is 14 Sum of k-maximum composite numbers
15+ min read
Count pairs (A, B) such that A has X and B has Y number of set bits and A+B = C
Given two numbers x, y which denotes the number of set bits. Also given is a number C. The task is to print the number of ways in which we can form two numbers A and B such that A has x number of set bits and B has y number of set bits and A+B = C.Examples: Input: X = 1, Y = 1, C = 3 Output: 2 So two possible ways are (A = 2 and B = 1) and (A = 1 a
15+ min read
three90RightbarBannerImg