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)
{
// Test A
// n = 6
// m = 6
// Test B
// n = 4
// m = 2
// Test C
// n = 3
// m = 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()
{
// Test A
// n = 6
// m = 6
// Test B
// n = 4
// m = 2
// Test C
// n = 3
// m = 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)
{
// Test A
// n = 6
// m = 6
// Test B
// n = 4
// m = 2
// Test C
// n = 3
// m = 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()
{
// Test A
// n = 6
// m = 6
// Test B
// n = 4
// m = 2
// Test C
// n = 3
// m = 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()
{
// Test A
// n = 6
// m = 6
// Test B
// n = 4
// m = 2
// Test C
// n = 3
// m = 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() :
#  Test A
#  n = 6
#  m = 6
#  Test B
#  n = 4
#  m = 2
#  Test C
#  n = 3
#  m = 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()
#  Test A
#  n = 6
#  m = 6
#  Test B
#  n = 4
#  m = 2
#  Test C
#  n = 3
#  m = 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
// Test B
// n = 4
// m = 2
// Test C
// n = 3
// m = 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()
{
// Test A
// n = 6
// m = 6
// Test B
// n = 4
// m = 2
// Test C
// n = 3
// m = 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
{
// Test A
// n = 6
// m = 6
// Test B
// n = 4
// m = 2
// Test C
// n = 3
// m = 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.

Categories
Relative Post