Apply For Jobs
Get Hiring UpdatesQuestion 3: Parallel Columbus
Parallel Columbus
In this article we will see InfyTQ Sample Coding question. You will find solution of InfyTQ Coding question in different programming language on this page.
Problem Statement
Nobel Prize-winning Austrian-Irish physicist Erwin Schrödinger developed a machine and brought as many Christopher Columbus from as many parallel universes he could. Actually he was quite amused by the fact that Columbus tried to find India and got America. He planned to dig it further.
Though totally for research purposes, he made a grid of size n X m, and planted some people of America in a position (x,y) [in 1 based indexing of the grid], and then planted you with some of your friends in the (n,m) position of the grid. Now he gathered all the Columbus in 1,1 positions and started a race.
Given the values for n, m, x, y, you have to tell how many different Columbus(s) together will explore you as India for the first time.
Remember, the Columbus who will reach to the people of America, will be thinking that as India and hence wont come further.
Function Description:
Complete the mark game function in the editor below. It has the following parameter(s):
Parameters:
| Name | Type | Description |
| n | Integer | The number of rows in the grid. |
| m | Integer | The number of columns in the grid. |
| x | Integer | The American cell’s Row. |
| y | Integer | The American cell’s Column. |
Constraints:
- 1 <= n <= 10^2
- 1 <= m <= 10^2
- 1 <= x <= n
- 1 <= y <= m
Input Format:
- The first line contains an integer, n, denoting the number of rows in the grid.
- The next line contains an integer m, denoting the number of columns in the grid.
- The next line contains an integer, x, denoting the American cell’s row.
- The next line contains an integer, y, denoting the American cell’s column.
Sample Cases
Sample Input 1
2
2
2
1
Sample Output 1
1
Explanation
The only way possible is (1,1) ->(2,1) -> (2,2), so the answer is 1.
#include <bits/stdc++.h>
using namespace std;
unordered_map<int,long long int> f;
long long int Fact(int n)
{
if(f[n]) return f[n];
return f[n]=n*Fact(n-1);
}
int main()
{
int n,m,x,y;
cin>>n>>m>>x>>y;
n-=1;m-=1;x-=1;y-=1;
f[0]=f[1]=1;
int p=(Fact(m+n)/(Fact(m)*Fact(n)));
int imp=((Fact(x+y)/(Fact(x)*Fact(y)))*(Fact(m-x+n-y)/(Fact(m-x)*Fact(n-y))));
cout<<p-imp;
}
import math
n=int(input())-1
m=int(input())-1
x=int(input())-1
y=int(input())-1
ans=math.factorial(n+m)
ans=ans//(math.factorial(n))
ans=ans//(math.factorial(m))
ans1=math.factorial(x+y)
ans1=ans1//(math.factorial(x))
ans1=ans1//(math.factorial(y))
x1=n-x
y1=m-y
ans2=math.factorial(x1+y1)
ans2=ans2//(math.factorial(x1))
ans2=ans2//(math.factorial(y1))
print(ans-(ans1*ans2))
import java.util.*;
class Main
{
static int f[] = new int[1000];
static int Fact(int n)
{
if(f[n]==1) return f[n];
return f[n]=n*Fact(n-1);
}
public static void main (String[]args)
{
Scanner sc = new Scanner (System.in);
int n = sc.nextInt ();
int m = sc.nextInt ();
int x = sc.nextInt ();
int y = sc.nextInt ();
n-=1;m-=1;x-=1;y-=1;
f[0]=f[1]=1;
int p=(Fact(m+n)/(Fact(m)*Fact(n)));
int imp=((Fact(x+y)/(Fact(x)*Fact(y)))*(Fact(m-x+n-y)/(Fact(m-x)*Fact(n-y))));
System.out.println(p-imp);
}
}
Login/Signup to comment