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 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