Diagonal read the matrix array - C++

 

Introduction

After a long time, here comes a post on parsing a NxN matrix. Our main intension here is to take the sum of the diagonals and take a absolute difference between them. At first, I simply forgot the C++ way to initialize an NxN array. Whoof!!

Let’s first understand what a double pointer is. It’s just a pointer to an array of pointers!!

That is,

What we do with a integer pointer *A? . Allocate an array of integers

Then what to do when u need a list of integer pointers **A ?  Allocate an array of integer pointers

How its done?

Now below is the code to allocate the double pointer

int N=10;

int **A = new int*[N]; // get array of N integer pointers

for(int i = 0; i < N; i++)

    A[i] = new int[N]  // now allocate to each pointer an array of N

// finally A[i][j] gets you into NxN!!

Next confusion comes with reading this array diagonally. Until we understand how coordinates of an diagonal behave, it’s tough to understand that clearly.

 

 If you see the left diagram, you can guess the paper work done for it.

 

From left->right, you can notice that always you get two indices, (i == j) equal. So you got this diagonal for all NxN.

 

From right –> left, what is the pattern ? It has to be the combination of i and j. If you see closely, i increases and j decreases as we move. i always increases in our loop, we just need to take care of making j to decrease.. or equating like this as well  i+j = N+1 works!!

 

 

#include <cmath>

#include <cstdio>

#include <vector>

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

    int N=1;

    cin>>N;

    int **A = new int*[N];

    for(int i = 0; i < N; ++i)

    {

        A[i] = new int[N];

        for(int j = 0; j < N; ++j)

        {

            cin>>A[i][j];

        }

    }

    int sumDiag1 = 0;

    int sumDiag2 = 0;

    for(int i = 0; i < N; ++i)

    {

        for(int j = 0; j < N; ++j)

        {

            if(i == j)

            {

               sumDiag1 += A[i][j];    

            }

            if(j + i == N-1)

            {

               sumDiag2 += A[i][j]; 

            }

        }

    }

    cout<<abs(sumDiag1 - sumDiag2);

    return 0;

}

DISCLAIMER: There are better ways to do this on internet without O(N^2) loop. You can do this in a single loop as well.

Maximum number of pieces with cuts

 

Introduction

   The problem is taken from HackerRank. The task is to cut a huge chocolate bar into 1x1 pieces with as much as possible cuts. The number of cuts are given using which we need to identify the number of pieces.

Solution

  The problem is so simple if we understand the logic behind it. The given value is number of cuts. In this value, some are horizontal lines and some are vertical lines. Don’t get confused by it. Just check for the base case, when there are two lines.

when number of cuts is 2, there will be only one chocolate piece. when the number of cuts are 3, there will be 3 = 1 + 2 = 1*2 = 2 cuts.. how ? all numbers are divisible by 2 and you get a nearest possible value divisible by 2. Next step is just subtracting that value with the main value. i.e, 3/2 = 1 (q).. 3-q = 2. Multiply both these values, you get the number of pieces.

#include <vector>

#include <iostream>

using namespace std;

int main(void)

{

    int T;

    vector<long> out;

    cin>>T;

    for(int i = 0; i < T; ++i)

    {

        long q, r, val;

        cin>>val;

        q = val / 2;

        r = val - q;

        out.push_back(q*r);

    }

    for(int i = 0; i < (int) out.size(); ++i)

        cout<<out[i]<<endl;

}

what is the math logic here? when you divide any number by 2, you get a exact median of all the cuts. The median might be even or odd. The remaining value can be taken either as horizontal or vertical to maximize number of cuts (it doesn’t matter larger value need to be horizontal or vertical).  You can event print out how many vertical & horizontal now safely. :)

This means if somebody asks you to cut a cake for 30 people, then try for a multiple of 30 which can give as exactly equal pieces(3x10 or 15x2 wont give as that, we need both the factors as much near as possible). So its (6+5) 11 cuts. (i.e) you put a 5 horizontal and then a 6 vertical cuts (or vice versa) to get 30 pieces total. A math in reverse just confused the dummy mind at first look!! :D This problem made me lose faith on basic division, subtraction and multiplication.

See also

Find out the prime factors of the number: http://en.wikipedia.org/wiki/Prime_factor. It has applications on cryptography and this problem shows as some basics to it. :)

Find power of 2

 

Introduction

  This something simple to understand recursion. Just for a time pass code recipe. :)

Concept

Recursion base condition: 

2⁰ = 1

Generic formula,

pow2(n) = { 1 , when n=0

                  2*pow2(n-1), when n>1

The above formula works out well to find the powers of 2.

Code

double pow2(double val)

{

  if(val == 0)

    return 1;

  return 2*pow2(val-1);

}

void main()

{

    cout<<pow2(1000);

}

Warning

• This is not an alternate to pow function. The runtime implements it using for loop.

Thinking in recursive way–Mathematics

“I simply forget recursion and always use debuggers to understand it. Debuggers are hated by mathematical programmers. Why you need debuggers btw when you use math to prove your program will work for all corner cases ?”

Introduction

   The funny thing about mathematics and programming is that, if you pick one, you will drop another. A perfect example of chicken and egg problem. But programs written for critical applications always goes for mathematical analysis.

  To understand Recursion, you need to know some mathematical functions which already aptly follow recursion.

Lets see the factorial function which is defined with below,

Lets see an example, where n=4

4! = 4 x 3!
4! = 4 x 3 x 2!
4! = 4 x 3 x 2 x 1!
4! = 4 x 3 x 2 x 1 x 1

Concept

   Ok. Factorial is basic. We all knew about all the mathematical functions and their direct mapping with recursion.

  Now, where to use recursion? just for mathematical functions? This is the question of programmers, not the mathematicians. :)

  I hope you read the previous post on Loop invariant. That is the basis for deciding whether to go for recursion or not. :)

  Let’s say, you need to maintain multiple values constant, logged for future processing in a loop. You usually would go for using stacks or some data structure to keep a log of all data required in future. 

Example:

   count the number of nodes in a tree

   How to think about this problem loud out? usually people mug up things. :) But that’s not the right way.

A simple logic, start with 0 nodes in a tree, means tree variable is NULL.

This is base condition. Then, what we need to do, we need count of left tree and right tree.

The code goes like below, so simple,

if(tree == NULL)

  return 0;

return count(tree->left) + 1 + count(tree->right);

Mathematical representation:

count(t) =   0, when t=0

                  1, when t=1

                 count(t->left) + count(t->right), when t > 1

Let’s try for 3,

count(3 node tree) = count(1) + count(left + right node)

              = 1 + count(1 left node) + count(1 right node) = 3

Analysis

  Here, the loop invariant is at any time, we have the node’s visited on hand. that is, if we have visited all tree->left, we start visiting tree->right. Once we are done with all tree->right, we reach base condition for every node. If the node count is 1, then its 1. :)

 This is what works out simply for anything that uses recursion, quick sort, merge sort.. any algorithm we see, the base condition value is the important one. After you design the base condition in the form of mathematical function, writing recursive program is simpler.

Understanding Logarithms

            “During the periods of John Napier (http://en.wikipedia.org/wiki/John_Napier), he was called a magician for inventing easier ways to multiply. But now, the calculators and computers are the actual magicians for humans!!”

Introduction

            As the above quote says, the history behind logarithms is interesting and first we need to understand the problem which made mathematicians to think about using shorter ways. Mathematicians are seriously lazy people like us. :)

  Napier had been working on his invention of logarithms for twenty years before he published his results, and trigonometry tables (sin, cos table) was the origin of his ideas at about 1594.He wanted to simplify geometric progression by tabulating it and simplifying multiplications using additions. With the additive property of powers as the concept behind his approach (2^1 * 2^2 = 2^3), he started working out an approach to find a series for easy multiplication of 0.999. It was extended then to 10 in future.

10^1/2 = sqrt(10) = 3.162277 which means log(3.162277) = ½. Similarly, We can  continue for rational powers easily, as 10^3/4 = 10^1/2*10^1/4 = sqrt(10) * sqrt(sqrt(10)) = sqrt(31.62277) = 5.623413. which means log(5.623413) = ¾. I need to learn how sqrt values moves decimal points. J But this is how logs were calculated.

            This means that recording powers of a base present inside a huge number is what logarithms do.

More info

So simply, logarithms is the record of power of a given value,

log ₂8 = 3 which means 2^3 = 8. Logarithmic tables recorded the powers of huge decimals with high precision and preparing such tables is tedious job!!

Below is the logarithmic properties and b is the base.

1. log_b(xy) = log_bx + log_by.
2. log_b(x/y) = log_bx - log_by.
3. log_b(xⁿ) = n log_bx.          
4. log_bx = log_ax / log_ab.     

Example:

Log₂ 8 = log₂4 + log₂2

Log₂ 2³ = 3*log₂2

Some diagrams from MathFun:

 

Problem 15: Pascal's Triangle - Project Euler

After a long-long time wanted to restart this blog and planning keep it updated with more problems/math and algorithms.

Problem

            Find the number of routes from the top-left corner to the bottom right corner without backtracking in a 20x20 array. The example give is a 2x2 square. In this square, you can have around 6 routes from start point to end point.

How would you start thinking about this problem? Start counting? You can never reach the conclusion.

Analysis

            As we have a useful condition that we cannot backtrack, once we move forward in any direction we can never come back. So, if we move in that angle, we get more routes passing through points in forward direction. The first thing came to my mind is the points!!

  If you count the points and tell that is the total route, then you are wrong as a single point might lead to multiple routes both vertical/horizontal. We started doing manual steps for 3x3. But at second thought, what got into my mind is a graph!! If u have a unidirectional graph all starting from one point and ending at the bottom right corner, can we then calculate for 4x4, 5x5 etc. First I tried for a 3x3 the approach we got in mind,

For each point, how many route that is possible? I remembered my entire graph logic learned to come up with this but was not sure whether this is right on 3x3 having total 20 routes. Moreover, writing in algorithm to implement this for 20x20 is impossible!!

  When I wanted to find the actual easiest way to solve this, then came the forgotten mathematics concept: combinations.

Solution

            As we know the routes are from top-left corner to bottom-right corner, we can only move two ways, right or down. For a 2x2, the various combinations possible are 6, RDDR, RRDD, RDRD, DRDR, DDRR, DRRD. All this means that, we need to find how many possible ways 2 rights can be placed in total 4 sided route.

            This can be done using combination with 4 C 2 = 4! / 2! (2!) = 6. So for NxN, we always have this generic formula, 2N C N = 2N! / N! (2N-N)!.

Simply said, with the above formula, you can easily get all the combinations. Then the analysis we did? What is that? Can the problem be solved in that way? Yes. The approach we got is nothing but Pascal’s triangle using acyclic graph method. It would have taken years to complete it. J

Refer: http://blog.functionalfun.net/2008/07/project-euler-problem-15-city-grids-and.html

Division method–5th Grade way

"As you become old, you will definitely forget your primary school rhymes!!.. similar to that, you would also forgot multiplication and division as well!!.. This is the dummy’s way to understand, Division with reminder.. Take 1 in the hand, 5 in the middle.. :)”

Introduction

  Suddenly, i found that i forgot the 5th Grade Long division method. I don’t know about you. But thought of covering it, as its not so simple.. :)

  It’s not a pure dummies or a 5th grade guide. We need to understand Long division method clearly to go in-depth for doing Division of Large numbers or Getting reminder between two large numbers.

  As you might guessed, division of large numbers (as heavy as 2048-bit size) are used now in RSA which is also proven to be cracked within years!!.. :)

  As this method is required basics for RSA encryption algorithm, this article will be useful for a computer geek as well as a 5th grader!!..

Concept

  The way we do long division is simple. But underlying logic behind division is very important one to understand. Multiplication if you take,

  how we come up with 4*3 = 12 ? 4 + 4 + 4 or 4 added 3-times gives you 12. So for a successful multiplication, just successive additions are more than enough. Even in current systems, they just use the adder circuit at ALU to do this.

Then what does 12/3 does ? There are 2-types are division a system categorized into,

• integer division
• floating point division

12/3 will yield you just an integer. So, based on programming language and system, it selects to use integer division where floating point is completely ignored.

Try, int z = 12/5

You will just get z=2. At the same case, if you convert these to float, you get the mantissa & exponential part which might require more than 32-bit. (float is just 32-bit, double is 64-bit).

Try this now,     float z=12.0/5.0;

The above is an example of floating point division.

At the core, division happens using subtraction. 12/3 means.. how many times subtracting three yields zero.

“Ok, i understood int, float. What is quotient and reminder ?”

(Take example: 12/3) - quotient(4) is the number you get after you divide with divisor (3) the dividend(12). Sometimes, just subtracting denominator with numerator will not yield zero. Subtract as much as you can so that, the value is less than your quotient. This value will become your reminder.If you want to continue subtracting, then it must be after a decimal point.

In the above division, 10 is the reminder and 17 is the value you get in integer division. now to find the exponential part, you can further divide from there, 10/25.. :) you get 0.4. So the resultant of this division is 17.4.

More explanation

  Division is just a concept of finding out how many values are inside a value

Just take the below long division example,

This is the normal way, we have learnt the division. But actually what happens here is different and this needs to be understood to write code to do large number division.

The above is the right way our teachers should have explained. We don’t just take the first 2 digits, we always assume that we have 0’s to complement as. 23*3 = 69 if we do and just subtract the first 2 digit simply means that there are 0’s in the other places. we have to finally add, all these 300 + 60 + 8 to get the actual quotient. Remember that, 11 is the reminder we have got. If we further divide, 11/23.. you get decimal pointed values.

Thus, it doesn’t mean that you need to always have 23*3 for your operation. you can even do like the above way, if you want to step in a easy multiplicative way.

References

http://en.wikipedia.org/wiki/Binary_multiplier

http://www.conceptualstudy.org/Elementary%20Math/Understanding%20Division.htm

Some exercises

“Now, how would you find the reminder between 56.74 / 45.67647”

In C++, you have fmod. Normally, you can do the following,

• first do integer division of the above numbers - 56/45
• now to get the reminder do this, 56.74 – 45.67647 * quotient (which is 1 in our case)
• this gives out our reminder as, 11.06

 

 

 

   

Collatz conjecture

 

Problem

  This is project euler problem 14. Really interesting and mathematically challenging one.

The following iterative sequence is defined for the set of positive integers:

n n/2 (n is even)
n 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 40 20 10 5 16 8 4 2 1

Source: Project Euler.

The below figure will explain the problem precisely.

References

http://en.wikipedia.org/wiki/Collatz_conjecture

http://projecteuler.net/problem=14

Solution

I tried the tail recursive way first..!! But its too slow and it took hours to run.. In debug mode, stack is used even for tail recursion.. so, it went useless to do 1 million function calls every time. so, moved into a iterative way.

Just a brute force algorithm for 1 million values took around 10-15 minutes to run. But, the 1-minute rule given by project euler is not followed in this program.. :)

There are better ways to do.. But since there seems no valid applications for this series, am just leaving it here..

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

    int gMax = 0;

    double gI = 0;

    for(double i=1; i<1000000; i++) {

        double val = i;

        int count = 0;

        cout<<val<<" ";

        while(val != 1) {

            ++count;

            if (fmod(val, 2.0) == 0) {

                val = val/2;

            }

            else

            { // odd

                val = 3*val + 1;

            }

        }

        count++;

        if(count > gMax) {

            gI = i;

            gMax = count;

        }

        cout<<endl;

    }

    return 0;

}

• gMax is the maximum count of the numbers in the series
• gI is the number which yields this max count