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)
-
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].
-
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
-
First, we need to calculate the binomial coefficient using the function
binomialCoefficient(n, k)
. -
Then, we calculate the Lobb number using the formula:
L(n, m) = (((2 * m) + 1) * C(2 * n, m + n)) / (m + n + 1).
-
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:
-
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: (((((()))))).
-
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.
-
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
-
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). -
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.
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