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 the number of letters common in given set of strings

 

Introduction

Find the number of letters common in a given set of strings. (Coutesy: HackerRank) Note that the given set of strings might have duplicates.

From the problem statement, i found that since duplicates are there we should remove them and then take the whole set of strings to process the common letters.

Approach

The given input set is as follows: N is the given number of strings, example, case 3

3
aaaabbc
hdjnffb
ccgdaab

Output:

1

The count of common characters across the above 3 strings is only ‘b’

Steps:

• Remove the duplicate in each string to get a unique string
• Process the whole set using a map with key as the character and count as the value
• Finally verify the map for which of the characters the count matches the given N

 

Solution

#include <iostream>
#include <string>
#include <map>
#include <vector>

using namespace std;

void remove_dup(string& gems) {
    map<char, bool> visited;
    int len = gems.length();
    int i = 0;
    while(i < len) {
        if(visited[gems[i]]) {
            gems.erase(i, 1);
            len--;
            continue;
        }
        visited[gems[i]] = true;
        ++i;
    }
}

int commons(vector<string>& stones) {
    map<char, int> element_map;
    int commons = 0;
    for(int i = 0; i < stones.size(); ++i) {
        for(int j = 0; j < stones[i].length(); ++j) {
            element_map[stones[i][j]]++;
        }
    }

    for(map<char, int>::iterator it = element_map.begin(); it != element_map.end(); ++it ) {
       if(it->second == stones.size())
           commons++;
    }
    return commons;
}
int main()
{
    int N;
    vector<string> stones;
    cin>>N;
    for(int i=0; i < N; i++) {
        string gem;
        cin>>gem;
        remove_dup(gem);
        stones.push_back(gem);
    }
    cout<<commons(stones)<<endl;
}

• My usual mistakes are in remove_dup. When you erase something in the string, the index goes out of toss. I never gave a thought about it before writing!
• Note that remove_dup does a O(N) operation using map on each of the input string – Is there some other way to make our life easier here??
• Finding commons requires constructing a map of counts for each character. This operation might get slower
• After we find this count, just verifying it whether it is equal to given string count will do our job since remove_dup taken of having our strings unique independently.

Number of operations to make it palindrome

 

Introduction

   Recently found an interesting Warmup problems @HackerRank. It’s simple and doesn’t use much algorithms. But has palindrome logic which is my favorite. :). And it came with a scramble love letter on it. Ok!! Here i come.

The Problem

Courtesy: https://www.hackerrank.com/challenges/the-love-letter-mystery

James got hold of a love letter that his friend Harry has written for his girlfriend. Being the prankster that James is, he decides to meddle with it. He changes all the words in the letter into palindromes.

While modifying the letters of the word, he follows 2 rules:

(a) He always reduces the value of a letter, e.g. he changes 'd' to 'c', but he does not change 'c' to 'd'.
(b) If he has to repeatedly reduce the value of a letter, he can do it until the letter becomes 'a'. Once a letter has been changed to 'a', it can no longer be changed.

Each reduction in the value of any letter is counted as a single operation. Find the minimum number of operations he carries out to convert a given string into a palindrome.

Input Format
The first line contains an integer T, i.e., the number of test cases.
The next T lines will contain a string each.

Output Format
A single line containing the number of minimum operations corresponding to each test case.

Constraints
1 ≤ T ≤ 10
1 ≤ length of string ≤ 10⁴
All characters are lower cased english alphabets.

The Solution

 

#include <iostream>
#include <cmath>
#include <string>

using namespace std;

int cramble(string str) {
    int size = str.length();
    int count = 0;
    for(int i = 0, j = size-1; i < j; ++i, --j) {
        if(str[i] != str[j]) {
            count += abs(str[i] - str[j]);
        }
    }
    return count;
}

int main()
{
    int T;
    cin>>T;
    for(int i=0; i<T; i++) {
        string love;
        cin>>love;
        cout<<cramble(love)<<endl;
    }    
    return 0;
}

• The solution is simple enough that the code explains it. We compare the first and last letter in string and try to make it equal. Whatever difference we get is taken into count for how many alterations required.
• Note that, we move only until the mid of the string. mid of the string is always equal to itself.
• abs is required since greater letter ASCII code might be in either side, may be on the first or at the last

Thinking in recursive way–Loop Invariant

“Even though, we can solve problems using recursion. It is tough to think something in a recursive way without the knowledge of functional programming”

See also

http://analgorithmaday.blogspot.in/2011/02/loop-invariant-to-prove-correctness.html
http://analgorithmaday.blogspot.com/2011/01/recursionfibonacci-series.html
Introduction
  Thinking in recursive way is little bit tough. But if you have programmed with a functional language then, there is no other way to think. :) When even loops are designed with recursion, you cover all the corner cases isn’t it? That’s the reason why robotics uses functional programming languages as it’s pure magic, fun and well defined mathematical entity rather than the program we write day-to-day.
  But why recursion is taught to be tough when it is so simple to implement and code looks so neat? The real application of recursion can only be seen in functional languages like Erlang.
Concept
  From what we have learnt about loop invariant, what is an invariant? variable is used to vary data, when does invariant used?
  In dummies way, invariant is nothing but a stack!! The data will never vary but get logged somewhere and get popped when needed. So, the data once set never changes but get logged.
In a for loop, we have looping variable which will be set once and the operation done for a single loop is constant!!.. The operation can only be the same for the next iteration without affecting what we are up to. otherwise, what we are doing in the loop is of no use. Simply this is called Loop invariant. When recursion is nothing but loops, understanding loops will give an intro to recursion. But Loops are simpler versions of recursion where usually people never think about constant inside the loop.
Example:

//Example of useless for loop with no loop invariant

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

//Example of storing the values

// loop invariant: at any time a[i-1] will have data upto i-1

int a[20];

for(int i=0;i < 10; i++) { a[i] = i; }

In the above example, for loop incrementing “i” seems like not maintaining anything as invariant. But still we can tell the value of i at any point of time.
If the loop gets to stop in-between then, i’s value is nothing but the time when its stopped. But we don’t have the history.
Next example, array getting set to value of i. History of i is stored. At any point of time, we have data operation for each iteration.
Did you know?
Erlang is a kind of programming language where there is no concept of variables. :) Once we assign a value to the variable using assignment operator, next time it does plain comparison rather than re-assignment. Which means its a invariant variable. It’s not a constant as we see in C++. Don’t confuse with that anyway.
http://learnyousomeerlang.com/starting-out-for-real#invariable-variables

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;

}

Implement push, pop, min in O(1) performance

 

Introduction

   This is a popular interview question found in a site. (ihas1337code). You need to implement push, pop, min all with just O(1) performance. You can use extra space and you can do any push & pops. Every time you should get the minimum in the stack using the min function.

Concept

  Do do this, you need 2 stacks. One which maintains all the minimums found until then and one which contains all the numbers.

For example, the main stack is.

3

2

10

1

7

5

9

The stack with all the min’s found will be

1

5

9

NaN

 

Now, when you pop from the main stack, make sure that you pop the min stack as well only when the element is equal to the popping element.

So, if we have pop-ed 3,2,10, we will still have 1 as min in the min stack. Remove 1 as well in the main stack, you must remove 1 in the min stack as well. Now, definitely 5 is the min.

  With this approach, you can implement pop, push, min all in O(1).

Code

class PerStack

{

    int arr1[100];

    int arr2[100];

    int top1;

    int top2;

public:

    PerStack() : top1(0), top2(0) {

        arr2[0] = INT_MAX;

    }

    void push(int val)

    {

        arr1[top1++] = val;

        if(val < arr2[top2] )

        {

            arr2[++top2] = val;

        }

    }

    int pop()

    {

        if(arr1[top1] == arr2[top2])

            arr2[top2--] = INT_MIN;

        return arr1[--top1];

    }

    int min() {

        return arr2[top2];

    }

};

void main()

{

    int A[] = {9,5,7,1,10,2,3};

    PerStack n;

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

        n.push(A[i]);

    cout<<"minimum : "<<n.min();

}

Construct a binary tree from pre-order and in-order traversals given

 

Question

I came to know about this question from ihas1337code.com. The problem is to construct a normal binary tree from the given pre-order and in-order arrays.

For example,

say, you are given,

preorder = {7,10,4,3,1,2,8,11} inorder = {4,10,3,1,7,11,8,2}

if you need to get a tree like this,

            _______7______
          /                                    \
  __10__                            ___2
/               \                         /
4                  3                  _8
                     \               /
                      1           11

Source: http://www.ihas1337code.com/2011/04/construct-binary-tree-from-inorder-and-preorder-postorder-traversal.html

How would you do that ? Just guess before going into above link

Approach

I came up with the approach. But feed-up with the recursion logic and broke my head with vectors & stacks. This is where the power of recursion is fully used. There are many problems like this which you must be used to get ready for interviews.The approach for this problem is like this,

• We know that the first node of the pre-order is definitely the root of the tree
• Subsequent nodes listed in the pre-order arrays are all roots of sub trees, coming with format left-right-root
• Also we know that, in-order traversal has left first, root and then right
• So, simply take a element in the pre-order array and search in the in-order array to get the indices. After you get the index, the left is the left sub tree, right is the right sub tree

For example, Consider the above input set.

The first iteration will be like,

_______7______
/ \

4 10 3 1                         11 8 2

So, detect 7 as the root.. search in the in-order array and find the index.. what you got is that, {4 10 3 1} are the nodes of the left sub tree and {11, 8, 2} are nodes of the right sub tree.

After you detect this, you need recursively do the same to in left and right lists to get the full tree constructed.

That is, the next root after seven is nothing but 10.. search for 10 in the left first.. having 10 as the root, 4 becomes the left and {3,1} becomes the right tree.

But how to do this approach ?

Approach – for implementation

The implementation of this approach is little bit tricky. Firstly, we should be very clear about what all we need replication for each tree creation. The following data is needed in each iteration,

• The root node!! its different for each sub-tree that we create
• the pre-order array movement and the in-order array movements.. we need to split the in-order arrays with root node found from pre-order array as the middle element.
• root->left and root->right should get the nodes which are processed in the future!! :(

After doing this exercise, i understood that, i need to restudy recursion again in a more clearer way :)

Recursive call of a function does the following things

• the arguments are put into a stack.. You can clearly see the arguments part of the call stack frame
• the local variables in the function are all replicated and if you return local variable value in the recursion.. it gets shared with the previous recursive function call in the stack.. :)

The local variables & return value based recursion is also known as tail recursion. We will see about this in detail separately.

We have to use tail recursion to successfully implement this code.

Code

struct BinaryTree 

{

    int data;

    BinaryTree* left;

    BinaryTree* right;

};

BinaryTree* newTreeNode(int data)

{

    BinaryTree* newNode = new BinaryTree;

    newNode->data = data;

    newNode->left = NULL;

    newNode->right = NULL;

    return newNode;

}

int getIndex(int* arr, int val, int size)

{

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

        if(arr[i] == val) 

            return i;

    }

    return -1;

}

BinaryTree* create_bintree(int* parray, int* iarray, int size)

{

    if(size == 0) return NULL;

    int rootVal = parray[0];

    BinaryTree* root  = newTreeNode(rootVal);

    int newIdx = getIndex(iarray, rootVal, size);

    root->left = create_bintree(parray+1, iarray, newIdx);

    root->right = create_bintree(parray+newIdx+1, iarray+newIdx+1, size-newIdx-1);

    return root;            

}

void main()

{

    int preorder[] = {7,10,4,3,1,2,8,11};

    int inorder[] = {4,10,3,1,7,11,8,2};

    BinaryTree* tree = create_bintree(preorder, inorder, 8);

}

• We have taken some code logic from ihas1337code. But we don’t use mapIndex and offsets, as it complicates things and also adds a restriction to the element set
• Note that, elements should be unique!!.. Otherwise, this approach will never workout.. :)
• NEVER EVER TRY WITH vectors, stacks without recursion. It will screw up heavily!!
• every node gets a new tree Node with newTreeNode function inside create_bintree
• we do the tail recursion, parray+1 to get the root->left. and we will end this recursion only after we have also seen the right nodes in the tree. :)
• That is, when we reach 0 in root->left.. we check for root->right as well!!.. End condition is newIdx is 0 (i.e, size = 0)
• parray+1 and parray+newIdx+1 is simple logic
  • You get the newIdx from inorder array.. which is the middle element and the root.
  • 0 to newIdx-1 will be left and newIdx+1 to end will be the right
• iarray and iarray+newIdx+1 works uniformly with parray so that.. root->left gets only left side nodes and root->right gets only the right side nodes.
• size-newIdx-1 in this, –1 is just because the array index starts at 0. size-newIdx is the actual size of right half. that is, end – newIdx+1 is the size of the right side in all cases
• There are lots of invariant in this code!!.. and its not verified with all kinds of Input. Handle with care!! :)