10/25/20

HackerEarth ‘Cells in a matrix’ Solution

Short Problem Definition:

You are given an integer N denoting an N×N matrix. Initially, each cell of the matrix is empty. You are given K tasks. In each task, you are given a cell (i,j) where cell (i,j) represents the ith row and jth column of the given matrix.

You have to perform each task sequentially in the given order. Each task is described in cell (i,j). For each task, you have to place X in each cell of row i and each cell column j. After you complete each task, you are required to print the number of empty cells in the matrix.  

Link

Cells In A Matrix

Complexity:

time complexity is O(K*log(N))

space complexity is O(N)

Execution:

There are many solutions to this problem statement. I picked this one, since its easy to understand and is correct.

Solution:
def cells_sol (N, K, tasks):
    rows = set([i+1 for i in xrange(N)])
    columns = set([i+1 for i in xrange(N)])
    result = []

    for task in tasks:
        rows.discard(task[0])
        columns.discard(task[1])
        result.append(len(rows)*len(columns))

    return result
    

N, K = map(int, raw_input().split())
task = []
for _ in range(K):
    i, j = map(int, raw_input().split())
    X = i, j
    task.append(X)


out_ = cells_sol(N, K, task)
print (' '.join(map(str, out_)))


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwitterredditpinterestlinkedin
10/25/20

HackerRank ‘Possible Path’ Solution

Short Problem Definition:

Adam is standing at point (a,b) in an infinite 2D grid. He wants to know if he can reach point (x,y) or not. The only operation he can do is to move to point (a+b, b) (a, b+a) (a-b, b), or (a, b-a) from some point (a,b). It is given that he can move to any point on this 2D grid, i.e., the points having positive or negative (or ) co-ordinates.

Tell Adam whether he can reach  or not.

Link

Possible Path

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

The problem statement is not requesting the path from A,B to X,Y, just that a path exists. This makes it a mathematical problem.

We know that GCD(a, b) == GCD(a+b, b) == GCD(a-b, b). Why? Because if something is a divisor D of B, adding/subtracting B from any number A that is also divisible by D will not change the divisibility requirement.

Hence GCD(a, b) == GCD(a+n*b, b+m*a) where n, m are integers.

Following the rules, we can realize that GCD(a+n*b, b+m*a) is GCD(x, y), which leads us to the final solution.

Solution:
def gcd(a, b):
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)

def solve(a, b, x, y):
    return gcd(a,b) == gcd(x,y)


If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.

Facebooktwitterredditpinterestlinkedin