Posted on by Kalkicode
Code Dynamic Programming

Lobb number

The given problem deals with the concept of Lobb numbers. Lobb numbers are a sequence of numbers that count the number of ways open and close parentheses can be arranged to form a valid sequence of balanced parentheses. A valid sequence of balanced parentheses is one in which each open parenthesis is properly closed by a corresponding closing parenthesis, and no closing parenthesis is unmatched.

In the problem, we are given two integers 'n' and 'm', and we need to calculate the Lobb number L(n, m). L(n, m) counts the number of ways that 'n + m' open parentheses and 'n − m' close parentheses can be arranged to form a valid sequence of balanced parentheses.

Explanation with Suitable Example

Let's consider the example of Lobb(3, 2).

Here, n = 3 and m = 2.

So, we have 'n + m' = 5 open parentheses and 'n − m' = 1 close parenthesis.

The valid sequences of balanced parentheses can be represented as:

((()))
(())()
()(())
()()()
(()())

So, there are 5 different valid sequences possible for Lobb(3, 2).

Pseudocode

Before diving into the pseudocode for the Lobb number calculation, let's understand the function binomialCoefficient(n, k), which calculates the binomial coefficient C(n, k) using dynamic programming. 

// Function to calculate binomial coefficient C(n, k)
function binomialCoefficient(n, k):
    create a 2D array c[n+1][k+1]
    
    for i from 0 to n do:
        for j from 0 to min(i, k) do:
            if j is 0 or j is equal to i then:
                c[i][j] = 1   // Base cases
            else:
                c[i][j] = c[i-1][j-1] + c[i-1][j]
    
    return c[n][k]

// Function to calculate Lobb number L(n, m)
function lobbNumber(n, m):
    result = (((2 * m) + 1) * binomialCoefficient(2 * n, m + n)) / (m + n + 1)
    print "Given n:", n, ", m:", m
    print result

// Test cases
lobbNumber(6, 6)
lobbNumber(4, 2)
lobbNumber(3, 2)

  1. Function binomialCoefficient(n, k): a. Create a 2D array c[n+1][k+1]. b. Iterate over 'i' from 0 to 'n': i. Iterate over 'j' from 0 to minimum of (i, k): - If 'j' is 0 or 'j' is equal to 'i', set c[i][j] to 1 (base cases). - Otherwise, set c[i][j] to c[i-1][j-1] + c[i-1][j]. c. Return c[n][k].

  2. Function lobbNumber(n, m): a. Calculate the result as: (((2 * m) + 1) * binomialCoefficient(2 * n, m + n)) / (m + n + 1). b. Print the result.

Algorithm Explanation

  1. First, we need to calculate the binomial coefficient using the function binomialCoefficient(n, k).

  2. Then, we calculate the Lobb number using the formula:

    L(n, m) = (((2 * m) + 1) * C(2 * n, m + n)) / (m + n + 1).

  3. Finally, we print the Lobb number for the given 'n' and 'm'.

Code Solution

// C Program for
// Lobb number
#include <stdio.h>

int minValue(int a, int b)
{
    if (a < b)
    {
        return a;
    }
    return b;
}
int binomialCoefficient(int n, int k)
{
    int c[n + 1][k + 1];
    for (int i = 0; i <= n; ++i)
    {
        for (int j = 0; j <= minValue(i, k); ++j)
        {
            if (j == 0 || j == i)
            {
                c[i][j] = 1;
            }
            else
            {
                c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
            }
        }
    }
    return c[n][k];
}
void lobbNumber(int n, int m)
{
    //  Lm,n counts the number of ways that n + m open parentheses 
    //  and n − m close parentheses can be arranged to form 
    //  the start of a valid sequence of balanced parentheses.
    int result = (((2 * m) + 1) * 
                  binomialCoefficient(2 *n, m + n)) / (m + n + 1);
    printf("\n Given n : %d , m : %d", n, m);
    printf("\n %d", result);
}
int main()
{
    // Test A
    // n = 6 
    // m = 6
    lobbNumber(6, 6);
    // Test B
    // n = 4 
    // m = 2
    lobbNumber(4, 2);
    // Test C
    // n = 3 
    // m = 2
    lobbNumber(3, 2);
    return 0;
}

Output

 Given n : 6 , m : 6
 1
 Given n : 4 , m : 2
 20
 Given n : 3 , m : 2
 5
/*
    Java program for
    Lobb number
*/
public class LobbNumber
{
	public int minValue(int a, int b)
	{
		if (a < b)
		{
			return a;
		}
		return b;
	}
	public int binomialCoefficient(int n, int k)
	{
		int[][] c = new int[n + 1][k + 1];
		for (int i = 0; i <= n; ++i)
		{
			for (int j = 0; j <= minValue(i, k); ++j)
			{
				if (j == 0 || j == i)
				{
					c[i][j] = 1;
				}
				else
				{
					c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
				}
			}
		}
		return c[n][k];
	}
	public void lobbNo(int n, int m)
	{
		//  Lm,n counts the number of ways that n + m open parentheses 
		//  and n − m close parentheses can be arranged to form 
		//  the start of a valid sequence of balanced parentheses.
		int result = (((2 * m) + 1) * 
                      binomialCoefficient(2 * n, m + n)) / (m + n + 1);
		System.out.print("\n Given n : " + n + " , m : " + m);
		System.out.print("\n " + result);
	}
	public static void main(String[] args)
	{
		LobbNumber task = new LobbNumber();
		// Test A
		// n = 6 
		// m = 6
		task.lobbNo(6, 6);
		// Test B
		// n = 4 
		// m = 2
		task.lobbNo(4, 2);
		// Test C
		// n = 3 
		// m = 2
		task.lobbNo(3, 2);
	}
}

Output

 Given n : 6 , m : 6
 1
 Given n : 4 , m : 2
 20
 Given n : 3 , m : 2
 5
// Include header file
#include <iostream>
using namespace std;
/*
    C++ program for
    Lobb number
*/
class LobbNumber
{
	public: int minValue(int a, int b)
	{
		if (a < b)
		{
			return a;
		}
		return b;
	}
	int binomialCoefficient(int n, int k)
	{
		int c[n + 1][k + 1];
		for (int i = 0; i <= n; ++i)
		{
			for (int j = 0; j <= this->minValue(i, k); ++j)
			{
				if (j == 0 || j == i)
				{
					c[i][j] = 1;
				}
				else
				{
					c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
				}
			}
		}
		return c[n][k];
	}
	void lobbNo(int n, int m)
	{
		//  Lm,n counts the number of ways that n + m open parentheses 
		//  and n − m close parentheses can be arranged to form 
		//  the start of a valid sequence of balanced parentheses.
		int result = (((2 *m) + 1) *
                      this->binomialCoefficient(2 *n, m + n)) / (m + n + 1);
		cout << "\n Given n : " << n << " , m : " << m;
		cout << "\n " << result;
	}
};
int main()
{
	LobbNumber *task = new LobbNumber();
	// Test A
	// n = 6 
	// m = 6
	task->lobbNo(6, 6);
	// Test B
	// n = 4 
	// m = 2
	task->lobbNo(4, 2);
	// Test C
	// n = 3 
	// m = 2
	task->lobbNo(3, 2);
	return 0;
}

Output

 Given n : 6 , m : 6
 1
 Given n : 4 , m : 2
 20
 Given n : 3 , m : 2
 5
// Include namespace system
using System;
/*
    Csharp program for
    Lobb number
*/
public class LobbNumber
{
	public int minValue(int a, int b)
	{
		if (a < b)
		{
			return a;
		}
		return b;
	}
	public int binomialCoefficient(int n, int k)
	{
		int[,] c = new int[n + 1,k + 1];
		for (int i = 0; i <= n; ++i)
		{
			for (int j = 0; j <= this.minValue(i, k); ++j)
			{
				if (j == 0 || j == i)
				{
					c[i,j] = 1;
				}
				else
				{
					c[i,j] = c[i - 1,j - 1] + c[i - 1,j];
				}
			}
		}
		return c[n,k];
	}
	public void lobbNo(int n, int m)
	{
		//  Lm,n counts the number of ways that n + m open parentheses 
		//  and n − m close parentheses can be arranged to form 
		//  the start of a valid sequence of balanced parentheses.
		int result = (((2 * m) + 1) * 
                      this.binomialCoefficient(2 * n, m + n)) / (m + n + 1);
		Console.Write("\n Given n : " + n + " , m : " + m);
		Console.Write("\n " + result);
	}
	public static void Main(String[] args)
	{
		LobbNumber task = new LobbNumber();
		// Test A
		// n = 6 
		// m = 6
		task.lobbNo(6, 6);
		// Test B
		// n = 4 
		// m = 2
		task.lobbNo(4, 2);
		// Test C
		// n = 3 
		// m = 2
		task.lobbNo(3, 2);
	}
}

Output

 Given n : 6 , m : 6
 1
 Given n : 4 , m : 2
 20
 Given n : 3 , m : 2
 5
package main
import "fmt"
/*
    Go program for
    Lobb number
*/

func minValue(a, b int) int {
	if a < b {
		return a
	}
	return b
}
func binomialCoefficient(n, k int) int {
	var c = make([][] int, n + 1)
	for i:= 0; i < n + 1;i++ {
		c[i] = make([]int,k+1)
	}
	for i := 0 ; i <= n ; i++ {
		for j := 0 ; j <= minValue(i, k) ; j++ {
			if j == 0 || j == i {
				c[i][j] = 1
			} else {
				c[i][j] = c[i - 1][j - 1] + c[i - 1][j]
			}
		}
	}
	return c[n][k]
}
func lobbNo(n, m int) {
	//  Lm,n counts the number of ways that n + m open parentheses 
	//  and n − m close parentheses can be arranged to form 
	//  the start of a valid sequence of balanced parentheses.
	var result int = (((2 * m) + 1) * 
		binomialCoefficient(2 * n, m + n)) / (m + n + 1)
	fmt.Print("\n Given n : ", n, " , m : ", m)
	fmt.Print("\n ", result)
}
func main() {

	// Test A
	// n = 6 
	// m = 6
	lobbNo(6, 6)
	// Test B
	// n = 4 
	// m = 2
	lobbNo(4, 2)
	// Test C
	// n = 3 
	// m = 2
	lobbNo(3, 2)
}

Output

 Given n : 6 , m : 6
 1
 Given n : 4 , m : 2
 20
 Given n : 3 , m : 2
 5
<?php
/*
    Php program for
    Lobb number
*/
class LobbNumber
{
	public	function minValue($a, $b)
	{
		if ($a < $b)
		{
			return $a;
		}
		return $b;
	}
	public	function binomialCoefficient($n, $k)
	{
		$c = array_fill(0, $n + 1, array_fill(0, $k + 1, 0));
		for ($i = 0; $i <= $n; ++$i)
		{
			for ($j = 0; $j <= $this->minValue($i, $k); ++$j)
			{
				if ($j == 0 || $j == $i)
				{
					$c[$i][$j] = 1;
				}
				else
				{
					$c[$i][$j] = $c[$i - 1][$j - 1] + $c[$i - 1][$j];
				}
			}
		}
		return $c[$n][$k];
	}
	public	function lobbNo($n, $m)
	{
		//  Lm,n counts the number of ways that n + m open parentheses 
		//  and n − m close parentheses can be arranged to form 
		//  the start of a valid sequence of balanced parentheses.
		$result = (int)((((2 * $m) + 1) * 
                         $this->binomialCoefficient(2 * $n, $m + $n)) / 
                        ($m + $n + 1));
		echo("\n Given n : ".$n.
			" , m : ".$m);
		echo("\n ".$result);
	}
}

function main()
{
	$task = new LobbNumber();
	// Test A
	// n = 6 
	// m = 6
	$task->lobbNo(6, 6);
	// Test B
	// n = 4 
	// m = 2
	$task->lobbNo(4, 2);
	// Test C
	// n = 3 
	// m = 2
	$task->lobbNo(3, 2);
}
main();

Output

 Given n : 6 , m : 6
 1
 Given n : 4 , m : 2
 20
 Given n : 3 , m : 2
 5
/*
    Node JS program for
    Lobb number
*/
class LobbNumber
{
	minValue(a, b)
	{
		if (a < b)
		{
			return a;
		}
		return b;
	}
	binomialCoefficient(n, k)
	{
		var c = Array(n + 1).fill(0).map(() => new Array(k + 1).fill(0));
		for (var i = 0; i <= n; ++i)
		{
			for (var j = 0; j <= this.minValue(i, k); ++j)
			{
				if (j == 0 || j == i)
				{
					c[i][j] = 1;
				}
				else
				{
					c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
				}
			}
		}
		return c[n][k];
	}
	lobbNo(n, m)
	{
		//  Lm,n counts the number of ways that n + m open parentheses 
		//  and n − m close parentheses can be arranged to form 
		//  the start of a valid sequence of balanced parentheses.
		var result = parseInt((((2 * m) + 1) * 
                               this.binomialCoefficient(2 * n, m + n)) / 
                              (m + n + 1));
		process.stdout.write("\n Given n : " + n + " , m : " + m);
		process.stdout.write("\n " + result);
	}
}

function main()
{
	var task = new LobbNumber();
	// Test A
	// n = 6 
	// m = 6
	task.lobbNo(6, 6);
	// Test B
	// n = 4 
	// m = 2
	task.lobbNo(4, 2);
	// Test C
	// n = 3 
	// m = 2
	task.lobbNo(3, 2);
}
main();

Output

 Given n : 6 , m : 6
 1
 Given n : 4 , m : 2
 20
 Given n : 3 , m : 2
 5
#    Python 3 program for
#    Lobb number
class LobbNumber :
	def minValue(self, a, b) :
		if (a < b) :
			return a
		
		return b
	
	def binomialCoefficient(self, n, k) :
		c = [[0] * (k + 1) for _ in range(n + 1) ]
		i = 0
		while (i <= n) :
			j = 0
			while (j <= self.minValue(i, k)) :
				if (j == 0 or j == i) :
					c[i][j] = 1
				else :
					c[i][j] = c[i - 1][j - 1] + c[i - 1][j]
				
				j += 1
			
			i += 1
		
		return c[n][k]
	
	def lobbNo(self, n, m) :
		#   Lm,n counts the number of ways that n + m open parentheses 
		#   and n − m close parentheses can be arranged to form 
		#   the start of a valid sequence of balanced parentheses.
		result = int((((2 * m) + 1) * 
                      self.binomialCoefficient(2 * n, m + n)) / (m + n + 1))
		print("\n Given n : ", n ," , m : ", m, end = "")
		print("\n ", result, end = "")
	

def main() :
	task = LobbNumber()
	#  Test A
	#  n = 6 
	#  m = 6
	task.lobbNo(6, 6)
	#  Test B
	#  n = 4 
	#  m = 2
	task.lobbNo(4, 2)
	#  Test C
	#  n = 3 
	#  m = 2
	task.lobbNo(3, 2)

if __name__ == "__main__": main()

Output

 Given n :  6  , m :  6
  1
 Given n :  4  , m :  2
  20
 Given n :  3  , m :  2
  5
#    Ruby program for
#    Lobb number
class LobbNumber 
	def minValue(a, b) 
		if (a < b) 
			return a
		end

		return b
	end

	def binomialCoefficient(n, k) 
		c = Array.new(n + 1) {Array.new(k + 1) {0}}
		i = 0
		while (i <= n) 
			j = 0
			while (j <= self.minValue(i, k)) 
				if (j == 0 || j == i) 
					c[i][j] = 1
				else
 
					c[i][j] = c[i - 1][j - 1] + c[i - 1][j]
				end

				j += 1
			end

			i += 1
		end

		return c[n][k]
	end

	def lobbNo(n, m) 
		#   Lm,n counts the number of ways that n + m open parentheses 
		#   and n − m close parentheses can be arranged to form 
		#   the start of a valid sequence of balanced parentheses.
		result = (((2 * m) + 1) * 
                  self.binomialCoefficient(2 * n, m + n)) / (m + n + 1)
		print("\n Given n : ", n ," , m : ", m)
		print("\n ", result)
	end

end

def main() 
	task = LobbNumber.new()
	#  Test A
	#  n = 6 
	#  m = 6
	task.lobbNo(6, 6)
	#  Test B
	#  n = 4 
	#  m = 2
	task.lobbNo(4, 2)
	#  Test C
	#  n = 3 
	#  m = 2
	task.lobbNo(3, 2)
end

main()

Output

 Given n : 6 , m : 6
 1
 Given n : 4 , m : 2
 20
 Given n : 3 , m : 2
 5
/*
    Scala program for
    Lobb number
*/
class LobbNumber()
{
	def minValue(a: Int, b: Int): Int = {
		if (a < b)
		{
			return a;
		}
		return b;
	}
	def binomialCoefficient(n: Int, k: Int): Int = {
		var c: Array[Array[Int]] = Array.fill[Int](n + 1, k + 1)(0);
		var i: Int = 0;
		while (i <= n)
		{
			var j: Int = 0;
			while (j <= minValue(i, k))
			{
				if (j == 0 || j == i)
				{
					c(i)(j) = 1;
				}
				else
				{
					c(i)(j) = c(i - 1)(j - 1) + c(i - 1)(j);
				}
				j += 1;
			}
			i += 1;
		}
		return c(n)(k);
	}
	def lobbNo(n: Int, m: Int): Unit = {
		//  Lm,n counts the number of ways that n + m open parentheses 
		//  and n − m close parentheses can be arranged to form 
		//  the start of a valid sequence of balanced parentheses.
		var result: Int = (((2 * m) + 1) * 
          binomialCoefficient(2 * n, m + n)) / (m + n + 1);
		print("\n Given n : " + n + " , m : " + m);
		print("\n " + result);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: LobbNumber = new LobbNumber();
		// Test A
		// n = 6 
		// m = 6
		task.lobbNo(6, 6);
		// Test B
		// n = 4 
		// m = 2
		task.lobbNo(4, 2);
		// Test C
		// n = 3 
		// m = 2
		task.lobbNo(3, 2);
	}
}

Output

 Given n : 6 , m : 6
 1
 Given n : 4 , m : 2
 20
 Given n : 3 , m : 2
 5
/*
    Swift 4 program for
    Lobb number
*/
class LobbNumber
{
	func minValue(_ a: Int, _ b: Int) -> Int
	{
		if (a < b)
		{
			return a;
		}
		return b;
	}
	func binomialCoefficient(_ n: Int, _ k: Int) -> Int
	{
		var c: [
			[Int]
		] = Array(repeating: Array(repeating: 0, count: k + 1), count: n + 1);
		var i: Int = 0;
		while (i <= n)
		{
			var j: Int = 0;
			while (j <= self.minValue(i, k))
			{
				if (j == 0 || j == i)
				{
					c[i][j] = 1;
				}
				else
				{
					c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
				}
				j += 1;
			}
			i += 1;
		}
		return c[n][k];
	}
	func lobbNo(_ n: Int, _ m: Int)
	{
		//  Lm,n counts the number of ways that n + m open parentheses 
		//  and n − m close parentheses can be arranged to form 
		//  the start of a valid sequence of balanced parentheses.
		let result: Int = (((2 * m) + 1) * 
                           self.binomialCoefficient(2 * n, m + n)) / 
          (m + n + 1);
		print("\n Given n : ", n ," , m : ", m, terminator: "");
		print("\n ", result, terminator: "");
	}
}
func main()
{
	let task: LobbNumber = LobbNumber();
	// Test A
	// n = 6 
	// m = 6
	task.lobbNo(6, 6);
	// Test B
	// n = 4 
	// m = 2
	task.lobbNo(4, 2);
	// Test C
	// n = 3 
	// m = 2
	task.lobbNo(3, 2);
}
main();

Output

 Given n :  6  , m :  6
  1
 Given n :  4  , m :  2
  20
 Given n :  3  , m :  2
  5
/*
    Kotlin program for
    Lobb number
*/
class LobbNumber
{
	fun minValue(a: Int, b: Int): Int
	{
		if (a < b)
		{
			return a;
		}
		return b;
	}
	fun binomialCoefficient(n: Int, k: Int): Int
	{
		var c: Array < Array < Int >> = Array(n + 1)
		{
			Array(k + 1)
			{
				0
			}
		};
		var i: Int = 0;
		while (i <= n)
		{
			var j: Int = 0;
			while (j <= this.minValue(i, k))
			{
				if (j == 0 || j == i)
				{
					c[i][j] = 1;
				}
				else
				{
					c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
				}
				j += 1;
			}
			i += 1;
		}
		return c[n][k];
	}
	fun lobbNo(n: Int, m: Int): Unit
	{
		//  Lm,n counts the number of ways that n + m open parentheses 
		//  and n − m close parentheses can be arranged to form 
		//  the start of a valid sequence of balanced parentheses.
		val result: Int = (((2 * m) + 1) * 
                           this.binomialCoefficient(2 * n, m + n)) / 
          (m + n + 1);
		print("\n Given n : " + n + " , m : " + m);
		print("\n " + result);
	}
}
fun main(args: Array < String > ): Unit
{
	val task: LobbNumber = LobbNumber();
	// Test A
	// n = 6 
	// m = 6
	task.lobbNo(6, 6);
	// Test B
	// n = 4 
	// m = 2
	task.lobbNo(4, 2);
	// Test C
	// n = 3 
	// m = 2
	task.lobbNo(3, 2);
}

Output

 Given n : 6 , m : 6
 1
 Given n : 4 , m : 2
 20
 Given n : 3 , m : 2
 5

Resultant Output Explanation

Now, let's see the output for the given test cases:

  1. Test A: Lobb(6, 6)

    • n = 6, m = 6
    • Lobb number L(6, 6) = 1
    • Explanation: For 6 open and 6 close parentheses, there is only one valid sequence: (((((()))))).

  2. Test B: Lobb(4, 2)

    • n = 4, m = 2
    • Lobb number L(4, 2) = 20
    • Explanation: For 4 open and 2 close parentheses, there are 20 valid sequences possible, which we won't list here but can be calculated using the formula mentioned in the algorithm section.

  3. Test C: Lobb(3, 2)

    • n = 3, m = 2
    • Lobb number L(3, 2) = 5
    • Explanation: We've already shown the 5 valid sequences for Lobb(3, 2) in the Suitable Example section.

Time Complexity of the Code

  1. The binomialCoefficient(n, k) function uses dynamic programming with nested loops over 'i' and 'j'. The time complexity of this function is O(n * k).

  2. The lobbNumber(n, m) function has a constant time complexity of O(1) as it only performs arithmetic calculations and function calls that take constant time.

Overall, the time complexity of the entire code is dominated by the binomialCoefficient(n, k) function, which is O(n * k). However, since the inputs 'n' and 'm' in the problem are relatively small, the code's actual performance will be efficient for practical purposes.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment





Categories
Relative Post