none
Questions & Solutions to Quiz-III RRS feed

  • Question

  • NameList
    There are two sections for grade 4 students and when moving to grade 5, the school management decided to merge them all into single section. You are required to write a program to merge students from both the sections in such a way that they are sorted in ascending order. Assume that no student names are repeated.

    This program uses a unique method getSortedNames. The method getSortedNames is unique because the data type it uses as input parameter is "vector names1, vector names2". The output of this method is again a vector which contains names in both names 1 set as well as names2 set arranged in ascending order.

    IMP: Remember to include header file #include <vector> for vector.

    Example 1:
    Input:
             names1[] = {"Aakash","Rohit","Babu"};
             names2[] = {"Uma","Vikram","Surya"}

    Output: Returns {"Aakash", "Babu", "Rohit", "Surya", "Uma", "Vikram"}

    Explanation: The method getSortedNames merges both the vectors in to a single vector as well arranges them in ascending order.

    Example 2:
    Input:
             names1[] = {"Clark","Harris","Smith","Davis","King","Adams","Campbell","Mitchell","Jackson"};
             names2[] = {"Barbara","Donald","Betty","Taylor","Anderson"}

    Output: Returns {"Adams", "Anderson", "Barbara", "Betty", "Campbell", "Clark", "Davis", "Donald", "Harris", "Jackson" , "King", "Mitchell", "Smith", "Taylor"}

    For C solutions
    Header File    :    NameList.h
    Function Name    :    vector<string> getSortedNames(vector<string> names1, vector<string> names2)
    Directory Name    :    namelist
    File Name    :    NameList.c
    For C++ solutions
    Header File    :    NameList.h
    Class Name    :    list
    Function Name    :    vector<string> getSortedNames()
    Directory Name    :    namelist
    FileName    :    NameList.cpp
    Saturday, April 21, 2007 3:28 PM

Answers

  • Write a program to pick out squarefree numbers from a given set of numbers. The criteria for a squarefree number is that it should not be a square value of its divisors and also its divisor should not be a sqaure value of its divisors. For example, 10 is square-free but 18 is not, as it is divisible by 9 = 32 .

    There are two methods used in this program and they are getNoOfSquareFreeNumbers and getSquareFreeNumbers. The method getNoOfSquareFreeNumbers uses a range of integer values and returns a single integer value which is the count of square free numbers present. The second method getSquareFreeNumbers returns all the numbers that satisfy the criteria for sqare free number.


    Example 1:
    Input
             from = 1
             to = 10
    Output
             Function getNoOfSquareFreeNumbers return : 7
             Function getSquareFreeNumbers returns : {1,2,3,5,6,7,10}

    Explanation:In this example the input range of numbers is from 1 to 10. The numbers that are missing in the output are {4,8 and 9}. If we consider the integer 4 we can see that the divisor 2 when squared will result in 4. So it is not a sqarefree number. The same goes for 8 and 9.

    Example 2:
    Input
             from = 4383
             to = 4400
    Output
             Function getNoOfSquareFreeNumbers return : 11
             Function getSquareFreeNumbers returns : {4385, 4386, 4387, 4389, 4390, 4391, 4393, 4395, 4397, 4398, 4399}

    For C solutions
    Header File    :    SquareFreeNumbers.h
    Function Name    :    int getNoOfSquareFreeNumbers(int from, int to), int* getSquareFreeNumbers(int from, int to)
    Directory Name    :    squarefreenumbers
    File Name    :    SquareFreeNumbers.c
    For C++ solutions
    Header File    :    SquareFreeNumbers.h
    Class Name    :    SquareFree
    Function Name    :    int getNoOfSquareFreeNumbers(int from, int to), int* getSquareFreeNumbers(int from, int to)
    Directory Name    :    squarefreenumbers
    FileName    :    SquareFreeNumbers.cpp

    Saturday, April 21, 2007 3:28 PM
  • Guys, can we discuss / post the solutions now or after the quiz is over ?
    Saturday, April 21, 2007 3:29 PM
  • nice dear
    Saturday, April 21, 2007 3:34 PM
  • this should be posted after the quiz is done i believe.. i believe that the questions will not repeated.. lets see i'm taking the quiz 2morrow..
    Saturday, April 21, 2007 5:37 PM
  • Try some more with the same
    Sunday, April 22, 2007 4:02 AM
  • Yes guys, i think i will wait till tomorrow and then we can start posting the solutions ): But as the questions may not be repeated, i guess we can atleast paste the questions here Smile so that others who are interested can try to solve it.
    Sunday, April 22, 2007 5:22 AM
  • We should not post answers right now...

    but we can share our quiz-3 experience.

     

    I think, this format with 2 questions is better than old one.

    and questions are also nice.

    Right?

    Sunday, April 22, 2007 10:50 AM
  • I agree with you hiren, but the level of the questions are getting harder , there are 2 questions, one was easy another was hard  Atleast we can solve the easy one if incase we dont solve the harder one. We can still get points for the one that we solved .
    Sunday, April 22, 2007 11:01 AM
  • And one more thing, i have observed that some of the questions also have the use of vectors and lists  which i really great  Not many of them know about vectors, list, queues, stack, etc etc .
    So i think they have set the questions such so that people who dont know these aspects, can learn it, which is really useful when you go into the corporate world.
    Sunday, April 22, 2007 11:06 AM
  • Yes...

    I faced same problem.

    One of my two questions was using List Concept...

    Sunday, April 22, 2007 1:47 PM
  • hey man, lists are very easy,. If you have time for the question, then please refer to
    http://www.cppreference.com/cpplist/index.html
    http://www.cppreference.com/cppvector/index.html

    They are really nice, and easy to program, it will ease your programming a lot. Hope you like it.
    Sunday, April 22, 2007 2:39 PM
  • Hey dear...

    I have already completed my quiz on first day (yesterday).

    I did the solution of that problem successfully.

    but I think, that can be hard for some people who are new to programming.

     

    by the way, thanks for suggestion.

    Sunday, April 22, 2007 5:02 PM
  • this will be better if u discuss after 22 april
    Sunday, April 22, 2007 8:52 PM
  • Here, I Post my quiz questions....
    I was able to solve the 1st one in the time limit but was not able to solve the other one... here goes the 1st one..

    Question 1

    There is a matrix with 9 rows and 9 columns. Each cell of the matrix is either black or white. With a single repaint operation, you can repaint all the cells in a single row or column black if the row or column already contains at least 5 black cells. Your goal is to make all the cells in the matrix black using a minimal number of repaint operations.

    You will be given a matrix array, where the jth character of the ith element represents the cell at row i, column j. Black cells will be written as '1' (one), and white cells will be written as '0' (zero). You have to return the minimal number of repaint operations required to make all the cells black, or -1 if this is impossible.

    Constraints

    ·  Each element of matrix will contain exactly 9 characters.

    ·  Each element of matrix will consist of '0' and '1' characters only.

    Example 1:
    Input:
                {"001111111",
                 "011111111",
                 "011111111",
                 "011111111",
                 "011111111",
                 "101111111",
                 "101111111",
                 "101111111",
                 "101111111"}

    Output: Returns 3
    Move 1: Repaint the first row.
    Move 2: Repaint the first column.
    Move 3: Repaint the second column.

    Example 2:
    Input:
                {"011111111",
                 "101111111",
                 "110111111",
                 "111011111",
                 "111101111",
                 "111110111",
                 "111111011",
                 "111111101",
                 "111111110"}

    Output: Returns 9
    Each white cell must be repainted separately.


    Monday, April 23, 2007 3:23 AM
  • Question 2

     

    You are given a 2*2 matrix and each row and column are associated with a positive integer value. You are required to write a program to determine four integers r1,r2,c1 and c2 which satisfy the following criteria for magic multiplication. The product of of r1 to c1 is same as the number associated with fist row, first column, product of r1 and c2 is same as the number present in first row, second column, product of r2 with c1 is same as the number present in second row, first column of the matrix and finally the product of r2 with c2 is same as the number present in the second row, second column of the matrix.


    The method used in this program is getMagicMultiplication which uses integer array 2*2 as input and returns a set of numbers that satisfy the criteria for magic multiplication.

    Constraints:

    ·  Return one solution which will be the best suited.

    ·  The output should be returned as {r1, r2, c1, c2}.

    Example 1:
    Input

    72

    132

    48

    88


    Output
         Returns {12,8,6,11}.

     

    6

    11

    12

    72

    132

    8

    48

    88

    In the above 2 * 2 matrix the values {72, 132, 48, 88} can be obtained by doing a magic multiplication as 12 * 6 = 72, 12 * 11 = 132, 8 * 6 = 48, 8 * 11 = 88. Therefore the values returned as output will be {12,8,6,11}.

    Example 2:
    Input

    25

    50

    75

    150


    Output
         Returns {5,15,5,10}.

     

    5

    10

    5

    25

    50

    15

    75

    150

    Monday, April 23, 2007 3:24 AM
  • Now I have the answer to the 1st question which works perfectly... but the problem is in the 2nd question.. can someone help me out in the 2nd question ???
    As i didnt had enough time left, i was not able to solve it,, but even now i m not able to get the logic that i should use to get the solution..
    Monday, April 23, 2007 3:28 AM
  •  Harshil_Patel_03b5f2 wrote:
    NameList
    There are two sections for grade 4 students and when moving to grade 5, the school management decided to merge them all into single section. You are required to write a program to merge students from both the sections in such a way that they are sorted in ascending order. Assume that no student names are repeated.

    This program uses a unique method getSortedNames. The method getSortedNames is unique because the data type it uses as input parameter is "vector names1, vector names2". The output of this method is again a vector which contains names in both names 1 set as well as names2 set arranged in ascending order.

    IMP: Remember to include header file #include <vector> for vector.

    Example 1:
    Input:
    names1[] = {"Aakash","Rohit","Babu"};
    names2[] = {"Uma","Vikram","Surya"}

    Output: Returns {"Aakash", "Babu", "Rohit", "Surya", "Uma", "Vikram"}

    Explanation: The method getSortedNames merges both the vectors in to a single vector as well arranges them in ascending order.

    Example 2:
    Input:
    names1[] = {"Clark","Harris","Smith","Davis","King","Adams","Campbell","Mitchell","Jackson"};
    names2[] = {"Barbara","Donald","Betty","Taylor","Anderson"}

    Output: Returns {"Adams", "Anderson", "Barbara", "Betty", "Campbell", "Clark", "Davis", "Donald", "Harris", "Jackson" , "King", "Mitchell", "Smith", "Taylor"}

    For C solutions
    Header File : NameList.h
    Function Name : vector<string> getSortedNames(vector<string> names1, vector<string> names2)
    Directory Name : namelist
    File Name : NameList.c
    For C++ solutions
    Header File : NameList.h
    Class Name : list
    Function Name : vector<string> getSortedNames()
    Directory Name : namelist
    FileName : NameList.cpp


    #include"NameList.h"
    #include<iostream>

    vector<string> list::getSortedNames() {
        vector<string> sortedstring;
        sortedstring.assign(names1.begin(), names1.end());
        sortedstring.insert(sortedstring.end(), names2.begin(), names2.end());
        sort(sortedstring.begin(), sortedstring.end());
        return sortedstring;
    }
    void dsmain() {
        list l1;
        l1.names1.push_back("Aakash");
        l1.names1.push_back("Rohit");
        l1.names1.push_back("Babu");
        l1.names2.push_back("Uma");
        l1.names2.push_back("Vikram");
        l1.names2.push_back("Surya") ;
        vector<string> sortedstring;
        sortedstring = l1.getSortedNames();
        vector<string>::iterator it;
        cout<<"Sorted List "<<endl;
        sort(sortedstring.begin(), sortedstring.end());
        for(it = sortedstring.begin() ; it != sortedstring.end() ; it++) {
            cout << *it << endl;
        }

    }


    Monday, April 23, 2007 9:43 AM
  •  Harshil_Patel_03b5f2 wrote:
    Write a program to pick out squarefree numbers from a given set of numbers. The criteria for a squarefree number is that it should not be a square value of its divisors and also its divisor should not be a sqaure value of its divisors. For example, 10 is square-free but 18 is not, as it is divisible by 9 = 32 .

    There are two methods used in this program and they are getNoOfSquareFreeNumbers and getSquareFreeNumbers. The method getNoOfSquareFreeNumbers uses a range of integer values and returns a single integer value which is the count of square free numbers present. The second method getSquareFreeNumbers returns all the numbers that satisfy the criteria for sqare free number.


    Example 1:
    Input
    from = 1
    to = 10
    Output
    Function getNoOfSquareFreeNumbers return : 7
    Function getSquareFreeNumbers returns : {1,2,3,5,6,7,10}

    Explanation:In this example the input range of numbers is from 1 to 10. The numbers that are missing in the output are {4,8 and 9}. If we consider the integer 4 we can see that the divisor 2 when squared will result in 4. So it is not a sqarefree number. The same goes for 8 and 9.

    Example 2:
    Input
    from = 4383
    to = 4400
    Output
    Function getNoOfSquareFreeNumbers return : 11
    Function getSquareFreeNumbers returns : {4385, 4386, 4387, 4389, 4390, 4391, 4393, 4395, 4397, 4398, 4399}

    For C solutions
    Header File : SquareFreeNumbers.h
    Function Name : int getNoOfSquareFreeNumbers(int from, int to), int* getSquareFreeNumbers(int from, int to)
    Directory Name : squarefreenumbers
    File Name : SquareFreeNumbers.c
    For C++ solutions
    Header File : SquareFreeNumbers.h
    Class Name : SquareFree
    Function Name : int getNoOfSquareFreeNumbers(int from, int to), int* getSquareFreeNumbers(int from, int to)
    Directory Name : squarefreenumbers
    FileName : SquareFreeNumbers.cpp




    #include"SquareFreeNumbers.h"
    #include<stdio.h>
    #include<conio.h>
    #include<stdlib.h>
    int isPerfectSquare(int);
    int isSquareFree(int);

    int isSquareFree(int no) {
        int j=0;
        for(j=2 ; j<=no ; j++) {
            if(no%j==0) { // factor
                if(isPerfectSquare(j)) { //Not square free
                    return 0;
                }
            }
        }
        return no;
    }
    int getNoOfSquareFreeNumbers(int from, int to) {
        int i=0,j=0, cnt=0, flag=0;
        for(flag=0, i=from ; i<=to ; i++) {
            if(isSquareFree(i)) {
                cnt++;
            }
        }
        return cnt;
    }
    int* getSquareFreeNumbers(int from, int to) {
        int *arr;
        int i, cnt=0;
        arr = (int *)malloc(sizeof(int) * (getNoOfSquareFreeNumbers(from, to)));
        for(i=from ; i<=to ; i++) {
            if(isSquareFree(i)) {
                arr[cnt++]=i;
            }
        }
        return arr;

    }

    int isPerfectSquare(int n) {
        int i=1;
        while( (i*i) != n) {
            if((i*i) >= n) {
                return 0;
            }
            i++;
        }
        return i;

    }
    void dsmain() {

        int n,from=4383, to=4400, i, *arr;
            from=1, to=10;
        n=getNoOfSquareFreeNumbers(from, to);
        arr = getSquareFreeNumbers(from, to);
        printf("Total No of Square Free Numbers : %d\n",n);
        printf("The square free numbers are :\n");
        for(i=0 ; i<n ; i++) {
            printf("%d ",arrIdea);
        }
    }

    Monday, April 23, 2007 9:43 AM
  •  Varun_Modi_a59ed9 wrote:
    Now I have the answer to the 1st question which works perfectly... but the problem is in the 2nd question.. can someone help me out in the 2nd question ???
    As i didnt had enough time left, i was not able to solve it,, but even now i m not able to get the logic that i should use to get the solution..


    Sorry m8 my friend also got one of those question, it was a hard one, i still cant find out the logic of it Sad
    Monday, April 23, 2007 9:45 AM
  • Block Counting
    Mantri builders have recently acquired a huge piece of land and they plan to sell blocks of land within that piece. You need to write a program to determine how many blocks of land are available in that piece. Consider this piece of land as a (x,y) graph in two dimensional space. If you have difficulty in imagining this, please refer to the graph provided in the example section below. The method countBlock uses two parameters as input and they are integer n, which is number of co ordinates in the graph and integer array coordinates, which is an array of 1*2.

    Constraints:
    # The number of coordinates should be a positive integer
    # The coordinate points in x and y quadrant should be a positive integer
    # The maximum number of coordinates n that can be given as input value should not exceed 100
    # The maximum number of coordinate combinations which is a 1*2 array that can be given as input value should not exceed 100 x*y points


    Example 1:
    Input
    int n = 6
    int coordinates[][2] = { {1,1}, {1,5}, {5,3}, {5,5}, {7,1}, {7,3} }.
         Click Here to view the example.

    Output Returns : 20
    Explanation: Count all the blocks inside the given coordinate values { {1,1}, {1,5}, {5,3}, {5,5}, {7,1}, {7,3} }. Hence the total number of blocks are 20.

    Example 2:
    Input
    int n = 8
    int coordinates[][2] = { {1,1}, {1,5}, {3,2}, {3,5}, {5,2}, {5,5}, {7,1}, {7,5} }.
    Output Returns : 18

    For C solutions
    Header File    :    BlockCounting.h
    Function Name    :    int countBlock(int n, int coordinates[][2]
    Directory Name    :    blockcounting
    File Name    :    BlockCounting.c
    For C++ solutions
    Header File    :    BlockCounting.h
    Class Name    :    block
    Function Name    :    int countBlock(int n, int coordinates[][2]
    Directory Name    :    blockcounting
    FileName    :    BlockCounting.cpp
    Monday, April 23, 2007 9:46 AM
  • In a class the students were asked to find the number of Upper and Lower case characters in a given sentence. Help the students by writing a program to find the number of Upper and Lower case characters in a sentence. The methods countUpperChar and countLowerChar holds one parameter called sentence. The functions returns the number of corresponding characters.
    Example 1:
    Input : char* sentence = {"DevSquare is an ONLINE development platform"}

    Output : Returns from method countUpperChar : 8
    Output : Returns from method countLowerChar : 30

    Example 2:
    Input : char* sentence = {"In English, CAPITAL letters are used as the first letter of a sentence or a PROPER NOUN and for INITIALS or ACRONYMS"}

    Output : Returns from method countUpperChar : 35
    Output : Returns from method countLowerChar : 59

    For C solutions
    Header File    :    UpperLower.h
    Function Name    :    int countUpperChar(char* sentence), int countLowerChar(char* sentence)
    Directory Name    :    UpperLower
    File Name    :    UpperLower.c
    For C++ solutions
    Header File    :    UpperLower.h
    Class Name    :    UpperLower
    Function Name    :    int countUpperChar(char* sentence), int countLowerChar(char* sentence)
    Directory Name    :    UpperLower
    FileName    :    UpperLower.cpp
    Monday, April 23, 2007 9:46 AM
  • Write a program to determine abundant numbers from a set of numbers. The criteria for a number to be an abundant number is that the divisors of that number when added should be greater than the product of that number with 2. As an example, consider the number 24. Its divisors are 1, 2, 3, 4, 6, 8, 12 and 24, whose sum is 60. Because 60 is more than 2 * 24, the number 24 is abundant.

    There are two methods used in this program and they are getNoAbundantNumbers and getAbundantNumbers. The method getNoAbundantNumbers uses a range of numbers as input value and returns a single integer value which is number of abundant numbers present in that range. The method getAbundantNumbers uses a range of numbers as input value and returns a set of numbers that satisfy the criteria for abundant numbers.

    Constraint:
    # The input value should be a non-zero positive integer and the range cannot exceed 10000.

    Example 1:
    Input:
             int from = 1
             int to = 50
    Output:
             Function getNoAbundantNumbers returns : 9
             Function getAbundantNumbers returns : {12, 18, 20, 24, 30, 36, 40, 42, 48}

    Explanation: The range of numbers is 1 to 50 and the method getNoAbundantNumbers returns 9 i.e there are 9 abundant numbers within that range which satisfy the criteria for abundant number. The method getAbundantNumbers returns all the numbers within that range which satisfy the criteria for abundant number and they are {12,18,20,24,30,36,40,42,48}. Consider integer 12 and the divisors for this numbers are 1,2,3,4,6,12. This number is a abundant number because after adding the divisors the resultant number is 28. Now the product of 12*2 is 24 which is less than the sum of its divisors. So this number is labelled abundant number.

    Example 2:
    Input:
             int from = 7567
             int to = 7600
    Output:
             Function getNoAbundantNumbers returns : 10
             Function getAbundantNumbers returns : {7568, 7572, 7578, 7580, 7584, 7588, 7590, 7592, 7596, 7600}

    For C solutions
    Header File    :    AbundantNumber.h
    Function Name    :    int getNoAbundantNumbers(int from, int to)&nbspint* getAbundantNumbers(int from, int to)
    Directory Name    :    abundantnumber
    File Name    :    AbundantNumber.c
    For C++ solutions
    Header File    :    AbundantNumber.h
    Class Name    :    AbundantNumber
    Function Name    :    int getNoAbundantNumbers(int from, int to)&nbspint* getAbundantNumbers(int from, int to)
    Directory Name    :    abundantnumber
    FileName    :    AbundantNumber.cpp
    Monday, April 23, 2007 9:46 AM
  • Gowthaman lives in Bangalore. His house is situated near a very busy large bus stop. But Gowthaman is tired of the traffic jams in the city so he wants to know the way to go from any place in the city to any other place with least number of buses traveled on. He goes to the bus stop and asks a bus conductor about his problem. But the conductor is an irritable chap and refuses to help him. After a lot of pestering he gives in to Gowthaman, but he does a weird trick: He only gives Gowthaman a schedule with a lot of tuples as follows:
    BUS NO,NODE 1,NODE 2

    The conductor also repeats the same tuple a lot of times for confusion. Gowthaman's task now is to go through the list and find out how many buses will be needed to travel from one point to another.

    Constraints:

        * Ignore the time of travel, start time and end time.
        * A bus with a specified bus number corresponds to one and only one path which can have multiple intermediate nodes. eg: Bus no 100 can have a path A-B-C-D-E but no other path in the city.
        * The input given will have no unreachable path conditions.
        * The bus number will be an integer, the node names are letters from the alphabet (A to Z).

    Example 1:
    Input
        int n = 11;
        int busNo[] = {100,100,101,102,101,102,103,104,105,105,105};
        char node1[] = {'A','B','A','D','A','D','D','B','E','E','E'};
        char node2[] = {'B','C','D','C','D','C','E','F','F','F','F'};
        char from = 'A';
        char to = 'F';

    Output: Returns 2.
    Explanation : As he needs to travel in two buses 100 that goes from A -> B and 104 that goes from B -> F from the starting to the destination place.

    For C solutions
    Header File    :    Buses.h
    Function Name    :    int getBuses(int n, int busNo[], char node1[], char node2[], char from, char to)
    Directory Name    :    busroute
    File Name    :    busroute.c
    For C++ solutions
    Header File    :    Buses.h
    Class Name    :    bus
    Function Name    :    int getBuses(int n, int busNo[], char node1[], char node2[], char from, char to)
    Directory Name    :    busroute
    FileName    :    busroute.cpp

    Monday, April 23, 2007 9:47 AM
  • There have been a lot of hard questions in the quiz this month. I think the next quiz will be even more harder, the level of toughness is increasing guys, do more practice.

    Any one of you guys got /  solved to the questions that i posted in the earlier post ? please post the solutions.
    Monday, April 23, 2007 9:49 AM
  • ya ur right
    Monday, April 23, 2007 11:16 AM
  • Question 1

    There is a matrix with 9 rows and 9 columns. Each cell of the matrix is either black or white. With a single repaint operation, you can repaint all the cells in a single row or column black if the row or column already contains at least 5 black cells. Your goal is to make all the cells in the matrix black using a minimal number of repaint operations.

    You will be given a matrix array, where the jth character of the ith element represents the cell at row i, column j. Black cells will be written as '1' (one), and white cells will be written as '0' (zero). You have to return the minimal number of repaint operations required to make all the cells black, or -1 if this is impossible.

    Constraints

    · Each element of matrix will contain exactly 9 characters.

    · Each element of matrix will consist of '0' and '1' characters only.

    Example 1:
    Input:
    {"001111111",
    "011111111",
    "011111111",
    "011111111",
    "011111111",
    "101111111",
    "101111111",
    "101111111",
    "101111111"}

    Output: Returns 3
    Move 1: Repaint the first row.
    Move 2: Repaint the first column.
    Move 3: Repaint the second column.

    Example 2:
    Input:
    {"011111111",
    "101111111",
    "110111111",
    "111011111",
    "111101111",
    "111110111",
    "111111011",
    "111111101",
    "111111110"}

    Output: Returns 9
    Each white cell must be repainted separately.

    Code Snippet

    Solution :

    #include<iostream.h>

    #include<conio.h>

    class repaint

    {

    public :

    int matrix[9][9];

    int MatrixRepaint();

    };

    #define row 0

    #define column 1

    int repaint::MatrixRepaint()

    {

    int CalculateBlack(int matrix[9][9], int *row_or_column, int *row_or_column_no);

    int count = 0;

    int row_or_column, row_or_column_no, i , j;

    // While We find a valid row or column to repaint...

    while(CalculateBlack(matrix, &row_or_column, &row_or_column_no))

    {

    count++;

    int tmp;

    if(row_or_column == row)

    {

    for(i = 0; i<9; i++)

    matrix[row_or_column_no][i] = 1;

    }

    else

    {

    for(i = 0; i<9; i++)

    matrix[i][row_or_column_no] = 1;

    }

    }

    int flag= 1;

    for(i=0;i<9;i++)

    for(j=0;j<9;j++)

    {

    if(matrix[i][j] != 1)

    flag = 0;

    }

    if(flag)

    return count;

    else

    return -1;

    }

    int CalculateBlack(int matrix[9][9], int *row_or_column, int *row_or_column_no)

    {

    // flag = 0;

    int i, j;

    int no_of_black[2][9] = {0};

    // Calculating the Number of Black Blocks in Each Row & column

    for(i=0; i<9; i++)

    for(j=0; j<9; j++)

    {

    if(matrix[i][j] == 1)

    {

    no_of_black[row][i]++;

    no_of_black[column][j]++;

    }

    }

    int min = 9;

    // Calculating the Row or Column With Minimum No. of Black Blocks But with atleast 5

    // Black Blocks...

    for(i=0;i<2; i++)

    for(j=0; j<9; j++)

    {

    if(no_of_black[i][j] < min && no_of_black[i][j] >= 5)

    {

    min = no_of_black[i][j];

    *row_or_column = i;

    *row_or_column_no = j;

    }

    }

    // If we find a valid row or column to repaint we return 1 or else 0

    if(min != 9)

    return 1;

    else

    return 0;

    }

    void copy( int matrix1[9][9], char matrix2[9][10])

    {

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

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

    {

    if(matrix2[i][j] == '1')

    matrix1[i][j] = 1;

    else

    matrix1[i][j] = 0;

    }

    }

    void main()

    {

    repaint b1;

    char tmp[9][10] = {"001111111",

    "011111111",

    "011111111",

    "011111111",

    "011111111",

    "101111111",

    "101111111",

    "101111111",

    "101111111"};

    copy(b1.matrix, tmp);

    cout<<b1.MatrixRepaint();

    }


    Monday, April 23, 2007 2:54 PM
  • Now for the second question

    Input

    72

    132

    48

    88


    Output
         Returns {12,8,6,11}.

     

    6

    11

    12

    72

    132

    8

    48

    88

    In the above 2 * 2 matrix the values {72, 132, 48, 88} can be obtained by doing a magic multiplication as 12 * 6 = 72, 12 * 11 = 132, 8 * 6 = 48, 8 * 11 = 88. Therefore the values returned as output will be {12,8,6,11}.

    Example 2:
    Input

    25

    50

    75

    150


    Output
         Returns {5,15,5,10}.

     

    5

    10

    5

    25

    50

    15

    75

    150



    -------------------------------------------------------------------------------

    I m not getting the logic to use to solve it... I tried finding out the Greatest Common divisors of the related numbers, but it didnt work.. can someone help me out here.. I really want to solve it....
    Monday, April 23, 2007 3:05 PM
  • @Varun i think you need to do a brute force with the common factors found for each element in the matrix. I still cant find out the logic how to get the solution for it. I also want to solve it......
    Monday, April 23, 2007 3:19 PM
  • Hey... really, this pro is too hard to solve.

    and also multiple output is there..

     

    for input :

    72       132

    48       88

     

    Output 1:

     

              6        11

    ---------------------

    12     72      132

    8       48      88

     

    Output 2:

     

           12      22

    --------------------

    6     72      132

    4     48      88

     

    and so on...

    Monday, April 23, 2007 5:54 PM
  • Nice observation buddy.. i didnt thought of it before... now what can we do to solve it... well i was 1st thinking of getting the gcd first, but looks like i will have to modify that strategy or if someone can add to this ???
    Monday, April 23, 2007 6:53 PM
  • Alright people, finally i hv cracked the problem.. I have derived the solution, and its so easy...
    Does anyone wants to have the solution??? Now the solution is simple, but try it urself first.. If you are not able to do it, i will post the answer here... I will wait for 3 people to ask for the answer here, than i will post the answer...

    Harshil will also get a good response to this thread, after all it was his idea to start this thread and where we all met
    Monday, April 23, 2007 7:14 PM
  • Hey varun,

     

    I tried it, but my program is giving right answer but not same as example… as I explained before.

    Multiple outputs are possible in this problem.

     

    Is your program giving exact output?

     

    If yes, I definitely like to see it.

     

    Tuesday, April 24, 2007 8:22 AM
  • Thanks @Varun , and first of all congratulations for solving the problem finally. As i am having exams, i didn't try solving the question, but i tried a to to find out the logic of the problem, for which i failed.  I think i am the 2nd person who is requesting for the solution to that problem. Waiting for one more chap to request, so that we all get have a look at the code, and also if you dint mind, explain the logic first. and then post the solution.
    Tuesday, April 24, 2007 9:36 AM
  • When, you said about the multiple answers exist, I got a way to find a valid answer....
    Though my code same output for the 1st example, for 2nd one it gives a different but a valid answer to the example... this can be extended to any question and it will give a valid answer if it exists...

    Will surely like to know what logic you used for your code
    Tuesday, April 24, 2007 11:22 AM
  • Ya guys, post the logic Smile its becoming harder to wait Smile
    Tuesday, April 24, 2007 12:51 PM
  • Okkk..
    So here comes the million dollar answer...

    1st the code.... looking at the code you should be able to understand the logic.. if still its not clear than i will try to explain it.. i will also appreciate other memebers to post their code for this problem...



    Code Snippet


    #include<stdio.h>
    #include<iostream.h>

    int gcd(int x, int y)
    {
        if(y==0)
            return (x);
        else
            return(gcd(y, x%y));



    int* getMagicMultiplication(int matrix[2][2])
    {
         int *ans;
         ans = new int[4];
         ans[0] =   gcd(matrix[0][0], matrix[0][1]);

         ans[2] = matrix[0][0] / ans[0];
         ans[1] = matrix[1][0] / ans[2];
         ans[3] = matrix[1][1] / ans[1];
         return (ans);
    }

    void main()
    {
        int matrix[2][2];
        int *ans, i;
        matrix[0][0] = 72;
        matrix[0][1] =132;
        matrix[1][0] =48;
        matrix[1][1] =88;
        ans = getMagicMultiplication(matrix);
        for(i=0;i<4;i++)
            printf("%d ",ans[i]);
    }


    Tuesday, April 24, 2007 4:31 PM
  • I did this program in C...

    and I didn't use gcd function.

    I got factors manually.

    so, it got somewhat lengthy..

    logic is almost same.

    Tuesday, April 24, 2007 5:33 PM
  • this program was originally written in C only.. its just i was doing some test so had included iostream.h but you can exclude it n run the same code in c.. it will run fine...
    GCD function is also written by me only.. just to make things look simpler i made it as a function, but still don know if this would work, because the prog gives a valid output, but not same as given by them for the 2nd example.. it differs... don know what logic they are using...
    Tuesday, April 24, 2007 6:10 PM
  • yaa.. I know that ur most of code is of C language and anyone can understand it...

    but you have included <iostream.h>

    that's y I cleared it....

     

    and I m telling that I haven't created any function, so my coding is lengthy.

    I know that you have created and used GCD function (by U only....)

     

    and I had already told you that program may give different but correct output. 

     

     

    Tuesday, April 24, 2007 6:31 PM
  • Hey buddy, I was not taunting or anything like that... Its nothing like that.. i m sorry if u felt so.. i was just highlighting the points of my code.. 
    Can you post your code also???
    Wednesday, April 25, 2007 3:11 AM
  • It's ok dear..

    I don't like to post my code here.. because your code is better than me.

    My coding is very larger.

    because I applied lengthy method (loop instead of recursive function) to find GCD.

    and other logic is same..

    that's y....

     

    Wednesday, April 25, 2007 9:08 AM
  • First of all thanks varun for posting the code. I now finally have understood the logic Smile after seeing the code, the logic seems to look like a piece of cake Stick out tongue why the hell we wasn't able to solve such an easy question Stick out tongue hehe

    And one more thing i have to point ut guys. Please dont fight, we need to create a good and healthy community here Smile
    Wednesday, April 25, 2007 10:28 AM
  • thnks varun. ... nice posts.... .!!. .
    Wednesday, April 25, 2007 6:02 PM
  • @ harshil

    u r right  dude.....

     

    v should not fight here,...we are the members ..

    if we won't unite then Admins will  take the advantage of this 

    Wednesday, April 25, 2007 7:17 PM
  • Hey people no one is fighting over here... please dont take it this way..

    Now, both of my problems are solved.. Now we can jump to someone else's problem which is still unsolved.. But please one at a time.. can we have the next problem???

    If there is no one else with any unsolved problems than i have a classic problem which is still unsolved... I dont have the exact question, but remmber what the question was.. it was of the shortest route from location [0,0] to [R,C] in a RxC Matrix, where each block has some Natural value and the summation of the blocks that comes under this route is smallest...
    Thursday, April 26, 2007 2:59 AM
  • Dear Friend,

     

    Can't you provide answers for some more questions like this. If time permits kindly do so. Then we all will be benefitted.

     

    Regards

    Thursday, April 26, 2007 9:18 AM
  • Thanks for the post buddy !
    Thursday, April 26, 2007 1:01 PM
  • Maze

    You are in a maze which resembles a matrix and has r rows and c columns. A positive integer number is associated with each row and column in this matrix. Please refer image in Example 1.

    Write a program to generate shortest path from (0x0) point in the maze to (rxc) point. The condition for shortness is defined by the end summation of all the numbers in that path and this number should be the least of all other paths. The method mazeMove uses positive integer r, positive integer c and integer array (rxc) as input parameters. The output of this method will compare all the summation from (0x0) point to (rxc) point and returns the least of these summations.

    Constraints:


    The number of rows and columns should not exceed 20x20
    The maximum value for each row and column cannot exceed 100
    Assume that there will be only one smallest path.

    Example 1:
    Input
    int r = 6
    int c = 5
    int values[][20] = { { 5, 6, 7, 10, 13 },
                               { 2, 4, 1, 15, 10 },
                               { 15, 3, 1, 2, 10 },
                               { 23, 15, 12, 3, 14 },
                               { 1, 9, 8, 6, 21 },
                               { 11, 10, 3, 3, 4 } };

         Click Here to view the example.

    Output Returns : 31
    Explanation: Add all the values from (0,0) to (6,5) with the path mentioned in example image which will be the smallest path with the summation of 31. Hence 31 is returned from the function.

    Example 2:
    Input
    int r = 4
    int c = 6
    int values[][20] = { { 5, 6, 7, 10, 11, 3},
                               {2, 10, 5, 6, 1, 10},
                               {1, 2, 12, 5, 6, 1},
                               {3, 1, 6, 2, 21, 13 } };

    Output Returns : 44

    For C solutions  
    Header File : Maze.h
    Function Name : int mazeMove( int r, int c, int values[][20])
    Directory Name : maze
    File Name : Maze.c
    For C++ solutions  
    Header File : Maze.h
    Class Name : maze
    Function Name : int mazeMove( int r, int c, int values[][20])
    Directory Name : maze
    FileName : Maze.cpp

    Friday, April 27, 2007 12:39 PM
  • @Varun, i have posted the question to that maze problem that you was requesting Sad It was also a hard one, i cant find out the solution to it. Also one more problem is there about the BUS ROUTE, i will post that later, after we have done discussions on this MAZE problem.
    Friday, April 27, 2007 12:41 PM
  • Thankz for the problem.. can you also post the link to the image where answer is given, so that it becomes easy to work with the answer...

    Now one of the method i thought of was "Greedy Approach", i.e. we start with the block (0,0) and select the adjacent box which has the least value, i.e. having a greedy approach to it.. that way we will stop when we reach the end block(r,c)...

    Now this solution does have some problems as it wont give the correct answer all the time.... but its a better choice... what do you guys have to say about it???
    Friday, April 27, 2007 2:13 PM
  • Sure m8, let me try finding the image to that maze problem. I also think that the greedy approach can be used. The problem is that it will become to complex Stick out tongue
    Friday, April 27, 2007 4:01 PM
  • OK here is the link to the maze image.

    Friday, April 27, 2007 4:03 PM
  • Thankz for the image buddy...

    Now for the complexity, I think that accepting a greedy method wont take the complexity too high as compared to other methods.. I know of one method which is a sure short answer to the problem but it has the highest complexity,

    The method is to take into consideration all the possible rootes to reach the point and then selecting the minimum one.. but this has the highest complexity and it will be too long... there has to be a better solution to it...

    Now say how to use Greedy method in solving it?? what should be the controling points and how the process should move.... I tried the greedy method that i talked about in the 1st exmple, offcourse manually, but i can write that code... It works for the 1st one...

    But it doesnot work for the 2nd one..

    so what should we do ???
    Friday, April 27, 2007 5:50 PM

  • Write a program to generate a list of Happy Numbers from a given range of numbers. The steps to determine whether a number is a happy number or not is as follows.
    Each digit in that number is squared and summed up. This action is performed repeatedly with the resulting numbers till the summation ends up being the number 1. If this happens then the number is termed as Happy Number.
    The method used in this program is getHappyNumbers and this method uses integer range of numbers as input and the output is a list<int> of numbers that satisfies the criteria for happy numbers. The datatype for this result is list<int> and it should be mentioned while defining this method.

    Constraint:


    The input value should be a non-zero positive integer and it should not exceed 10000.
    IMP:

    Remember to include header file #include<list> for list.


    Example 1:
    Input:
             int from = 15
             int to = 50

    Output: Returns {19, 23, 28, 31, 32, 44, 49}

    Explanation: There are 7 numbers with range from 15 to 50. First happy number is 19 and let us take the number 19 for explanation. As per the description let us square 1 and 9 and add them(12 + 92). The result is 82. Now repeating the previous step again for this number 82. The result is 68. Again repeating the first step and the result is 100. Now performaing the step one again on this number resluts in 1. So this number 19 is a Happy Number.

    Example 2:
    Input:
             int from = 1101
             int to = 1175

    Output: Returns {1112, 1114, 1115, 1121, 1122, 1125, 1128, 1141, 1148, 1151, 1152, 1158}

    For C solutions 
    Header File : HappyNumbers.h
    Function Name : list<int> getHappyNumbers(int from, int to)
    Directory Name : happynumbers
    File Name : HappyNumbers.c
    For C++ solutions 
    Header File : HappyNumbers.h
    Class Name : happy
    Function Name : list<int> getHappyNumbers(int from, int to)
    Directory Name : happynumbers
    FileName : HappyNumbers.cpp


    General Instructions:     * The directory , file / class names, functions, method signatures, header files to be used are mentioned in the problem statement. Do not use your own names or change the method signatures and fields. You can add any number of additional methods.
     
        * First add the directory in the Main Program Directory and then add the particular file in that directory. Do not forget to mention the file extension, either .c or .cpp as the case maybe.
     
        * For C solutions, change the value of "C_OR_CPP" macro in header file as 1 and for C++ solutions change the value as 2.
     
        * Incase of iostream.h specify as iostream only. 


    #include<conio.h>
    #include<iostream>
    #include<list>

    using namespace std;

    list<int> getHappyNumbers(int from, int to)
    {
         list<int> happyNumbers = list<int>();
         list<int> temp;
         list<int>::iterator it;
        
         int ctr, number, sum, digit, ctr2, flag;
        
         if(from <= 0 || to <= 0)
         {
              cout<<"Invalid numbers as numbers should be > 0.";
              return happyNumbers;
         }
        
         if(to < from)
         {
              cout<<"Range improper. Value of parameter \'to\' should be ";
              cout<<"greater than \'from\' parameter.";
              return happyNumbers;
         }
        
         if(to > 10000)
         {
              cout<<"Max possible number is 10000. Range should not exceed that.";
              return happyNumbers;
         }
        
         for(ctr = from ; ctr <= to ; ctr++)
         {   
              number = ctr;
              ctr2 = 0;
              flag = 1;
              temp = list<int>();
             
              flag = 1;
             
              while(flag == 1)
              {
                  sum = 0;

                  while(number != 0)
                  {
                       digit = number % 10;
                       number = number / 10;
                       sum += (digit * digit);
                  }
                 
                  if(sum == 1)
                  {
                       happyNumbers.push_back(ctr);
                       flag = 0;
                       break;
                  }
                  else
                  {
                       for(it = temp.begin() ; it != temp.end() ; it++)
                       {
                              if(*it == sum)
                              {
                                     flag = 0;
                                     break;
                              }
                       }
                       temp.push_back(sum);
                       number = sum;
                  }
              }
         }
        
         return happyNumbers;
    }

    int main(void)
    {
         list<int> result;
         list<int>::iterator it;
        
         cout<<"\n\nHappy numbers between 15 and 50 : ";    
         cout<<"\n-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=\n";    
         result = getHappyNumbers(15, 50);
         for(it = result.begin() ; it != result.end() ; it++)
         {
                cout<<" "<<*it;
         }

         cout<<"\n\nHappy numbers between 1101 and 1175 : ";    
         cout<<"\n-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=\n";    
         result = getHappyNumbers(1101, 1175);
         for(it = result.begin() ; it != result.end() ; it++)
         {
                cout<<" "<<*it;
         }

         cout<<"\n\nHappy numbers between 15 and 10 : ";    
         cout<<"\n-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=\n";    
         result = getHappyNumbers(15, 10);
         for(it = result.begin() ; it != result.end() ; it++)
         {
                cout<<" "<<*it;
         }

         cout<<"\n\nHappy numbers between -15 and -10 : ";    
         cout<<"\n-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=\n";    
         result = getHappyNumbers(-15, -10);
         for(it = result.begin() ; it != result.end() ; it++)
         {
                cout<<" "<<*it;
         }

         cout<<"\n\nHappy numbers between 1000 and 10001 : ";    
         cout<<"\n-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-\n";    
         result = getHappyNumbers(1000, 10001);
         for(it = result.begin() ; it != result.end() ; it++)
         {
                cout<<*it<<"  ";
         }

         getch();    
    }


    Friday, April 27, 2007 5:58 PM
  • Thanks sanket for the Happy Numbers problem  Smile

    and varun, on the first look the problem seems simple, but when we try to implement it we get stuck. the main problem i faced was how to make the computer know in which direction to go. Now to make it easy, suppose we assume that we want to ONLY move in right down direction, but then when i tried implementing my program got stuck in a loop cause when it shifted the control to another box in the maze image, it found out that the earlier box which we came from was the minimum, and hence it tried shifting the control to there Sad so i guess we will have to keep track of what all places we visited, and if have already visited a place, then find the next minimum.
    Friday, April 27, 2007 6:09 PM

  • Write a program to find out the relationship between you and your partner. Your program must select one among these relationship (Friend, Love, Affection, Marriage, Enemy or Sister). The program must take two names as input eliminate the similar alphabets in both the words and count the remaining number of alphabets and calculate the corresponding relationship. As we must have heard of FLAMES your program must implement the concept of flames.

    Constraints:
    Consider upper and lower case character are same.
    Names contains only alphabets.
    If both names are same return as FRIEND.

    Example 1:
    Input
    k1[]= "Fernando Gonzalez"
    k2[]= "Roger Federer"
    Output
    Returns MARRIAGE.
    Consider the word FLAMES where F-Friend, L-Love, A-Affection, M-Marriage, E-Enemy, S-Sister. Here in the above example by eliminating the similar alphabets we get a total count of 14 (nanonzalzRerer) by combining both the words so the count starts from F in the FLAMES and it continues till it reaches the 14th character in the word FLAMES. The letter L gets eliminated in the first count and S,E,A,F in similar fashion and the remaining letter which is left out is to be returned as the output. Therefore the left out letter M - MARRIAGE is returned as output.

    Example 2:
    Input
    k1[]= "White"
    k2[]= "Davis"
    Output
    Returns AFFECTION.

    Example 3:
    Input
    k1[]= "Hernandez"
    k2[]= "Martinez"
    Output
    Returns ENEMY.

    For C solutions
    Header File : MatchFinder.h
    Function Name : char* matchfinder(char k1[], char k2[])
    Directory Name : MatchFinder
    File Name : MatchFinder.c
    For C++ solutions
    Header File : MatchFinder.h
    Class Name : finder
    Function Name : char* matchfinder(char k1[], char k2[])
    Directory Name : MatchFinder
    FileName : MatchFinder.cpp


    General Instructions: * The directory , file / class names, functions, method signatures, header files to be used are mentioned in the problem statement. Do not use your own names or change the method signatures and fields. You can add any number of additional methods.

    * First add the directory in the Main Program Directory and then add the particular file in that directory. Do not forget to mention the file extension, either .c or .cpp as the case maybe.

    * For C solutions, change the value of "C_OR_CPP" macro in header file as 1 and for C++ solutions change the value as 2.

    * Incase of iostream.h specify as iostream only.


    #include<conio.h>
    #include<iostream>
    #include<ctype.h>
    #include<malloc.h>
    #include<string>

    using namespace std;

    char* matchfinder(char k1[], char k2[])
    {
    int ctr, length1, length2, totalLength, common = 0, ctr2, flag;
    int *flames = (int *)calloc(6, sizeof(int));
    int flamesLength = 6;
    int pass;
    char temp;
    int *name1, *name2;
    char flamesString[6][10] = {"Friend", "Love", "Affection", "Marriage",
    "Enemy", "Sister"};

    length1 = strlen(k1);
    name1 = (int *)calloc(length1, sizeof(int));
    length2 = strlen(k2);
    name2 = (int *)calloc(length2, sizeof(int));

    totalLength = length1 + length2;

    strlwr(k1);
    strlwr(k2);

    if(strcmp(k1, k2) == 0)
    {
    return flamesString[0];
    }

    for(ctr = 0 ; ctr < length1 ; ctr++)
    {
    if(!(isalpha(k1[ctr]) || isspace(k1[ctr])))
    {
    return "INVALID STRING.";
    }
    }

    for(ctr = 0 ; ctr < length2 ; ctr++)
    {
    if(!(isalpha(k2[ctr]) || isspace(k2[ctr])))
    {
    return "INVALID STRING.";
    }
    }

    for(ctr = 0 ; ctr < length1 ; ctr++)
    {
    flag = 1;

    for(ctr2 = 0 ; ctr2 < length2 && flag == 1; ctr2++)
    {
    if(k1[ctr] == k2[ctr2] && name2[ctr2] == 0)
    {
    name1[ctr] = name2[ctr2] = 1;
    totalLength -= 2;
    flag = 0;
    break;
    }
    }
    }

    ctr2 = 0;

    for(ctr = 0 ; ctr < 6 ; )
    {
    if(flames[ctr] == 0)
    {
    ctr2++;

    if(ctr2 == totalLength)
    {
    flames[ctr] = 1;
    flamesLength--;
    ctr2 = 0;
    }
    }

    if(flamesLength == 1)
    {
    break;
    }

    ctr++;

    if(ctr == 6)
    {
    ctr = 0;
    }
    }

    for(ctr = 0 ; ctr < 6 ; ctr++)
    {
    if(flames[ctr] == 0)
    {
    return flamesString[ctr];
    }
    }
    }

    int main(void)
    {
    char name1[20];
    char name2[20];
    char result[15];

    strcpy(name1, "Fernando Gonzalez");
    strcpy(name2, "Roger Federer");
    strcpy(result, matchfinder(name1, name2));
    cout<<result<<endl;

    strcpy(name1, "White");
    strcpy(name2, "Davis");
    strcpy(result, matchfinder(name1, name2));
    cout<<result<<endl;

    strcpy(name1, "Sanket");
    strcpy(name2, "Swati");
    strcpy(result, matchfinder(name1, name2));
    cout<<result<<endl;

    strcpy(name1, "Hernandez");
    strcpy(name2, "Martinez");
    strcpy(result, matchfinder(name1, name2));
    cout<<result<<endl;

    strcpy(name1, "Student");
    strcpy(name2, "Rockstar");
    strcpy(result, matchfinder(name1, name2));
    cout<<result<<endl;

    strcpy(name1, "Student");
    strcpy(name2, "student");
    strcpy(result, matchfinder(name1, name2));
    cout<<result<<endl;

    strcpy(name1, "Student");
    strcpy(name2, "student-");
    strcpy(result, matchfinder(name1, name2));
    cout<<result<<endl;

    getch();
    }



    Friday, April 27, 2007 6:14 PM
  • Sanket, Thanks for the FLAMES problem and solution Smile

    Can you help us try solving the MAZE problem ? it too seems to be complicated.
    Friday, April 27, 2007 6:21 PM
  • its nice solutions
    Friday, April 27, 2007 6:28 PM
  • Ya we can do that by having a parallel matrix which stores the flags for the visited blocks.. that way we can avoid going back to the same block...

    but now there is also a possibility that we end up at a dead end or like the snake game, we go on hiting at the ourself.... so need to think over there...
    Friday, April 27, 2007 6:41 PM
  • Maze problem .............solution .............

     

     

     

     

    #include <stdio.h>
    #include<alloc.h>
    #include <conio.h>


    int r = 4;
    int c = 6;
    int values[][20] = { { 5, 11, 11, 11, 11, 11},
          { 1, 11, 11, 11, 10, 11},
          { 1,  1, 11, 1 , 1 , 1 },
          { 11, 1, 1 , 1 , 10 ,1}};
    int min(int a,int b);
    int minimum(int arr[],int visited[],int n);
    int makeCostMatrix(int r,int c,int arr[20][20],int *cost[400]);
    int mazeMove(int r,int c,int values[][20]);

    int min(int a,int b)
    {
     return a<b?a:b;
    }

    int minimum(int arr[],int visited[],int n)
    {
     int small=9999,i;
     for(i=1;i<=n;i++)
     {
      if(visitedIdea==1)
       continue;
      if(arrIdea<small)
       small=arrIdea;
     }
     for(i=1;i<=n;i++)
     {
      if(visitedIdea==1)
       continue;
      if(arrIdea==small)
       return i;
     }
     return 0;
    }

    int makeCostMatrix(int r,int c,int arr[20][20],int *cost[400])
    {
     int cnt=0,i,j;
     for(i=0;i<r;i++)
     {
      for(j=0;j<c;j++)
      {
       int nodeNo = i*c+j;
       if(j+1<c)        //next in row
       {
        cost[nodeNo][nodeNo+1]=arr[nodeNo/c][(nodeNo+1)%c];
        cnt++;
       }
       if(j-1>=0)       //prev in row
       {
        cost[nodeNo][nodeNo-1]=arr[(nodeNo-1)/c][(nodeNo)%c];
        cnt++;
       }
       if(i+1<r)        //down in col
       {
        cost[nodeNo][nodeNo+c]=arr[(nodeNo+c)/c][(nodeNo)%c];
        cnt++;
       }
       if(i-1>=0)       //up in col
       {
        cost[nodeNo][nodeNo-c]=arr[(nodeNo)/c][(nodeNo-c)%c];
        cnt++;
       }
      }
     }
     return cnt/2;
    }

    int mazeMove(int r,int c,int values[][20])
    {
     int i,j,k,l[400],path[400],pl=0,visited[400]={0},v;
     int start=0,end=r*c-1,cnt=r*c-1;
     int *cost[400];
     for(i=0;i<400;i++)
      costIdea = (int*)malloc(400);
     for(i=0;i<r*c;i++)
      for(j=0;j<r*c;j++)
       costIdea[j]=9999;
     makeCostMatrix(r,c,values,cost);
     for(i=0;i<400;i++)
     {
      lIdea=9999;
      pathIdea=-1;
     }
     v=start;
     visited[v]=1;
     path[start]=0;
     for(i=0;v!=end;i++)
     {
      for(j=0;j<=cnt;j++)
      {
       if(visited[j]==1)
        continue;
       l[j]=min(l[j],pl+cost[v][j]);
       if(min(l[j],pl+cost[v][j])==pl+cost[v][j])
        path[j]=v;
      }
      v=minimum(l,visited,cnt);
      visited[v]=1;
      pl=l[v];
     }
     for(k=0,i=end;i!=startWink
     {
      visited[k++]=pathIdea;
      i=pathIdea;
     }
     return pl+values[0][0];
    }

    void main()
    {
     clrscr();
     printf("\n%d",mazeMove(r,c,values));
     getch();
    }

    Friday, April 27, 2007 7:11 PM
  • thankz for the code, but it is having some errors as the smileys replaced some of the key terms.. please use the code block for giving the codes....

    Well your program works, i just checked it, but please tell the logic u used to do it....
    Saturday, April 28, 2007 2:41 AM
  • try replacing the matrix value with the one i m giving...

    int r = 4;
    int c = 6;
    int values[][20] = { { 5,  6,  7, 10, 11,  3},
                         { 2, 10,  5,  6,  1, 10},
                         { 1,  2, 12,  5,  6,  1},
                         { 3,  1,  6,  2, 21 ,13}};

    At quiz this example was given.. now the answer was suppose to be 44, but your code is giving 41.. now how did the code found 41 as answer??

    If you can just trace down, you would get the idea of whatz going on, and please do explain the logic that you applied.
    Saturday, April 28, 2007 2:50 AM
  • Thanks dude for  the code. It would be nice if you give the logic of your code, its a bit tricky Stick out tongue
    Saturday, April 28, 2007 2:19 PM
  • Helloo Anyone Out there.. why did we stopped.... Rajkumar Please explaing the logic you u used...
    Tuesday, May 1, 2007 2:58 AM
  • I think no one is interested anymore in that maze solution.

    Lets post another question Smile
    Tuesday, May 1, 2007 4:38 PM
  • Code Snippet

    Block Counting
    Mantri builders have recently acquired a huge piece of land and they plan to sell blocks of land within that piece. You need to write a program to determine how many blocks of land are available in that piece. Consider this piece of land as a (x,y) graph in two dimensional space. If you have difficulty in imagining this, please refer to the graph provided in the example section below. The method countBlock uses two parameters as input and they are integer n, which is number of co ordinates in the graph and integer array coordinates, which is an array of 1*2.

    Constraints:
    # The number of coordinates should be a positive integer
    # The coordinate points in x and y quadrant should be a positive integer
    # The maximum number of coordinates n that can be given as input value should not exceed 100
    # The maximum number of coordinate combinations which is a 1*2 array that can be given as input value should not exceed 100 x*y points


    Example 1:
    Input
    int n = 6
    int coordinates[][2] = { {1,1}, {1,5}, {5,3}, {5,5}, {7,1}, {7,3} }.
         Click Here to view the example.

    Output Returns : 20
    Explanation: Count all the blocks inside the given coordinate values { {1,1}, {1,5}, {5,3}, {5,5}, {7,1}, {7,3} }. Hence the total number of blocks are 20.

    Example 2:
    Input
    int n = 8
    int coordinates[][2] = { {1,1}, {1,5}, {3,2}, {3,5}, {5,2}, {5,5}, {7,1}, {7,5} }.
    Output Returns : 18

    For C solutions
    Header File    :    BlockCounting.h
    Function Name    :    int countBlock(int n, int coordinates[][2]
    Directory Name    :    blockcounting
    File Name    :    BlockCounting.c
    For C++ solutions
    Header File    :    BlockCounting.h
    Class Name    :    block
    Function Name    :    int countBlock(int n, int coordinates[][2]
    Directory Name    :    blockcounting
    FileName    :    BlockCounting.cpp


    Tuesday, May 1, 2007 4:39 PM

All replies

  • Write a program to pick out squarefree numbers from a given set of numbers. The criteria for a squarefree number is that it should not be a square value of its divisors and also its divisor should not be a sqaure value of its divisors. For example, 10 is square-free but 18 is not, as it is divisible by 9 = 32 .

    There are two methods used in this program and they are getNoOfSquareFreeNumbers and getSquareFreeNumbers. The method getNoOfSquareFreeNumbers uses a range of integer values and returns a single integer value which is the count of square free numbers present. The second method getSquareFreeNumbers returns all the numbers that satisfy the criteria for sqare free number.


    Example 1:
    Input
             from = 1
             to = 10
    Output
             Function getNoOfSquareFreeNumbers return : 7
             Function getSquareFreeNumbers returns : {1,2,3,5,6,7,10}

    Explanation:In this example the input range of numbers is from 1 to 10. The numbers that are missing in the output are {4,8 and 9}. If we consider the integer 4 we can see that the divisor 2 when squared will result in 4. So it is not a sqarefree number. The same goes for 8 and 9.

    Example 2:
    Input
             from = 4383
             to = 4400
    Output
             Function getNoOfSquareFreeNumbers return : 11
             Function getSquareFreeNumbers returns : {4385, 4386, 4387, 4389, 4390, 4391, 4393, 4395, 4397, 4398, 4399}

    For C solutions
    Header File    :    SquareFreeNumbers.h
    Function Name    :    int getNoOfSquareFreeNumbers(int from, int to), int* getSquareFreeNumbers(int from, int to)
    Directory Name    :    squarefreenumbers
    File Name    :    SquareFreeNumbers.c
    For C++ solutions
    Header File    :    SquareFreeNumbers.h
    Class Name    :    SquareFree
    Function Name    :    int getNoOfSquareFreeNumbers(int from, int to), int* getSquareFreeNumbers(int from, int to)
    Directory Name    :    squarefreenumbers
    FileName    :    SquareFreeNumbers.cpp

    Saturday, April 21, 2007 3:28 PM
  • Guys, can we discuss / post the solutions now or after the quiz is over ?
    Saturday, April 21, 2007 3:29 PM
  • nice dear
    Saturday, April 21, 2007 3:34 PM
  • this should be posted after the quiz is done i believe.. i believe that the questions will not repeated.. lets see i'm taking the quiz 2morrow..
    Saturday, April 21, 2007 5:37 PM
  • Try some more with the same
    Sunday, April 22, 2007 4:02 AM
  • Yes guys, i think i will wait till tomorrow and then we can start posting the solutions ): But as the questions may not be repeated, i guess we can atleast paste the questions here Smile so that others who are interested can try to solve it.
    Sunday, April 22, 2007 5:22 AM
  • We should not post answers right now...

    but we can share our quiz-3 experience.

     

    I think, this format with 2 questions is better than old one.

    and questions are also nice.

    Right?

    Sunday, April 22, 2007 10:50 AM
  • I agree with you hiren, but the level of the questions are getting harder , there are 2 questions, one was easy another was hard  Atleast we can solve the easy one if incase we dont solve the harder one. We can still get points for the one that we solved .
    Sunday, April 22, 2007 11:01 AM
  • And one more thing, i have observed that some of the questions also have the use of vectors and lists  which i really great  Not many of them know about vectors, list, queues, stack, etc etc .
    So i think they have set the questions such so that people who dont know these aspects, can learn it, which is really useful when you go into the corporate world.
    Sunday, April 22, 2007 11:06 AM
  • Yes...

    I faced same problem.

    One of my two questions was using List Concept...

    Sunday, April 22, 2007 1:47 PM
  • hey man, lists are very easy,. If you have time for the question, then please refer to
    http://www.cppreference.com/cpplist/index.html
    http://www.cppreference.com/cppvector/index.html

    They are really nice, and easy to program, it will ease your programming a lot. Hope you like it.
    Sunday, April 22, 2007 2:39 PM
  • Hey dear...

    I have already completed my quiz on first day (yesterday).

    I did the solution of that problem successfully.

    but I think, that can be hard for some people who are new to programming.

     

    by the way, thanks for suggestion.

    Sunday, April 22, 2007 5:02 PM
  • this will be better if u discuss after 22 april
    Sunday, April 22, 2007 8:52 PM
  • Here, I Post my quiz questions....
    I was able to solve the 1st one in the time limit but was not able to solve the other one... here goes the 1st one..

    Question 1

    There is a matrix with 9 rows and 9 columns. Each cell of the matrix is either black or white. With a single repaint operation, you can repaint all the cells in a single row or column black if the row or column already contains at least 5 black cells. Your goal is to make all the cells in the matrix black using a minimal number of repaint operations.

    You will be given a matrix array, where the jth character of the ith element represents the cell at row i, column j. Black cells will be written as '1' (one), and white cells will be written as '0' (zero). You have to return the minimal number of repaint operations required to make all the cells black, or -1 if this is impossible.

    Constraints

    ·  Each element of matrix will contain exactly 9 characters.

    ·  Each element of matrix will consist of '0' and '1' characters only.

    Example 1:
    Input:
                {"001111111",
                 "011111111",
                 "011111111",
                 "011111111",
                 "011111111",
                 "101111111",
                 "101111111",
                 "101111111",
                 "101111111"}

    Output: Returns 3
    Move 1: Repaint the first row.
    Move 2: Repaint the first column.
    Move 3: Repaint the second column.

    Example 2:
    Input:
                {"011111111",
                 "101111111",
                 "110111111",
                 "111011111",
                 "111101111",
                 "111110111",
                 "111111011",
                 "111111101",
                 "111111110"}

    Output: Returns 9
    Each white cell must be repainted separately.


    Monday, April 23, 2007 3:23 AM
  • Question 2

     

    You are given a 2*2 matrix and each row and column are associated with a positive integer value. You are required to write a program to determine four integers r1,r2,c1 and c2 which satisfy the following criteria for magic multiplication. The product of of r1 to c1 is same as the number associated with fist row, first column, product of r1 and c2 is same as the number present in first row, second column, product of r2 with c1 is same as the number present in second row, first column of the matrix and finally the product of r2 with c2 is same as the number present in the second row, second column of the matrix.


    The method used in this program is getMagicMultiplication which uses integer array 2*2 as input and returns a set of numbers that satisfy the criteria for magic multiplication.

    Constraints:

    ·  Return one solution which will be the best suited.

    ·  The output should be returned as {r1, r2, c1, c2}.

    Example 1:
    Input

    72

    132

    48

    88


    Output
         Returns {12,8,6,11}.

     

    6

    11

    12

    72

    132

    8

    48

    88

    In the above 2 * 2 matrix the values {72, 132, 48, 88} can be obtained by doing a magic multiplication as 12 * 6 = 72, 12 * 11 = 132, 8 * 6 = 48, 8 * 11 = 88. Therefore the values returned as output will be {12,8,6,11}.

    Example 2:
    Input

    25

    50

    75

    150


    Output
         Returns {5,15,5,10}.

     

    5

    10

    5

    25

    50

    15

    75

    150

    Monday, April 23, 2007 3:24 AM
  • Now I have the answer to the 1st question which works perfectly... but the problem is in the 2nd question.. can someone help me out in the 2nd question ???
    As i didnt had enough time left, i was not able to solve it,, but even now i m not able to get the logic that i should use to get the solution..
    Monday, April 23, 2007 3:28 AM
  •  Harshil_Patel_03b5f2 wrote:
    NameList
    There are two sections for grade 4 students and when moving to grade 5, the school management decided to merge them all into single section. You are required to write a program to merge students from both the sections in such a way that they are sorted in ascending order. Assume that no student names are repeated.

    This program uses a unique method getSortedNames. The method getSortedNames is unique because the data type it uses as input parameter is "vector names1, vector names2". The output of this method is again a vector which contains names in both names 1 set as well as names2 set arranged in ascending order.

    IMP: Remember to include header file #include <vector> for vector.

    Example 1:
    Input:
    names1[] = {"Aakash","Rohit","Babu"};
    names2[] = {"Uma","Vikram","Surya"}

    Output: Returns {"Aakash", "Babu", "Rohit", "Surya", "Uma", "Vikram"}

    Explanation: The method getSortedNames merges both the vectors in to a single vector as well arranges them in ascending order.

    Example 2:
    Input:
    names1[] = {"Clark","Harris","Smith","Davis","King","Adams","Campbell","Mitchell","Jackson"};
    names2[] = {"Barbara","Donald","Betty","Taylor","Anderson"}

    Output: Returns {"Adams", "Anderson", "Barbara", "Betty", "Campbell", "Clark", "Davis", "Donald", "Harris", "Jackson" , "King", "Mitchell", "Smith", "Taylor"}

    For C solutions
    Header File : NameList.h
    Function Name : vector<string> getSortedNames(vector<string> names1, vector<string> names2)
    Directory Name : namelist
    File Name : NameList.c
    For C++ solutions
    Header File : NameList.h
    Class Name : list
    Function Name : vector<string> getSortedNames()
    Directory Name : namelist
    FileName : NameList.cpp


    #include"NameList.h"
    #include<iostream>

    vector<string> list::getSortedNames() {
        vector<string> sortedstring;
        sortedstring.assign(names1.begin(), names1.end());
        sortedstring.insert(sortedstring.end(), names2.begin(), names2.end());
        sort(sortedstring.begin(), sortedstring.end());
        return sortedstring;
    }
    void dsmain() {
        list l1;
        l1.names1.push_back("Aakash");
        l1.names1.push_back("Rohit");
        l1.names1.push_back("Babu");
        l1.names2.push_back("Uma");
        l1.names2.push_back("Vikram");
        l1.names2.push_back("Surya") ;
        vector<string> sortedstring;
        sortedstring = l1.getSortedNames();
        vector<string>::iterator it;
        cout<<"Sorted List "<<endl;
        sort(sortedstring.begin(), sortedstring.end());
        for(it = sortedstring.begin() ; it != sortedstring.end() ; it++) {
            cout << *it << endl;
        }

    }


    Monday, April 23, 2007 9:43 AM
  •  Harshil_Patel_03b5f2 wrote:
    Write a program to pick out squarefree numbers from a given set of numbers. The criteria for a squarefree number is that it should not be a square value of its divisors and also its divisor should not be a sqaure value of its divisors. For example, 10 is square-free but 18 is not, as it is divisible by 9 = 32 .

    There are two methods used in this program and they are getNoOfSquareFreeNumbers and getSquareFreeNumbers. The method getNoOfSquareFreeNumbers uses a range of integer values and returns a single integer value which is the count of square free numbers present. The second method getSquareFreeNumbers returns all the numbers that satisfy the criteria for sqare free number.


    Example 1:
    Input
    from = 1
    to = 10
    Output
    Function getNoOfSquareFreeNumbers return : 7
    Function getSquareFreeNumbers returns : {1,2,3,5,6,7,10}

    Explanation:In this example the input range of numbers is from 1 to 10. The numbers that are missing in the output are {4,8 and 9}. If we consider the integer 4 we can see that the divisor 2 when squared will result in 4. So it is not a sqarefree number. The same goes for 8 and 9.

    Example 2:
    Input
    from = 4383
    to = 4400
    Output
    Function getNoOfSquareFreeNumbers return : 11
    Function getSquareFreeNumbers returns : {4385, 4386, 4387, 4389, 4390, 4391, 4393, 4395, 4397, 4398, 4399}

    For C solutions
    Header File : SquareFreeNumbers.h
    Function Name : int getNoOfSquareFreeNumbers(int from, int to), int* getSquareFreeNumbers(int from, int to)
    Directory Name : squarefreenumbers
    File Name : SquareFreeNumbers.c
    For C++ solutions
    Header File : SquareFreeNumbers.h
    Class Name : SquareFree
    Function Name : int getNoOfSquareFreeNumbers(int from, int to), int* getSquareFreeNumbers(int from, int to)
    Directory Name : squarefreenumbers
    FileName : SquareFreeNumbers.cpp




    #include"SquareFreeNumbers.h"
    #include<stdio.h>
    #include<conio.h>
    #include<stdlib.h>
    int isPerfectSquare(int);
    int isSquareFree(int);

    int isSquareFree(int no) {
        int j=0;
        for(j=2 ; j<=no ; j++) {
            if(no%j==0) { // factor
                if(isPerfectSquare(j)) { //Not square free
                    return 0;
                }
            }
        }
        return no;
    }
    int getNoOfSquareFreeNumbers(int from, int to) {
        int i=0,j=0, cnt=0, flag=0;
        for(flag=0, i=from ; i<=to ; i++) {
            if(isSquareFree(i)) {
                cnt++;
            }
        }
        return cnt;
    }
    int* getSquareFreeNumbers(int from, int to) {
        int *arr;
        int i, cnt=0;
        arr = (int *)malloc(sizeof(int) * (getNoOfSquareFreeNumbers(from, to)));
        for(i=from ; i<=to ; i++) {
            if(isSquareFree(i)) {
                arr[cnt++]=i;
            }
        }
        return arr;

    }

    int isPerfectSquare(int n) {
        int i=1;
        while( (i*i) != n) {
            if((i*i) >= n) {
                return 0;
            }
            i++;
        }
        return i;

    }
    void dsmain() {

        int n,from=4383, to=4400, i, *arr;
            from=1, to=10;
        n=getNoOfSquareFreeNumbers(from, to);
        arr = getSquareFreeNumbers(from, to);
        printf("Total No of Square Free Numbers : %d\n",n);
        printf("The square free numbers are :\n");
        for(i=0 ; i<n ; i++) {
            printf("%d ",arrIdea);
        }
    }

    Monday, April 23, 2007 9:43 AM
  •  Varun_Modi_a59ed9 wrote:
    Now I have the answer to the 1st question which works perfectly... but the problem is in the 2nd question.. can someone help me out in the 2nd question ???
    As i didnt had enough time left, i was not able to solve it,, but even now i m not able to get the logic that i should use to get the solution..


    Sorry m8 my friend also got one of those question, it was a hard one, i still cant find out the logic of it Sad
    Monday, April 23, 2007 9:45 AM
  • Block Counting
    Mantri builders have recently acquired a huge piece of land and they plan to sell blocks of land within that piece. You need to write a program to determine how many blocks of land are available in that piece. Consider this piece of land as a (x,y) graph in two dimensional space. If you have difficulty in imagining this, please refer to the graph provided in the example section below. The method countBlock uses two parameters as input and they are integer n, which is number of co ordinates in the graph and integer array coordinates, which is an array of 1*2.

    Constraints:
    # The number of coordinates should be a positive integer
    # The coordinate points in x and y quadrant should be a positive integer
    # The maximum number of coordinates n that can be given as input value should not exceed 100
    # The maximum number of coordinate combinations which is a 1*2 array that can be given as input value should not exceed 100 x*y points


    Example 1:
    Input
    int n = 6
    int coordinates[][2] = { {1,1}, {1,5}, {5,3}, {5,5}, {7,1}, {7,3} }.
         Click Here to view the example.

    Output Returns : 20
    Explanation: Count all the blocks inside the given coordinate values { {1,1}, {1,5}, {5,3}, {5,5}, {7,1}, {7,3} }. Hence the total number of blocks are 20.

    Example 2:
    Input
    int n = 8
    int coordinates[][2] = { {1,1}, {1,5}, {3,2}, {3,5}, {5,2}, {5,5}, {7,1}, {7,5} }.
    Output Returns : 18

    For C solutions
    Header File    :    BlockCounting.h
    Function Name    :    int countBlock(int n, int coordinates[][2]
    Directory Name    :    blockcounting
    File Name    :    BlockCounting.c
    For C++ solutions
    Header File    :    BlockCounting.h
    Class Name    :    block
    Function Name    :    int countBlock(int n, int coordinates[][2]
    Directory Name    :    blockcounting
    FileName    :    BlockCounting.cpp
    Monday, April 23, 2007 9:46 AM
  • In a class the students were asked to find the number of Upper and Lower case characters in a given sentence. Help the students by writing a program to find the number of Upper and Lower case characters in a sentence. The methods countUpperChar and countLowerChar holds one parameter called sentence. The functions returns the number of corresponding characters.
    Example 1:
    Input : char* sentence = {"DevSquare is an ONLINE development platform"}

    Output : Returns from method countUpperChar : 8
    Output : Returns from method countLowerChar : 30

    Example 2:
    Input : char* sentence = {"In English, CAPITAL letters are used as the first letter of a sentence or a PROPER NOUN and for INITIALS or ACRONYMS"}

    Output : Returns from method countUpperChar : 35
    Output : Returns from method countLowerChar : 59

    For C solutions
    Header File    :    UpperLower.h
    Function Name    :    int countUpperChar(char* sentence), int countLowerChar(char* sentence)
    Directory Name    :    UpperLower
    File Name    :    UpperLower.c
    For C++ solutions
    Header File    :    UpperLower.h
    Class Name    :    UpperLower
    Function Name    :    int countUpperChar(char* sentence), int countLowerChar(char* sentence)
    Directory Name    :    UpperLower
    FileName    :    UpperLower.cpp
    Monday, April 23, 2007 9:46 AM
  • Write a program to determine abundant numbers from a set of numbers. The criteria for a number to be an abundant number is that the divisors of that number when added should be greater than the product of that number with 2. As an example, consider the number 24. Its divisors are 1, 2, 3, 4, 6, 8, 12 and 24, whose sum is 60. Because 60 is more than 2 * 24, the number 24 is abundant.

    There are two methods used in this program and they are getNoAbundantNumbers and getAbundantNumbers. The method getNoAbundantNumbers uses a range of numbers as input value and returns a single integer value which is number of abundant numbers present in that range. The method getAbundantNumbers uses a range of numbers as input value and returns a set of numbers that satisfy the criteria for abundant numbers.

    Constraint:
    # The input value should be a non-zero positive integer and the range cannot exceed 10000.

    Example 1:
    Input:
             int from = 1
             int to = 50
    Output:
             Function getNoAbundantNumbers returns : 9
             Function getAbundantNumbers returns : {12, 18, 20, 24, 30, 36, 40, 42, 48}

    Explanation: The range of numbers is 1 to 50 and the method getNoAbundantNumbers returns 9 i.e there are 9 abundant numbers within that range which satisfy the criteria for abundant number. The method getAbundantNumbers returns all the numbers within that range which satisfy the criteria for abundant number and they are {12,18,20,24,30,36,40,42,48}. Consider integer 12 and the divisors for this numbers are 1,2,3,4,6,12. This number is a abundant number because after adding the divisors the resultant number is 28. Now the product of 12*2 is 24 which is less than the sum of its divisors. So this number is labelled abundant number.

    Example 2:
    Input:
             int from = 7567
             int to = 7600
    Output:
             Function getNoAbundantNumbers returns : 10
             Function getAbundantNumbers returns : {7568, 7572, 7578, 7580, 7584, 7588, 7590, 7592, 7596, 7600}

    For C solutions
    Header File    :    AbundantNumber.h
    Function Name    :    int getNoAbundantNumbers(int from, int to)&nbspint* getAbundantNumbers(int from, int to)
    Directory Name    :    abundantnumber
    File Name    :    AbundantNumber.c
    For C++ solutions
    Header File    :    AbundantNumber.h
    Class Name    :    AbundantNumber
    Function Name    :    int getNoAbundantNumbers(int from, int to)&nbspint* getAbundantNumbers(int from, int to)
    Directory Name    :    abundantnumber
    FileName    :    AbundantNumber.cpp
    Monday, April 23, 2007 9:46 AM
  • Gowthaman lives in Bangalore. His house is situated near a very busy large bus stop. But Gowthaman is tired of the traffic jams in the city so he wants to know the way to go from any place in the city to any other place with least number of buses traveled on. He goes to the bus stop and asks a bus conductor about his problem. But the conductor is an irritable chap and refuses to help him. After a lot of pestering he gives in to Gowthaman, but he does a weird trick: He only gives Gowthaman a schedule with a lot of tuples as follows:
    BUS NO,NODE 1,NODE 2

    The conductor also repeats the same tuple a lot of times for confusion. Gowthaman's task now is to go through the list and find out how many buses will be needed to travel from one point to another.

    Constraints:

        * Ignore the time of travel, start time and end time.
        * A bus with a specified bus number corresponds to one and only one path which can have multiple intermediate nodes. eg: Bus no 100 can have a path A-B-C-D-E but no other path in the city.
        * The input given will have no unreachable path conditions.
        * The bus number will be an integer, the node names are letters from the alphabet (A to Z).

    Example 1:
    Input
        int n = 11;
        int busNo[] = {100,100,101,102,101,102,103,104,105,105,105};
        char node1[] = {'A','B','A','D','A','D','D','B','E','E','E'};
        char node2[] = {'B','C','D','C','D','C','E','F','F','F','F'};
        char from = 'A';
        char to = 'F';

    Output: Returns 2.
    Explanation : As he needs to travel in two buses 100 that goes from A -> B and 104 that goes from B -> F from the starting to the destination place.

    For C solutions
    Header File    :    Buses.h
    Function Name    :    int getBuses(int n, int busNo[], char node1[], char node2[], char from, char to)
    Directory Name    :    busroute
    File Name    :    busroute.c
    For C++ solutions
    Header File    :    Buses.h
    Class Name    :    bus
    Function Name    :    int getBuses(int n, int busNo[], char node1[], char node2[], char from, char to)
    Directory Name    :    busroute
    FileName    :    busroute.cpp

    Monday, April 23, 2007 9:47 AM
  • There have been a lot of hard questions in the quiz this month. I think the next quiz will be even more harder, the level of toughness is increasing guys, do more practice.

    Any one of you guys got /  solved to the questions that i posted in the earlier post ? please post the solutions.
    Monday, April 23, 2007 9:49 AM
  • ya ur right
    Monday, April 23, 2007 11:16 AM
  • Question 1

    There is a matrix with 9 rows and 9 columns. Each cell of the matrix is either black or white. With a single repaint operation, you can repaint all the cells in a single row or column black if the row or column already contains at least 5 black cells. Your goal is to make all the cells in the matrix black using a minimal number of repaint operations.

    You will be given a matrix array, where the jth character of the ith element represents the cell at row i, column j. Black cells will be written as '1' (one), and white cells will be written as '0' (zero). You have to return the minimal number of repaint operations required to make all the cells black, or -1 if this is impossible.

    Constraints

    · Each element of matrix will contain exactly 9 characters.

    · Each element of matrix will consist of '0' and '1' characters only.

    Example 1:
    Input:
    {"001111111",
    "011111111",
    "011111111",
    "011111111",
    "011111111",
    "101111111",
    "101111111",
    "101111111",
    "101111111"}

    Output: Returns 3
    Move 1: Repaint the first row.
    Move 2: Repaint the first column.
    Move 3: Repaint the second column.

    Example 2:
    Input:
    {"011111111",
    "101111111",
    "110111111",
    "111011111",
    "111101111",
    "111110111",
    "111111011",
    "111111101",
    "111111110"}

    Output: Returns 9
    Each white cell must be repainted separately.

    Code Snippet

    Solution :

    #include<iostream.h>

    #include<conio.h>

    class repaint

    {

    public :

    int matrix[9][9];

    int MatrixRepaint();

    };

    #define row 0

    #define column 1

    int repaint::MatrixRepaint()

    {

    int CalculateBlack(int matrix[9][9], int *row_or_column, int *row_or_column_no);

    int count = 0;

    int row_or_column, row_or_column_no, i , j;

    // While We find a valid row or column to repaint...

    while(CalculateBlack(matrix, &row_or_column, &row_or_column_no))

    {

    count++;

    int tmp;

    if(row_or_column == row)

    {

    for(i = 0; i<9; i++)

    matrix[row_or_column_no][i] = 1;

    }

    else

    {

    for(i = 0; i<9; i++)

    matrix[i][row_or_column_no] = 1;

    }

    }

    int flag= 1;

    for(i=0;i<9;i++)

    for(j=0;j<9;j++)

    {

    if(matrix[i][j] != 1)

    flag = 0;

    }

    if(flag)

    return count;

    else

    return -1;

    }

    int CalculateBlack(int matrix[9][9], int *row_or_column, int *row_or_column_no)

    {

    // flag = 0;

    int i, j;

    int no_of_black[2][9] = {0};

    // Calculating the Number of Black Blocks in Each Row & column

    for(i=0; i<9; i++)

    for(j=0; j<9; j++)

    {

    if(matrix[i][j] == 1)

    {

    no_of_black[row][i]++;

    no_of_black[column][j]++;

    }

    }

    int min = 9;

    // Calculating the Row or Column With Minimum No. of Black Blocks But with atleast 5

    // Black Blocks...

    for(i=0;i<2; i++)

    for(j=0; j<9; j++)

    {

    if(no_of_black[i][j] < min && no_of_black[i][j] >= 5)

    {

    min = no_of_black[i][j];

    *row_or_column = i;

    *row_or_column_no = j;

    }

    }

    // If we find a valid row or column to repaint we return 1 or else 0

    if(min != 9)

    return 1;

    else

    return 0;

    }

    void copy( int matrix1[9][9], char matrix2[9][10])

    {

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

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

    {

    if(matrix2[i][j] == '1')

    matrix1[i][j] = 1;

    else

    matrix1[i][j] = 0;

    }

    }

    void main()

    {

    repaint b1;

    char tmp[9][10] = {"001111111",

    "011111111",

    "011111111",

    "011111111",

    "011111111",

    "101111111",

    "101111111",

    "101111111",

    "101111111"};

    copy(b1.matrix, tmp);

    cout<<b1.MatrixRepaint();

    }


    Monday, April 23, 2007 2:54 PM
  • Now for the second question

    Input

    72

    132

    48

    88


    Output
         Returns {12,8,6,11}.

     

    6

    11

    12

    72

    132

    8

    48

    88

    In the above 2 * 2 matrix the values {72, 132, 48, 88} can be obtained by doing a magic multiplication as 12 * 6 = 72, 12 * 11 = 132, 8 * 6 = 48, 8 * 11 = 88. Therefore the values returned as output will be {12,8,6,11}.

    Example 2:
    Input

    25

    50

    75

    150


    Output
         Returns {5,15,5,10}.

     

    5

    10

    5

    25

    50

    15

    75

    150



    -------------------------------------------------------------------------------

    I m not getting the logic to use to solve it... I tried finding out the Greatest Common divisors of the related numbers, but it didnt work.. can someone help me out here.. I really want to solve it....
    Monday, April 23, 2007 3:05 PM
  • @Varun i think you need to do a brute force with the common factors found for each element in the matrix. I still cant find out the logic how to get the solution for it. I also want to solve it......
    Monday, April 23, 2007 3:19 PM
  • Hey... really, this pro is too hard to solve.

    and also multiple output is there..

     

    for input :

    72       132

    48       88

     

    Output 1:

     

              6        11

    ---------------------

    12     72      132

    8       48      88

     

    Output 2:

     

           12      22

    --------------------

    6     72      132

    4     48      88

     

    and so on...

    Monday, April 23, 2007 5:54 PM
  • Nice observation buddy.. i didnt thought of it before... now what can we do to solve it... well i was 1st thinking of getting the gcd first, but looks like i will have to modify that strategy or if someone can add to this ???
    Monday, April 23, 2007 6:53 PM
  • Alright people, finally i hv cracked the problem.. I have derived the solution, and its so easy...
    Does anyone wants to have the solution??? Now the solution is simple, but try it urself first.. If you are not able to do it, i will post the answer here... I will wait for 3 people to ask for the answer here, than i will post the answer...

    Harshil will also get a good response to this thread, after all it was his idea to start this thread and where we all met
    Monday, April 23, 2007 7:14 PM
  • Hey varun,

     

    I tried it, but my program is giving right answer but not same as example… as I explained before.

    Multiple outputs are possible in this problem.

     

    Is your program giving exact output?

     

    If yes, I definitely like to see it.

     

    Tuesday, April 24, 2007 8:22 AM
  • Thanks @Varun , and first of all congratulations for solving the problem finally. As i am having exams, i didn't try solving the question, but i tried a to to find out the logic of the problem, for which i failed.  I think i am the 2nd person who is requesting for the solution to that problem. Waiting for one more chap to request, so that we all get have a look at the code, and also if you dint mind, explain the logic first. and then post the solution.
    Tuesday, April 24, 2007 9:36 AM
  • When, you said about the multiple answers exist, I got a way to find a valid answer....
    Though my code same output for the 1st example, for 2nd one it gives a different but a valid answer to the example... this can be extended to any question and it will give a valid answer if it exists...

    Will surely like to know what logic you used for your code
    Tuesday, April 24, 2007 11:22 AM
  • Ya guys, post the logic Smile its becoming harder to wait Smile
    Tuesday, April 24, 2007 12:51 PM
  • Okkk..
    So here comes the million dollar answer...

    1st the code.... looking at the code you should be able to understand the logic.. if still its not clear than i will try to explain it.. i will also appreciate other memebers to post their code for this problem...



    Code Snippet


    #include<stdio.h>
    #include<iostream.h>

    int gcd(int x, int y)
    {
        if(y==0)
            return (x);
        else
            return(gcd(y, x%y));



    int* getMagicMultiplication(int matrix[2][2])
    {
         int *ans;
         ans = new int[4];
         ans[0] =   gcd(matrix[0][0], matrix[0][1]);

         ans[2] = matrix[0][0] / ans[0];
         ans[1] = matrix[1][0] / ans[2];
         ans[3] = matrix[1][1] / ans[1];
         return (ans);
    }

    void main()
    {
        int matrix[2][2];
        int *ans, i;
        matrix[0][0] = 72;
        matrix[0][1] =132;
        matrix[1][0] =48;
        matrix[1][1] =88;
        ans = getMagicMultiplication(matrix);
        for(i=0;i<4;i++)
            printf("%d ",ans[i]);
    }


    Tuesday, April 24, 2007 4:31 PM
  • I did this program in C...

    and I didn't use gcd function.

    I got factors manually.

    so, it got somewhat lengthy..

    logic is almost same.

    Tuesday, April 24, 2007 5:33 PM
  • this program was originally written in C only.. its just i was doing some test so had included iostream.h but you can exclude it n run the same code in c.. it will run fine...
    GCD function is also written by me only.. just to make things look simpler i made it as a function, but still don know if this would work, because the prog gives a valid output, but not same as given by them for the 2nd example.. it differs... don know what logic they are using...
    Tuesday, April 24, 2007 6:10 PM
  • yaa.. I know that ur most of code is of C language and anyone can understand it...

    but you have included <iostream.h>

    that's y I cleared it....

     

    and I m telling that I haven't created any function, so my coding is lengthy.

    I know that you have created and used GCD function (by U only....)

     

    and I had already told you that program may give different but correct output. 

     

     

    Tuesday, April 24, 2007 6:31 PM
  • Hey buddy, I was not taunting or anything like that... Its nothing like that.. i m sorry if u felt so.. i was just highlighting the points of my code.. 
    Can you post your code also???
    Wednesday, April 25, 2007 3:11 AM
  • It's ok dear..

    I don't like to post my code here.. because your code is better than me.

    My coding is very larger.

    because I applied lengthy method (loop instead of recursive function) to find GCD.

    and other logic is same..

    that's y....

     

    Wednesday, April 25, 2007 9:08 AM
  • First of all thanks varun for posting the code. I now finally have understood the logic Smile after seeing the code, the logic seems to look like a piece of cake Stick out tongue why the hell we wasn't able to solve such an easy question Stick out tongue hehe

    And one more thing i have to point ut guys. Please dont fight, we need to create a good and healthy community here Smile
    Wednesday, April 25, 2007 10:28 AM
  • thnks varun. ... nice posts.... .!!. .
    Wednesday, April 25, 2007 6:02 PM
  • @ harshil

    u r right  dude.....

     

    v should not fight here,...we are the members ..

    if we won't unite then Admins will  take the advantage of this 

    Wednesday, April 25, 2007 7:17 PM
  • Hey people no one is fighting over here... please dont take it this way..

    Now, both of my problems are solved.. Now we can jump to someone else's problem which is still unsolved.. But please one at a time.. can we have the next problem???

    If there is no one else with any unsolved problems than i have a classic problem which is still unsolved... I dont have the exact question, but remmber what the question was.. it was of the shortest route from location [0,0] to [R,C] in a RxC Matrix, where each block has some Natural value and the summation of the blocks that comes under this route is smallest...
    Thursday, April 26, 2007 2:59 AM
  • Dear Friend,

     

    Can't you provide answers for some more questions like this. If time permits kindly do so. Then we all will be benefitted.

     

    Regards

    Thursday, April 26, 2007 9:18 AM
  • Thanks for the post buddy !
    Thursday, April 26, 2007 1:01 PM
  • Maze

    You are in a maze which resembles a matrix and has r rows and c columns. A positive integer number is associated with each row and column in this matrix. Please refer image in Example 1.

    Write a program to generate shortest path from (0x0) point in the maze to (rxc) point. The condition for shortness is defined by the end summation of all the numbers in that path and this number should be the least of all other paths. The method mazeMove uses positive integer r, positive integer c and integer array (rxc) as input parameters. The output of this method will compare all the summation from (0x0) point to (rxc) point and returns the least of these summations.

    Constraints:


    The number of rows and columns should not exceed 20x20
    The maximum value for each row and column cannot exceed 100
    Assume that there will be only one smallest path.

    Example 1:
    Input
    int r = 6
    int c = 5
    int values[][20] = { { 5, 6, 7, 10, 13 },
                               { 2, 4, 1, 15, 10 },
                               { 15, 3, 1, 2, 10 },
                               { 23, 15, 12, 3, 14 },
                               { 1, 9, 8, 6, 21 },
                               { 11, 10, 3, 3, 4 } };

         Click Here to view the example.

    Output Returns : 31
    Explanation: Add all the values from (0,0) to (6,5) with the path mentioned in example image which will be the smallest path with the summation of 31. Hence 31 is returned from the function.

    Example 2:
    Input
    int r = 4
    int c = 6
    int values[][20] = { { 5, 6, 7, 10, 11, 3},
                               {2, 10, 5, 6, 1, 10},
                               {1, 2, 12, 5, 6, 1},
                               {3, 1, 6, 2, 21, 13 } };

    Output Returns : 44

    For C solutions  
    Header File : Maze.h
    Function Name : int mazeMove( int r, int c, int values[][20])
    Directory Name : maze
    File Name : Maze.c
    For C++ solutions  
    Header File : Maze.h
    Class Name : maze
    Function Name : int mazeMove( int r, int c, int values[][20])
    Directory Name : maze
    FileName : Maze.cpp

    Friday, April 27, 2007 12:39 PM
  • @Varun, i have posted the question to that maze problem that you was requesting Sad It was also a hard one, i cant find out the solution to it. Also one more problem is there about the BUS ROUTE, i will post that later, after we have done discussions on this MAZE problem.
    Friday, April 27, 2007 12:41 PM
  • Thankz for the problem.. can you also post the link to the image where answer is given, so that it becomes easy to work with the answer...

    Now one of the method i thought of was "Greedy Approach", i.e. we start with the block (0,0) and select the adjacent box which has the least value, i.e. having a greedy approach to it.. that way we will stop when we reach the end block(r,c)...

    Now this solution does have some problems as it wont give the correct answer all the time.... but its a better choice... what do you guys have to say about it???
    Friday, April 27, 2007 2:13 PM
  • Sure m8, let me try finding the image to that maze problem. I also think that the greedy approach can be used. The problem is that it will become to complex Stick out tongue
    Friday, April 27, 2007 4:01 PM
  • OK here is the link to the maze image.

    Friday, April 27, 2007 4:03 PM
  • Thankz for the image buddy...

    Now for the complexity, I think that accepting a greedy method wont take the complexity too high as compared to other methods.. I know of one method which is a sure short answer to the problem but it has the highest complexity,

    The method is to take into consideration all the possible rootes to reach the point and then selecting the minimum one.. but this has the highest complexity and it will be too long... there has to be a better solution to it...

    Now say how to use Greedy method in solving it?? what should be the controling points and how the process should move.... I tried the greedy method that i talked about in the 1st exmple, offcourse manually, but i can write that code... It works for the 1st one...

    But it doesnot work for the 2nd one..

    so what should we do ???
    Friday, April 27, 2007 5:50 PM

  • Write a program to generate a list of Happy Numbers from a given range of numbers. The steps to determine whether a number is a happy number or not is as follows.
    Each digit in that number is squared and summed up. This action is performed repeatedly with the resulting numbers till the summation ends up being the number 1. If this happens then the number is termed as Happy Number.
    The method used in this program is getHappyNumbers and this method uses integer range of numbers as input and the output is a list<int> of numbers that satisfies the criteria for happy numbers. The datatype for this result is list<int> and it should be mentioned while defining this method.

    Constraint:


    The input value should be a non-zero positive integer and it should not exceed 10000.
    IMP:

    Remember to include header file #include<list> for list.


    Example 1:
    Input:
             int from = 15
             int to = 50

    Output: Returns {19, 23, 28, 31, 32, 44, 49}

    Explanation: There are 7 numbers with range from 15 to 50. First happy number is 19 and let us take the number 19 for explanation. As per the description let us square 1 and 9 and add them(12 + 92). The result is 82. Now repeating the previous step again for this number 82. The result is 68. Again repeating the first step and the result is 100. Now performaing the step one again on this number resluts in 1. So this number 19 is a Happy Number.

    Example 2:
    Input:
             int from = 1101
             int to = 1175

    Output: Returns {1112, 1114, 1115, 1121, 1122, 1125, 1128, 1141, 1148, 1151, 1152, 1158}

    For C solutions 
    Header File : HappyNumbers.h
    Function Name : list<int> getHappyNumbers(int from, int to)
    Directory Name : happynumbers
    File Name : HappyNumbers.c
    For C++ solutions 
    Header File : HappyNumbers.h
    Class Name : happy
    Function Name : list<int> getHappyNumbers(int from, int to)
    Directory Name : happynumbers
    FileName : HappyNumbers.cpp


    General Instructions:     * The directory , file / class names, functions, method signatures, header files to be used are mentioned in the problem statement. Do not use your own names or change the method signatures and fields. You can add any number of additional methods.
     
        * First add the directory in the Main Program Directory and then add the particular file in that directory. Do not forget to mention the file extension, either .c or .cpp as the case maybe.
     
        * For C solutions, change the value of "C_OR_CPP" macro in header file as 1 and for C++ solutions change the value as 2.
     
        * Incase of iostream.h specify as iostream only. 


    #include<conio.h>
    #include<iostream>
    #include<list>

    using namespace std;

    list<int> getHappyNumbers(int from, int to)
    {
         list<int> happyNumbers = list<int>();
         list<int> temp;
         list<int>::iterator it;
        
         int ctr, number, sum, digit, ctr2, flag;
        
         if(from <= 0 || to <= 0)
         {
              cout<<"Invalid numbers as numbers should be > 0.";
              return happyNumbers;
         }
        
         if(to < from)
         {
              cout<<"Range improper. Value of parameter \'to\' should be ";
              cout<<"greater than \'from\' parameter.";
              return happyNumbers;
         }
        
         if(to > 10000)
         {
              cout<<"Max possible number is 10000. Range should not exceed that.";
              return happyNumbers;
         }
        
         for(ctr = from ; ctr <= to ; ctr++)
         {   
              number = ctr;
              ctr2 = 0;
              flag = 1;
              temp = list<int>();
             
              flag = 1;
             
              while(flag == 1)
              {
                  sum = 0;

                  while(number != 0)
                  {
                       digit = number % 10;
                       number = number / 10;
                       sum += (digit * digit);
                  }
                 
                  if(sum == 1)
                  {
                       happyNumbers.push_back(ctr);
                       flag = 0;
                       break;
                  }
                  else
                  {
                       for(it = temp.begin() ; it != temp.end() ; it++)
                       {
                              if(*it == sum)
                              {
                                     flag = 0;
                                     break;
                              }
                       }
                       temp.push_back(sum);
                       number = sum;
                  }
              }
         }
        
         return happyNumbers;
    }

    int main(void)
    {
         list<int> result;
         list<int>::iterator it;
        
         cout<<"\n\nHappy numbers between 15 and 50 : ";    
         cout<<"\n-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=\n";    
         result = getHappyNumbers(15, 50);
         for(it = result.begin() ; it != result.end() ; it++)
         {
                cout<<" "<<*it;
         }

         cout<<"\n\nHappy numbers between 1101 and 1175 : ";    
         cout<<"\n-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=\n";    
         result = getHappyNumbers(1101, 1175);
         for(it = result.begin() ; it != result.end() ; it++)
         {
                cout<<" "<<*it;
         }

         cout<<"\n\nHappy numbers between 15 and 10 : ";    
         cout<<"\n-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=\n";    
         result = getHappyNumbers(15, 10);
         for(it = result.begin() ; it != result.end() ; it++)
         {
                cout<<" "<<*it;
         }

         cout<<"\n\nHappy numbers between -15 and -10 : ";    
         cout<<"\n-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=\n";    
         result = getHappyNumbers(-15, -10);
         for(it = result.begin() ; it != result.end() ; it++)
         {
                cout<<" "<<*it;
         }

         cout<<"\n\nHappy numbers between 1000 and 10001 : ";    
         cout<<"\n-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-\n";    
         result = getHappyNumbers(1000, 10001);
         for(it = result.begin() ; it != result.end() ; it++)
         {
                cout<<*it<<"  ";
         }

         getch();    
    }


    Friday, April 27, 2007 5:58 PM
  • Thanks sanket for the Happy Numbers problem  Smile

    and varun, on the first look the problem seems simple, but when we try to implement it we get stuck. the main problem i faced was how to make the computer know in which direction to go. Now to make it easy, suppose we assume that we want to ONLY move in right down direction, but then when i tried implementing my program got stuck in a loop cause when it shifted the control to another box in the maze image, it found out that the earlier box which we came from was the minimum, and hence it tried shifting the control to there Sad so i guess we will have to keep track of what all places we visited, and if have already visited a place, then find the next minimum.
    Friday, April 27, 2007 6:09 PM

  • Write a program to find out the relationship between you and your partner. Your program must select one among these relationship (Friend, Love, Affection, Marriage, Enemy or Sister). The program must take two names as input eliminate the similar alphabets in both the words and count the remaining number of alphabets and calculate the corresponding relationship. As we must have heard of FLAMES your program must implement the concept of flames.

    Constraints:
    Consider upper and lower case character are same.
    Names contains only alphabets.
    If both names are same return as FRIEND.

    Example 1:
    Input
    k1[]= "Fernando Gonzalez"
    k2[]= "Roger Federer"
    Output
    Returns MARRIAGE.
    Consider the word FLAMES where F-Friend, L-Love, A-Affection, M-Marriage, E-Enemy, S-Sister. Here in the above example by eliminating the similar alphabets we get a total count of 14 (nanonzalzRerer) by combining both the words so the count starts from F in the FLAMES and it continues till it reaches the 14th character in the word FLAMES. The letter L gets eliminated in the first count and S,E,A,F in similar fashion and the remaining letter which is left out is to be returned as the output. Therefore the left out letter M - MARRIAGE is returned as output.

    Example 2:
    Input
    k1[]= "White"
    k2[]= "Davis"
    Output
    Returns AFFECTION.

    Example 3:
    Input
    k1[]= "Hernandez"
    k2[]= "Martinez"
    Output
    Returns ENEMY.

    For C solutions
    Header File : MatchFinder.h
    Function Name : char* matchfinder(char k1[], char k2[])
    Directory Name : MatchFinder
    File Name : MatchFinder.c
    For C++ solutions
    Header File : MatchFinder.h
    Class Name : finder
    Function Name : char* matchfinder(char k1[], char k2[])
    Directory Name : MatchFinder
    FileName : MatchFinder.cpp


    General Instructions: * The directory , file / class names, functions, method signatures, header files to be used are mentioned in the problem statement. Do not use your own names or change the method signatures and fields. You can add any number of additional methods.

    * First add the directory in the Main Program Directory and then add the particular file in that directory. Do not forget to mention the file extension, either .c or .cpp as the case maybe.

    * For C solutions, change the value of "C_OR_CPP" macro in header file as 1 and for C++ solutions change the value as 2.

    * Incase of iostream.h specify as iostream only.


    #include<conio.h>
    #include<iostream>
    #include<ctype.h>
    #include<malloc.h>
    #include<string>

    using namespace std;

    char* matchfinder(char k1[], char k2[])
    {
    int ctr, length1, length2, totalLength, common = 0, ctr2, flag;
    int *flames = (int *)calloc(6, sizeof(int));
    int flamesLength = 6;
    int pass;
    char temp;
    int *name1, *name2;
    char flamesString[6][10] = {"Friend", "Love", "Affection", "Marriage",
    "Enemy", "Sister"};

    length1 = strlen(k1);
    name1 = (int *)calloc(length1, sizeof(int));
    length2 = strlen(k2);
    name2 = (int *)calloc(length2, sizeof(int));

    totalLength = length1 + length2;

    strlwr(k1);
    strlwr(k2);

    if(strcmp(k1, k2) == 0)
    {
    return flamesString[0];
    }

    for(ctr = 0 ; ctr < length1 ; ctr++)
    {
    if(!(isalpha(k1[ctr]) || isspace(k1[ctr])))
    {
    return "INVALID STRING.";
    }
    }

    for(ctr = 0 ; ctr < length2 ; ctr++)
    {
    if(!(isalpha(k2[ctr]) || isspace(k2[ctr])))
    {
    return "INVALID STRING.";
    }
    }

    for(ctr = 0 ; ctr < length1 ; ctr++)
    {
    flag = 1;

    for(ctr2 = 0 ; ctr2 < length2 && flag == 1; ctr2++)
    {
    if(k1[ctr] == k2[ctr2] && name2[ctr2] == 0)
    {
    name1[ctr] = name2[ctr2] = 1;
    totalLength -= 2;
    flag = 0;
    break;
    }
    }
    }

    ctr2 = 0;

    for(ctr = 0 ; ctr < 6 ; )
    {
    if(flames[ctr] == 0)
    {
    ctr2++;

    if(ctr2 == totalLength)
    {
    flames[ctr] = 1;
    flamesLength--;
    ctr2 = 0;
    }
    }

    if(flamesLength == 1)
    {
    break;
    }

    ctr++;

    if(ctr == 6)
    {
    ctr = 0;
    }
    }

    for(ctr = 0 ; ctr < 6 ; ctr++)
    {
    if(flames[ctr] == 0)
    {
    return flamesString[ctr];
    }
    }
    }

    int main(void)
    {
    char name1[20];
    char name2[20];
    char result[15];

    strcpy(name1, "Fernando Gonzalez");
    strcpy(name2, "Roger Federer");
    strcpy(result, matchfinder(name1, name2));
    cout<<result<<endl;

    strcpy(name1, "White");
    strcpy(name2, "Davis");
    strcpy(result, matchfinder(name1, name2));
    cout<<result<<endl;

    strcpy(name1, "Sanket");
    strcpy(name2, "Swati");
    strcpy(result, matchfinder(name1, name2));
    cout<<result<<endl;

    strcpy(name1, "Hernandez");
    strcpy(name2, "Martinez");
    strcpy(result, matchfinder(name1, name2));
    cout<<result<<endl;

    strcpy(name1, "Student");
    strcpy(name2, "Rockstar");
    strcpy(result, matchfinder(name1, name2));
    cout<<result<<endl;

    strcpy(name1, "Student");
    strcpy(name2, "student");
    strcpy(result, matchfinder(name1, name2));
    cout<<result<<endl;

    strcpy(name1, "Student");
    strcpy(name2, "student-");
    strcpy(result, matchfinder(name1, name2));
    cout<<result<<endl;

    getch();
    }



    Friday, April 27, 2007 6:14 PM
  • Sanket, Thanks for the FLAMES problem and solution Smile

    Can you help us try solving the MAZE problem ? it too seems to be complicated.
    Friday, April 27, 2007 6:21 PM
  • its nice solutions
    Friday, April 27, 2007 6:28 PM
  • Ya we can do that by having a parallel matrix which stores the flags for the visited blocks.. that way we can avoid going back to the same block...

    but now there is also a possibility that we end up at a dead end or like the snake game, we go on hiting at the ourself.... so need to think over there...
    Friday, April 27, 2007 6:41 PM
  • Maze problem .............solution .............

     

     

     

     

    #include <stdio.h>
    #include<alloc.h>
    #include <conio.h>


    int r = 4;
    int c = 6;
    int values[][20] = { { 5, 11, 11, 11, 11, 11},
          { 1, 11, 11, 11, 10, 11},
          { 1,  1, 11, 1 , 1 , 1 },
          { 11, 1, 1 , 1 , 10 ,1}};
    int min(int a,int b);
    int minimum(int arr[],int visited[],int n);
    int makeCostMatrix(int r,int c,int arr[20][20],int *cost[400]);
    int mazeMove(int r,int c,int values[][20]);

    int min(int a,int b)
    {
     return a<b?a:b;
    }

    int minimum(int arr[],int visited[],int n)
    {
     int small=9999,i;
     for(i=1;i<=n;i++)
     {
      if(visitedIdea==1)
       continue;
      if(arrIdea<small)
       small=arrIdea;
     }
     for(i=1;i<=n;i++)
     {
      if(visitedIdea==1)
       continue;
      if(arrIdea==small)
       return i;
     }
     return 0;
    }

    int makeCostMatrix(int r,int c,int arr[20][20],int *cost[400])
    {
     int cnt=0,i,j;
     for(i=0;i<r;i++)
     {
      for(j=0;j<c;j++)
      {
       int nodeNo = i*c+j;
       if(j+1<c)        //next in row
       {
        cost[nodeNo][nodeNo+1]=arr[nodeNo/c][(nodeNo+1)%c];
        cnt++;
       }
       if(j-1>=0)       //prev in row
       {
        cost[nodeNo][nodeNo-1]=arr[(nodeNo-1)/c][(nodeNo)%c];
        cnt++;
       }
       if(i+1<r)        //down in col
       {
        cost[nodeNo][nodeNo+c]=arr[(nodeNo+c)/c][(nodeNo)%c];
        cnt++;
       }
       if(i-1>=0)       //up in col
       {
        cost[nodeNo][nodeNo-c]=arr[(nodeNo)/c][(nodeNo-c)%c];
        cnt++;
       }
      }
     }
     return cnt/2;
    }

    int mazeMove(int r,int c,int values[][20])
    {
     int i,j,k,l[400],path[400],pl=0,visited[400]={0},v;
     int start=0,end=r*c-1,cnt=r*c-1;
     int *cost[400];
     for(i=0;i<400;i++)
      costIdea = (int*)malloc(400);
     for(i=0;i<r*c;i++)
      for(j=0;j<r*c;j++)
       costIdea[j]=9999;
     makeCostMatrix(r,c,values,cost);
     for(i=0;i<400;i++)
     {
      lIdea=9999;
      pathIdea=-1;
     }
     v=start;
     visited[v]=1;
     path[start]=0;
     for(i=0;v!=end;i++)
     {
      for(j=0;j<=cnt;j++)
      {
       if(visited[j]==1)
        continue;
       l[j]=min(l[j],pl+cost[v][j]);
       if(min(l[j],pl+cost[v][j])==pl+cost[v][j])
        path[j]=v;
      }
      v=minimum(l,visited,cnt);
      visited[v]=1;
      pl=l[v];
     }
     for(k=0,i=end;i!=startWink
     {
      visited[k++]=pathIdea;
      i=pathIdea;
     }
     return pl+values[0][0];
    }

    void main()
    {
     clrscr();
     printf("\n%d",mazeMove(r,c,values));
     getch();
    }

    Friday, April 27, 2007 7:11 PM
  • thankz for the code, but it is having some errors as the smileys replaced some of the key terms.. please use the code block for giving the codes....

    Well your program works, i just checked it, but please tell the logic u used to do it....
    Saturday, April 28, 2007 2:41 AM
  • try replacing the matrix value with the one i m giving...

    int r = 4;
    int c = 6;
    int values[][20] = { { 5,  6,  7, 10, 11,  3},
                         { 2, 10,  5,  6,  1, 10},
                         { 1,  2, 12,  5,  6,  1},
                         { 3,  1,  6,  2, 21 ,13}};

    At quiz this example was given.. now the answer was suppose to be 44, but your code is giving 41.. now how did the code found 41 as answer??

    If you can just trace down, you would get the idea of whatz going on, and please do explain the logic that you applied.
    Saturday, April 28, 2007 2:50 AM
  • Thanks dude for  the code. It would be nice if you give the logic of your code, its a bit tricky Stick out tongue
    Saturday, April 28, 2007 2:19 PM
  • Helloo Anyone Out there.. why did we stopped.... Rajkumar Please explaing the logic you u used...
    Tuesday, May 1, 2007 2:58 AM
  • I think no one is interested anymore in that maze solution.

    Lets post another question Smile
    Tuesday, May 1, 2007 4:38 PM
  • Code Snippet

    Block Counting
    Mantri builders have recently acquired a huge piece of land and they plan to sell blocks of land within that piece. You need to write a program to determine how many blocks of land are available in that piece. Consider this piece of land as a (x,y) graph in two dimensional space. If you have difficulty in imagining this, please refer to the graph provided in the example section below. The method countBlock uses two parameters as input and they are integer n, which is number of co ordinates in the graph and integer array coordinates, which is an array of 1*2.

    Constraints:
    # The number of coordinates should be a positive integer
    # The coordinate points in x and y quadrant should be a positive integer
    # The maximum number of coordinates n that can be given as input value should not exceed 100
    # The maximum number of coordinate combinations which is a 1*2 array that can be given as input value should not exceed 100 x*y points


    Example 1:
    Input
    int n = 6
    int coordinates[][2] = { {1,1}, {1,5}, {5,3}, {5,5}, {7,1}, {7,3} }.
         Click Here to view the example.

    Output Returns : 20
    Explanation: Count all the blocks inside the given coordinate values { {1,1}, {1,5}, {5,3}, {5,5}, {7,1}, {7,3} }. Hence the total number of blocks are 20.

    Example 2:
    Input
    int n = 8
    int coordinates[][2] = { {1,1}, {1,5}, {3,2}, {3,5}, {5,2}, {5,5}, {7,1}, {7,5} }.
    Output Returns : 18

    For C solutions
    Header File    :    BlockCounting.h
    Function Name    :    int countBlock(int n, int coordinates[][2]
    Directory Name    :    blockcounting
    File Name    :    BlockCounting.c
    For C++ solutions
    Header File    :    BlockCounting.h
    Class Name    :    block
    Function Name    :    int countBlock(int n, int coordinates[][2]
    Directory Name    :    blockcounting
    FileName    :    BlockCounting.cpp


    Tuesday, May 1, 2007 4:39 PM
  • The above question is for the Block Counting Problem.

    I guess its a hard one, lets see if anyone can solve it Smile

    I have many more questions if you guys want ....
    Tuesday, May 1, 2007 4:41 PM