Question

2. Given an array of integers, find two numbers such that they add up to a specific target number. Input: numbers (2, 7,1 15, target-9 (10 points) Output: index-, ndex2-2 3. Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0. (10 points)

Answer 1

2. Here we will check for every pair of integers in array and if their sum is equal to target the output the index.

void Find( int A[], int n, int target)

{

int i,j ;

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

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

{

if (i==j)

continue; //since we do not want repeated element

else if(A[i] + A[j] ==target) //then we got two index

{ printf ("index1 = %d, index2 = %d", i,j); return; }//print index and return

else

continue; //continue till we do not find the index

}

return; //return if no such index are found

}

3. Below is the algorithm to do this. We will maintain two arrays A and B of size M and N respectively. Here A[i] will 1 if row i of matrix C will be all 0s and B[j] will be 1 if column j of matrix C will be all 0s.

ALGO(C[][] , int M, int N)

1. Set all entries of array A and array B to be 0.

2. For i = 1 to M

3.......For j= 1 to N

4............. if (C[i][j] ==0 ) //we have to make row i and column j all 0s

5....................Then Set A[i] = 1 and B[j] = 1

6. For i= 1 to M

7.......For j= 1 to N

8...........if (A[i]==1 || B[j]==1) //if either of row i or column j set to be 0

9.................C[i][j] = 0 //then set C[i][j] to be 0

10. Return;

Please comment for any clarification.