Entringer Number
The Entringer Number E(n, k) are the number of permutations of {1, 2, …, n + 1}, starting with k + 1, which, after initially falling, alternatively fall then rise. The Entringer are given by:
For example, for n = 4 and k = 2, E(4, 2) is 4.
They are:
3 2 4 1 5
3 2 5 1 4
3 1 4 2 5
3 1 5 2 4
Examples :
Input : n = 4, k = 2
Output : 4
Input : n = 4, k = 3
Output : 5
Below is program to find Entringer Number E(n, k). The program is based on above simple recursive formula.
// CPP Program to find Entringer Number E(n, k)
#include <bits/stdc++.h>
using namespace std;
// Return Entringer Number E(n, k)
int zigzag(int n, int k)
{
// Base Case
if (n == 0 && k == 0)
return 1;
// Base Case
if (k == 0)
return 0;
// Recursive step
return zigzag(n, k - 1) +
zigzag(n - 1, n - k);
}
// Driven Program
int main()
{
int n = 4, k = 3;
cout << zigzag(n, k) << endl;
return 0;
}
// JAVA Code For Entringer Number
import java.util.*;
class GFG {
// Return Entringer Number E(n, k)
static int zigzag(int n, int k)
{
// Base Case
if (n == 0 && k == 0)
return 1;
// Base Case
if (k == 0)
return 0;
// Recursive step
return zigzag(n, k - 1) +
zigzag(n - 1, n - k);
}
/* Driver program to test above function */
public static void main(String[] args)
{
int n = 4, k = 3;
System.out.println(zigzag(n, k));
}
}
// This code is contributed by Arnav Kr. Mandal.
# Python Program to find Entringer Number E(n, k)
# Return Entringer Number E(n, k)
def zigzag(n, k):
# Base Case
if (n == 0 and k == 0):
return 1
# Base Case
if (k == 0):
return 0
# Recursive step
return zigzag(n, k - 1) + zigzag(n - 1, n - k);
# Driven Program
n = 4
k = 3
print(zigzag(n, k))
# This code is contributed by
# Smitha Dinesh Semwal
// C# Code For Entringer Number
using System;
class GFG {
// Return Entringer Number E(n, k)
static int zigzag(int n, int k)
{
// Base Case
if (n == 0 && k == 0)
return 1;
// Base Case
if (k == 0)
return 0;
// Recursive step
return zigzag(n, k - 1) +
zigzag(n - 1, n - k);
}
/* Driver program to test above function */
public static void Main()
{
int n = 4, k = 3;
Console.WriteLine(zigzag(n, k));
}
}
// This code is contributed by vt_m.
<script>
// Program to find Entringer Number E(n, k)
// Return Entringer Number E(n, k)
function zigzag( n, k)
{
// Base Case
if (n == 0 && k == 0)
return 1;
// Base Case
if (k == 0)
return 0;
// Recursive step
return zigzag(n, k - 1) +
zigzag(n - 1, n - k);
}
// Driven Program
n = 4;
k = 3;
document.write( zigzag(n, k));
//This code is contributed by sweetyty
</script>
<?php
// PHP Program to find
// Entringer Number E(n, k)
// Return Entringer Number E(n, k)
function zigzag($n, $k)
{
// Base Case
if ($n == 0 and $k == 0)
return 1;
// Base Case
if ($k == 0)
return 0;
// Recursive step
return zigzag($n, $k - 1) +
zigzag($n - 1,$n - $k);
}
// Driven Code
$n = 4; $k = 3;
echo zigzag($n, $k) ;
// This code is contributed by anuj_67.
?>
Output
5
Below is the implementation of finding Entringer Number using Dynamic Programming:
// CPP Program to find Entringer Number E(n, k)
#include <bits/stdc++.h>
using namespace std;
// Return Entringer Number E(n, k)
int zigzag(int n, int k)
{
int dp[n + 1][k + 1];
memset(dp, 0, sizeof(dp));
// Base cases
dp[0][0] = 1;
for (int i = 1; i <= n; i++)
dp[i][0] = 0;
// Finding dp[i][j]
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++)
dp[i][j] = dp[i][j - 1] + dp[i - 1][i - j];
}
return dp[n][k];
}
// Driven Program
int main()
{
int n = 4, k = 3;
cout << zigzag(n, k) << endl;
return 0;
}
// JAVA Code For Entringer Number
import java.util.*;
class GFG {
// Return Entringer Number E(n, k)
static int zigzag(int n, int k)
{
int dp[][] = new int[n + 1][k + 1];
// Base cases
dp[0][0] = 1;
for (int i = 1; i <= n; i++)
dp[i][0] = 0;
// Finding dp[i][j]
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= Math.min(i, k);
j++)
dp[i][j] = dp[i][j - 1] +
dp[i - 1][i - j];
}
return dp[n][k];
}
/* Driver program to test above function */
public static void main(String[] args)
{
int n = 4, k = 3;
System.out.println(zigzag(n, k));
}
}
// This code is contributed by Arnav Kr. Mandal.
# Python3 Program to find Entringer
# Number E(n, k)
# Return Entringer Number E(n, k)
def zigzag(n, k):
dp = [[0 for x in range(k+1)]
for y in range(n+1)]
# Base cases
dp[0][0] = 1
for i in range(1, n+1):
dp[i][0] = 0
# Finding dp[i][j]
for i in range(1, n+1):
for j in range(1, k+1):
dp[i][j] = (dp[i][j - 1]
+ dp[i - 1][i - j])
return dp[n][k]
# Driven Program
n = 4
k = 3
print(zigzag(n, k))
# This code is contributed by
# Prasad Kshirsagar
// C# Code For Entringer Number
using System;
class GFG {
// Return Entringer Number E(n, k)
static int zigzag(int n, int k)
{
int[, ] dp = new int[n + 1, k + 1];
// Base cases
dp[0, 0] = 1;
for (int i = 1; i <= n; i++)
dp[i, 0] = 0;
// Finding dp[i][j]
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= Math.Min(i, k);
j++)
dp[i, j] = dp[i, j - 1] + dp[i - 1, i - j];
}
return dp[n, k];
}
/* Driver program to test above function */
public static void Main()
{
int n = 4, k = 3;
Console.WriteLine(zigzag(n, k));
}
}
// This code is contributed by vt_m.
<script>
// JavaScript program For Entringer Number
// Return Entringer Number E(n, k)
function zigzag(n, k)
{
let dp = new Array(n+1);
// Loop to create 2D array using 1D array
for (var i = 0; i < dp.length; i++) {
dp[i] = new Array(2);
}
// Base cases
dp[0][0] = 1;
for (let i = 1; i <= n; i++)
dp[i][0] = 0;
// Finding dp[i][j]
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= Math.min(i, k);
j++)
dp[i][j] = dp[i][j - 1] +
dp[i - 1][i - j];
}
return dp[n][k];
}
// Driver code
let n = 4, k = 3;
document.write(zigzag(n, k));
</script>
<?php
// PHP Program to find
// Entringer Number E(n, k)
// Return Entringer Number E(n, k)
function zigzag($n, $k)
{
$dp = array(array());
// Base cases
$dp[0][0] = 1;
for ($i = 1; $i <= $n; $i++)
$dp[$i][0] = 0;
// Finding dp[i][j]
for ($i = 1; $i <= $n; $i++)
{
for ($j = 1; $j <= $i; $j++)
$dp[$i][$j] = $dp[$i][$j - 1] +
$dp[$i - 1][$i - $j];
}
return $dp[$n][$k];
}
// Driven Code
$n = 4; $k = 3;
echo zigzag($n, $k);
// This code is contributed by anuj_67.
?>
Output
5
Time Complexity: O(n * n)
Auxiliary Space: O(n * k)
Efficient approach : Space optimization
In previous approach the current value dp[i][j] is only depend upon the current and previous row values of DP. So to optimize the space complexity we use a single 1D array to store the computations.
Implementation steps:
- Create a 1D vector dp of size K+1.
- Set a base case by initializing the values of DP .
- Now iterate over subproblems by the help of nested loop and get the current value from previous computations.
- Now Create a temporary 1d vector curr used to store the current values from previous computations.
- After every iteration assign the value of curr to dp for further iteration.
- At last return and print the final answer stored in dp[k].
Implementation:
// CPP Program to find Entringer Number E(n, k)
#include <bits/stdc++.h>
using namespace std;
// Return Entringer Number E(n, k)
int zigzag(int n, int k)
{
// vector to store values
vector<int> dp(k + 1, 0);
// Base cases
dp[0] = 1;
// iterate to get current value from previous value
for (int i = 1; i <= n; i++) {
vector<int> curr(k + 1, 0);
for (int j = 1; j <= i; j++) {
curr[j] = curr[j - 1] + dp[i - j];
}
// assigning values to iterate further
dp = curr;
}
// return final answer
return dp[k];
}
// Driven Program
int main()
{
int n = 4, k = 3;
cout << zigzag(n, k) << endl;
return 0;
}
import java.util.*;
public class Main {
// Return Entringer Number E(n, k)
public static int zigzag(int n, int k)
{
// array to store values
int[] dp = new int[n + 1];
Arrays.fill(dp, 0);
// Base cases
dp[0] = 1;
// iterate to get current value from previous value
for (int i = 1; i <= n; i++) {
int[] curr = new int[n + 1];
Arrays.fill(curr, 0);
for (int j = 1; j <= i; j++) {
curr[j] = curr[j - 1] + dp[i - j];
}
// assigning values to iterate further
dp = curr;
}
// return final answer
return dp[k];
}
// Driven Program
public static void main(String[] args)
{
int n = 4, k = 3;
System.out.println(zigzag(n, k));
}
}
def zigzag(n, k):
# array to store values
dp = [0] * (n + 1)
# Base cases
dp[0] = 1
# iterate to get current value from previous value
for i in range(1, n + 1):
curr = [0] * (n + 1)
for j in range(1, i + 1):
curr[j] = curr[j - 1] + dp[i - j]
# assigning values to iterate further
dp = curr
# return final answer
return dp[k]
# Driven Program
if __name__ == "__main__":
n = 4
k = 3
print(zigzag(n, k))
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
class Program {
// Return Entringer Number E(n, k)
public static int zigzag(int n, int k)
{
// array to store values
int[] dp = new int[n + 1];
// fill array with 0
Array.Fill(dp, 0);
// Base cases
dp[0] = 1;
// iterate to get current value from previous value
for (int i = 1; i <= n; i++) {
// create a new array to store current values
int[] curr = new int[n + 1];
// fill array with 0
Array.Fill(curr, 0);
for (int j = 1; j <= i; j++) {
// assign values to current array
curr[j] = curr[j - 1] + dp[i - j];
}
// assigning values to iterate further
dp = curr;
}
// return final answer
return dp[k];
}
static void Main(string[] args)
{
int n = 4, k = 3;
Console.WriteLine(zigzag(n, k));
}
}
// Function to calculate Entringer Number E(n, k)
function zigzag(n, k) {
// Array to store values
let dp = new Array(k + 1).fill(0);
// Base cases
dp[0] = 1;
// Iterate to get current value from previous value
for (let i = 1; i <= n; i++) {
let curr = new Array(k + 1).fill(0);
for (let j = 1; j <= i; j++) {
curr[j] = curr[j - 1] + dp[i - j];
}
// Assigning values to iterate further
dp = curr;
}
// Return final answer
return dp[k];
}
// Main function to test the zigzag function
function main() {
let n = 4; // The value of n
let k = 3; // The value of k
let ans = zigzag(n, k); // Calculate the Entringer Number
console.log(ans); // Print the result
}
main();
// This code is contributed by sarojmcy2e
Output
5
Time complexity: O(N*K)
Auxiliary Space: O(K)
Contact Us