Thursday, 22 October 2015

2D Array - DS Hacker Rank Problem Solution Using C++.

Problem Statement
You are given a 6*6 2D array. An hourglass in an array is a portion shaped like this:
a b c
  d
e f g
For example, if we create an hourglass using the number 1 within an array full of zeros, it may look like this:
1 1 1 0 0 0
0 1 0 0 0 0
1 1 1 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
Actually there are many hourglasses in the array above. The three leftmost hourglasses are the following:
1 1 1     1 1 0     1 0 0
  1         0         0
1 1 1     1 1 0     1 0 0
The sum of an hourglass is the sum of all the numbers within it. The sum for the hourglasses above are 7, 4, and 2, respectively.
In this problem you have to print the largest sum among all the hourglasses in the array.
Note: If you have already solved the problem Java 2D array in the data structures chapter in the Java domain, you may skip this challenge.
Input Format
There will be exactly 6 lines, each containing 6 integers seperated by spaces. Each integer will be between -9 and 9 inclusive.
Output Format
Print the answer to this problem on a single line.
Sample Input
1 1 1 0 0 0
0 1 0 0 0 0
1 1 1 0 0 0
0 0 2 4 4 0
0 0 0 2 0 0
0 0 1 2 4 0
Sample Output
19
Explanation
The hourglass which has the largest sum is:
2 4 4
  2
1 2 4


Problem Link : https://www.hackerrank.com/challenges/2d-array

TAG: C++, Data Structure, 2D Array,Hacker Rank.


Solution:


#include<bits/stdc++.h>
using namespace std;
/*
    *
    * Prosen Ghosh
    * American International University - Bangladesh (AIUB)
    *
*/
int main(){

    int ar[10][10],maxSum = -36985247;
    for(int i = 0; i < 6; i++){
        for(int j = 0; j < 6; j++)cin >> ar[i][j];
    }

    for(int i = 0; i < 6; i++){
        for(int j = 0; j < 6; j++){
            if(j+2 < 6 && i+2 < 6 ){
                int sum = ar[i][j] + ar[i][j+1] + ar[i][j+2] + ar[i+1][j+1] + ar[i+2][j] + ar[i+2][j+1] + ar[i+2][j+2];
                if(sum > maxSum)maxSum = sum;
            }
        }
    }
    cout << maxSum << endl;
    return 0;
}

11 comments:

  1. maxSum = -36985247 can i know y u did this bro ? thanks in advance ,

    ReplyDelete
  2. have to print hourglass which has the largest sum.
    Ex:
    -9 -9 -9 -9 -9 -9
    -9 -9 -9 -9 -9 -9
    -9 -9 -9 -9 -9 -9
    -9 -9 -9 -9 -9 -9
    -9 -9 -9 -9 -9 -9
    -9 -9 -9 -9 -9 -9

    What will be the output?
    it should be -63 which is greater than -36985247(a random negative value) so the result will be -63. you can also set any large negative value, which is greater than or equal to -63.

    ReplyDelete
  3. We can write loop condition as i<4 and j<4 and avoid if condition

    ReplyDelete
  4. int main(){
    vector< vector > arr(6,vector(6));
    for(int arr_i = 0;arr_i < 6;arr_i++){
    for(int arr_j = 0;arr_j < 6;arr_j++){
    cin >> arr[arr_i][arr_j];
    }
    }
    int sum=-36985247;
    for(int i=0;i<4;i++){
    for(int j=0;j<4;j++){
    int temp=arr[i][j]+arr[i][j+1]+arr[i][j+2]+arr[i+1][j+1]+arr[i+2][j]+arr[i+2][j+1]+arr[i+2][j+2];
    if(temp>sum){
    sum=temp;
    }
    }
    }
    cout<<sum<<endl;
    return 0;
    }
    Optimized code

    ReplyDelete
  5. my code is not working




    #include
    #include
    #include
    #include
    #include
    #include
    #include
    int greaterglass(int ,int );

    int main(){
    int a[6][6],sum=0,greater=-99;
    for(int i = 0; i < 6;i++)
    {
    for(int j = 0; j < 6; j++)
    {

    scanf("%d",&a[i][j]);
    }
    }

    for( int i = 0; i < 4; i++)
    {
    for(int j = 0; j < 4; j++)
    {

    sum=(a[i][j]+ a[i][j+1] +a[i][j+2]+a[i+1][j+1]+a[i+2][j]+a[i+2][j+1]+a[i+2][j+2]);
    greater=greaterglass(sum,greater);
    }
    }
    printf("%d",greater);

    return 0;
    }
    int greaterglass(int sum,int greater)
    {
    if(sum>greater)
    return sum;
    else
    return greater;
    }

    ReplyDelete
  6. why maxsum is taken as -36985247??

    ReplyDelete
  7. why maxsum is taken as -36985247??

    ReplyDelete
  8. Why the condition is (i+2) < 6 && (j+2) < 6. Please explain.

    ReplyDelete
  9. compare both c++ solution and c solution from above
    in c++ solution he has given condition (i+2)<6 && (j+2)<6 to excute the if condition 4 times in column
    because in 6x6 matrix only 4 hour glasses in row wise and 4 hour glasses in column wise will be there so total hour glasses are 4*4=16. 16 hour glasses will be there

    and in c-solution:- he directly repeated the for loop condition 4 times

    so both of the conditions are similar but the logic's are nice

    ReplyDelete
  10. This comment has been removed by the author.

    ReplyDelete