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

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

Large number addition method

Question

  It’s a simple and usual question. If you need to add 2 50-digit numbers, what would you do? The first thing a dummy would look into is definitely the limits of the primitive data type. But note that, a 32-bit machine with a separate floating point processor can at max process 64-bit (for double). So, it comes to max 2^64 which is 20 digits. Then how would you solve for more digits?

Say, the question is you need to add some 100’s of 50-digit numbers and you need to find the first 20 digits.

Brain storm

  I started solving the problem. Straight forward I knew that I need to write code for a simple adder system. Addition is very simple considering the operations required for doing it.

1. Take the LSD part (Least significant digit or the last digit in the number)
2.  Add all the LSD digits of the given numbers (50^th digit)
3.  Ex: if there are 100 numbers with digit max which can be 9, it can add up to max 900.
4. We need to maintain a carry which is the digits other than the last digit that we got in the sum
5. Take carry as well in addition of the next set of digits. (49-0^th digit)
6. Finally output the sum

The method I followed to find the last digit is not much optimized. That is, if you divide a number by 10, you get the carry value. If you mod the number by 10, you get the remainder which is nothing but the last digit.

This same question might get twisted for different bases. Say, you need to do the same for base 2. J Then the rules are different and our algorithm won’t work.

Code

int main()

{

    char line[55];

    short dignum[100][50];

    int count=0;

    ifstream myfile ("eulerinput.txt");

    for(int i=0 ; i<100; i++) {

        myfile.getline(line, 51);

        for(int j=0; j < 50; j++) {

            dignum[i][j] = line[j]-48;

            cout<<dignum[i][j];

        }

      cout<<endl;

    }

    int carry=0; // never >999.. since 100 digits addition + carry can never exceed over 999

    //adder

    int dsum;

    for(int i=49; i>=0; i--) {

      dsum = 0;

      for(int j=0; j < 100; j++) {

                  dsum += dignum[j][i];

      }

      dsum += carry;

      carry = dsum/10;

      cout<<dsum%10<<" "; //digits in reverse

    }

    cout<<endl<<dsum;

    return 0;

}

Finding the count of factors of a number

 

Question

  This is more of a mathematical and a GMAT/CAT question rather than a programming one. But found this question very interesting and found it from Project Euler.

Before seeing the solution, please try out yourselves.

Let me reiterate the question,

“Find a number which has more than 500 factors. The number is part of a triangle series or natural series of additions”

Triangular number is given a name since it can fill every point in a triangle and will add up like this,

1+2+3+4…+n = n(n+1)/2

The above is sometimes called arithmetic series sum as well.

If you need some mathematical background about finding factors, see the below video,

Methods to find factors

Answer

   I really loved the second brute force method given in the above video since its simple and easier to visualize and program.

  I got into lots of problem since I didn’t make up the triangular number in my mind after I got that clear, zoom I got the answer. Number of trails would be at least 20 times. :)

  First tried manually using calculators. But it didn’t work out since I didn’t see that I need to calculate only for triangular number.

Do the second method of factorizing start from 1 and go up by triangular series and count the number of factors.

   The Method is,

1.  find sqrt(number)

2. If the sqrt is a perfect square, then set diff to –1

3. run a loop from 1 to sqrt(number) and count how many numbers are dividing the triangular number selected

4. count*2+diff gives the total factors.

 

Code

#include <math.h>

void main(int argc, char* argv[])

{

    int data=0; //pow(35.00,13.00);

    int next=1;

    int max = 0;

    while(1) {

    int count=0;

    int diff = 0;

    data = data+next;

    int mid = (int) floor(sqrt((double)data));

    if(mid * mid == data) 

        diff = -1;

    for(int j=1;j<=mid;j++) {

        if(data % j == 0) {

            ++count;

        }

    }

    count = count*2+diff;

    if(count > max) {

        max = count;

        cout<<data<<"="<<count<<endl;

        if(max > 499) 

            break;

    }

    next++;

    }

}