Skip to main content

Contact

Name

Email

Message

Comments

Popular posts from this blog

CodeChef March Challenge 2021 — Consecutive Addition

“You are given two matrices A and B, each with R rows (numbered 1 through R) and C columns (numbered 1 through C). Let’s denote an element of A or B in row i and column j by A(i,j) or B(i,j) respectively….. ” You can read the whole problem here . Problem description in short Given two matrices, A and B. Task is to transform A to B using special some addition-based criteria. The criteria for transformation is as follows we are given a number K 2 ≤ K ≤ min(R, C), where R is row size and C is column size we have to take any submatrix of size Kx1 (i.e. along the column) or 1xK (i.e. along the row), in A, and to all the numbers that fall under that submatrix have, add some integer v, this can be chosen by us. This has to be done in such a way that finally A transforms to B. The actual problem is to check if this kind of transformation is possible, given A and B. Ideation…. Befor e  I begin I wanna say that it is an observation based problem, can have many solutions and my solution is no...

Solving a Tree Problem

Balanced Binary Tree T ree problems are quite popular among competitive programming questions.  A ll the fame  is because of the co mplexity of thought they deliver to the mind of a beginner and sometimes they even scare the intermediate programmers, who have been programming for a while. Here in this blog, I will discuss a general problem that has similar complexity issues and share a thought to break the solution. Some Prerequisites Sites all over the internet are filled with basic level tree problems like Finding the depth of a node in a tree Finding the height of a tree Sum of a subtree rooted at some internal node of the tree Finding LCA (Lowest Common Ancestor)of two nodes of a tree (in O(N)) Finding LCA of any two nodes of a tree (in O(logN)) Generally speaking, all such problems are the building block for the tree-problems of intermediate level, like one discussed below. A Generic Problem The problem starts with a description of a tree and clearing out what all kind of...

Fibonacci Sequence: Running Sum

  This article is in continuation of  this one . R ecap In the  previous article , I had tried to emphasize how nᵗʰ Fibonacci Number = Number of ways to climb n step staircase, where you have only two possible options to move, either by climbing 1 step or 2 steps at a time. In the same article, I have mentioned some other  p ossible representations of the Fibonacci Sequence. One of them is the number of ways to tile a N x 1 board with a 1 x 1 square and 2 x 1 domino. By writing the recurrence relation for the same, we can state that NoOfWaysToTile(n) = nᵗʰ Fibonacci Number. Recurrence for the Tiling problem Tiling Problem Relation and Fibonacci Number Reversing the above Equation In this article, I am going to discuss my approach to the Running Sum Identity of the Fibonacci Sequence using the same relation. The Running Sum of Fibonacci Sequence The Left Hand Side (L.H.S.) The L.H.S. of the equation has 2 parts  Fib(n)  and  (- 1) . Fib(n) = nᵗʰ Fibonac...