Question 3: Parallel Columbus

November 20, 2021

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

Sample Output 1

Explanation

The only way possible is (1,1) ->(2,1) -> (2,2), so the answer is 1.

C++

Python

Java

C++

#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;
}

Python

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))

Java

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);   
  }
}