CareerCup

We can solve this problem by storing the product of all rows in a rows array and then the product of all column in a column array. Then, we will be simple multiplication of the rows and column.

Code:

public class Practice77 {
	public static void main(String[] args){
		int[][] arr = {{1,2,3,1},
					  {1,0,-1,2},
					  {-1,1,1,1}};
		int rows[] = new int[arr.length];
		int col[] = new int[arr[0].length];
		int tot = 1;
		int colNo = 0;
		for(int i=0;i<rows.length;i++){
			tot = 1;
			for(int j=0;j<col.length;j++){
				tot = tot * arr[i][j];
			}
			rows[i] = tot;
		}
		
		for(int i=0;i<col.length;i++){
			tot = 1;
			for(int j=0;j<rows.length;j++)
				tot = tot * arr[j][i];
			col[i] = tot;
		}
		
		
		for(int i=0;i<rows.length;i++){
			for(int j=0;j<col.length;j++){
				int val = rows[i] * col[j];
				if(val > 0){
					arr[i][j] = 1;
				}else if(val == 0){
					arr[i][j] = 0;
				}else{
					arr[i][j] = -1;
				}
			}
		}
		
		for(int i=0;i<rows.length;i++){
			System.out.println(Arrays.toString(arr[i]));
		}
	}
		
}

One easier solution is to calculate the multiplication of all elements in i'th rows(int[] rowMul) and j'th columns(int[] colMul). So total 3+4=7 multiplication.
Later just go through the matrix to do

for(int i=0; i<rows; i++)
 for(int j=0; j<columns; j++)
    {
	if(rowMul[i]*colMul[j] > 0)
            matrix[i][j] = 1;
       else if(rowMul[i]*colMul[j] < 0)
            matrix[i][j] = -1;
       else 
            matrix[i][j] = 0;
  }

/*
Running time is terrible
*/

Original[n][n];
result[n+1][n+1];

for(row =0; row < NumOfRow; row++)
{
result[row][n] = 1;
for(col=0;col<NumOfColumn;col++)
{
result[row][n] = result[row][n] * Original[row][col] //last row cell
result[n][col] = result[row][n] * Original[row][col] //last col cell
}
}

for(row =0; row < NumOfRow; row++)
{
for(col=0;col<NumOfColumn;col++)
{
if(result[row][n] * result[n][col] > 0)
{
result[row][col] = 1;
}
else if (result[row][n] * result[n][col] == 0)
{
result[row][col] = 0;
}
else
{
result[row][col] = -1;
}
}
}

This cpp code worked perfectly fine with no error:

#include<iostream.h>
#include<conio.h>
void main()
{
clrscr();
signed int a[10][10],b[10][10],m,p;
signed int i,j,k,l;
cout<<"Enter the array value"<<endl;
for(i=1;i<=3;i++)
{for(j=1;j<=4;j++)
{cin>>a[i][j];
}
}
for(i=1;i<=3;i++)
{for(j=1;j<=4;j++)
{cout<<a[i][j];
}cout<<endl;
}cout<<endl;
for(i=1;i<=3;i++)
{for(j=1;j<=4;j++)
{       m=1;p=1;
	for(k=1;k<=4;k++)
	{m*=a[i][k];
	}
	for(l=1;l<=3;l++)
	{p*=a[l][j];
	}
	if((m*p)==0)
	{b[i][j]=0;
	}
	else if((m*p)>0)
	{b[i][j]=1;
	}
	else if((m*p)<0)
	{b[i][j]=-1;
	}
}
}
cout<<"Final result: "<<endl;
for(i=1;i<=3;i++)
{for(j=1;j<=4;j++)
{cout<<b[i][j];
}cout<<endl;
}
getch();
}

1. One way could be to store just the locations of 0s and negative numbers. e.g. if (i,j) contains 0, then (i,:) = 0 and (:,j) = 0.

2. Similar will be the case with any negative number (keeping a track of number of negative numbers : -1 if odd and 1 if even)

3. Rest all values will be 1

I think my below code is a partial dynamic program

I have used a dictionary to store the values of column. multiplying the column values will take at most len(column) and after that theta(1) amortized running time.

And the inner for loop will be skipped if the multiplication of row values = 0.

If I'm wrong or any other improvement can be done for the efficiency, pls post it!

#!usr/bin/python3
col_dict = {}

def row_calculation(row,number):
        total = 1
        for elem in row:
            total = elem * total
        return total
def column_calculation(column,number):
    if number not in col_dict:
        total =1
        for elem in column:
            total = elem * total
        col_dict[number] = total
        return total
    else:
        return col_dict[number]

def main():
    matrix_list = [[1,2,3,1],[1,0,-1,2],[-1,1,1,1]]
    new_matrix = []
    row_length = len(matrix_list)
    column_length = len(matrix_list[0])
    for row in range(len(matrix_list)):
        temp_list = []
        row_value = row_calculation(matrix_list[row],row)
        if row_value is 0:
            temp_list = [0]*column_length
            new_matrix.append(temp_list)
            continue
        for elem in range(len(matrix_list[row])):
            column_list = [matrix_list[col_number][elem] for col_number in range(row_length)]
            column_value = column_calculation(column_list,elem)
            if (column_value * row_value) > 0:
                temp_list.append(1)
            elif (column_value * row_value) < 0:
                temp_list.append(-1)   
            else:
                temp_list.append(0)
        new_matrix.append(temp_list)
    print(new_matrix)
if __name__ == "__main__" : main()

O(N) - Using TreeMap

import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.TreeMap;


public class matrixMul {

	public static void main(String[] args) {
		
		TreeMap<String,Integer> hm = new TreeMap<String,Integer>();
		TreeMap<String,Integer> tm1 = new TreeMap<String,Integer>();
		TreeMap<String,Integer> tm2 = new TreeMap<String,Integer>();
		
		hm.put("1,1",1);	hm.put("2,1",1);	hm.put("3,1",-1);
		hm.put("1,2",2);	hm.put("2,2",0);   hm.put("3,2",1); 
		hm.put("1,3",3);	hm.put("2,3",-1);  hm.put("3,3",1);
		hm.put("1,4",1);	hm.put("2,4",2);   hm.put("3,4",1);
			
		Set<Entry<String, Integer>> s = hm.entrySet();		
        Iterator<Entry<String, Integer>> i = s.iterator();
		
		while(i.hasNext()){			
			@SuppressWarnings("rawtypes")
			Map.Entry he = (Map.Entry)i.next();
			String Key = he.getKey().toString();
			int Value = (Integer)he.getValue();
			
						
			String [] sarray = Key.split(",");
			
			if(tm1.containsKey(sarray[0])){
				int num = (Integer)tm1.get(sarray[0]);
				tm1.put(sarray[0], num*Value);
			}
			else
				tm1.put(sarray[0], Value);		
			
			if(tm2.containsKey(sarray[1])){
				int num = (Integer)tm2.get(sarray[1]);
				tm2.put(sarray[1], num*Value);
			}
			else
				tm2.put(sarray[1], Value);	
		}
		
		System.out.println(tm1);
		System.out.println(tm2);
		
		Set<Entry<String, Integer>> st = hm.entrySet();		
        Iterator<Entry<String, Integer>> it = st.iterator();
		
		while(it.hasNext()){			
			@SuppressWarnings("rawtypes")
			Map.Entry he = (Map.Entry)it.next();
			String Key = he.getKey().toString();
			String [] sarray = Key.split(",");
			
			int Value1 = tm1.get(sarray[0]);
			int Value2 = tm2.get(sarray[1]);
			int Value3 = Value1*Value2;
						
			if(Value3 == 0){
				hm.put(Key, 0);
			}
			else if(Value3 < 0){
				hm.put(Key, -1);
			}
			else{
				hm.put(Key, 1);
			}			
		}
		
		System.out.println(hm);
		
	}

}

package code;

public class Matrix {

public static void main(String[] args)
{

int[][] matrix={{1,2,3,1},{1,0,-1,2},{-1,1,1,1}};

int[] row=new int[3];
int[] col=new int[4];


for(int i=0;i<3;i++)
{
row[i]=1;
}
for(int j=0;j<4;j++)
{
col[j]=1;
}

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

for(int j=0;j<4;j++)
{
if(matrix[i][j]<0)
{
if(row[i]!=0)
{
row[i]=-row[i];
}


if(col[j]!=0)
{
col[j]=-col[j];
}

}
else if(matrix[i][j]==0)
{
row[i]=0;
col[j]=0;
}

}
}



/*for(int i=0;i<row.length;i++)
{
System.out.println("row: "+row[i]);
}

for(int j=0;j<col.length;j++)
{
System.out.println("col: "+col[j]);
}*/

int[][] output=new int[row.length][col.length];

for(int i=0;i<row.length;i++)
{
for(int j=0;j<col.length;j++)
{
if(row[i]==0||col[0]==0)
output[i][j]=0;

if((row[i]==col[j])&&(row[i]!=0))
output[i][j]=1;

if((row[i]==-1&&col[j]==1)||(row[i]==1&&col[j]==-1))
{
output[i][j]=-1;
}
}
}


for(int i=0;i<row.length;i++)
{
System.out.println();
for(int j=0;j<col.length;j++)
System.out.print(output[i][j]+" ");
}

}

}

matrix=[[1, 2, 3, 1], [1, 0, -1, 2], [-1, 1, 1, 1]]

def column_multiplication(rows,col_elem):
col_result=1
while rows>0:
col_result=col_result * matrix[rows-1][col_elem]
rows=rows-1
return col_result

def rows_multiplication(col,row_elem):
rows_result=1
while col>0:
rows_result=rows_result * matrix[row_elem][col-1]
col=col-1
return rows_result

def main():
print "Given Matrix : ", matrix
rows=len(matrix)
col=len(matrix[0])
new_matrix=[ [ None for i in range(col) ] for j in range(rows) ]
for row_elem in range(rows):
for col_elem in range(col):
col_result=column_multiplication(rows,col_elem)
rows_result=rows_multiplication(col,row_elem)
if col_result * rows_result == 0:
new_matrix[row_elem][col_elem]= 0
elif col_result * rows_result > 0:
new_matrix[row_elem][col_elem]= 1
elif col_result * rows_result < 0:
new_matrix[row_elem][col_elem]= -1
print "Result Matrix : ", new_matrix

if __name__=="__main__":
main()

static int[][] findMult(int[][] arr)
	{
		

		int[][] result = new int[arr.length][arr[0].length];
		int mult =1;
		for(int i=0; i<arr.length ; i++)
		{
			
			for(int j=0; j< arr[i].length ; j++)
			{
				for(int k=0; k< arr.length ; k++)
				{
					mult *= arr[k][j];
					
				}
				for(int k=0; k< arr.length ; k++)
				{
					mult *= arr[i][k];
					
				}
				
				if(mult > 0)
				{
					result[i][j] = 1;
					
				}else if(mult < 0)
				{
					result[i][j] = -1;
				}else
				{
					result[i][j] = 0;
				}
				
				mult = 1;
			}
			
			
		}
		return result;
		
	}

matrix=[[1, 2, 3, 1], [1, 0, -1, 2], [-1, 1, 1, 1]]

def column_multiplication(rows,col_elem):
col_result=1
while rows>0:
col_result=col_result * matrix[rows-1][col_elem]
rows=rows-1
return col_result

def rows_multiplication(col,row_elem):
rows_result=1
while col>0:
rows_result=rows_result * matrix[row_elem][col-1]
col=col-1
return rows_result

def main():
print "\nGiven Matrix : ", matrix, "\n"
rows=len(matrix)
col=len(matrix[0])
new_matrix=[ [ None for i in range(col) ] for j in range(rows) ]
for row_elem in range(rows):
for col_elem in range(col):
col_result=column_multiplication(rows,col_elem)
rows_result=rows_multiplication(col,row_elem)
if col_result * rows_result == 0:
new_matrix[row_elem][col_elem]= 0
elif col_result * rows_result > 0:
new_matrix[row_elem][col_elem]= 1
elif col_result * rows_result < 0:
new_matrix[row_elem][col_elem]= -1
print "Result Matrix : ", new_matrix

if __name__=="__main__":
main()

public static int[][] computeIndicators(int[][] inputMatrix){
		int rows = inputMatrix.length;
		int cols = inputMatrix[0].length;
		int[] rowIndicators = new int[rows];
		int[] colIndicators = new int[cols];
		int[][] outputMatrix = new int[rows][cols];		
		
		for(int i = 0; i < rows; i++){
			int rowIndicator = 1;
			for(int j = 0; j < cols; j++){
				rowIndicator *= inputMatrix[i][j];	
			}
			if(rowIndicator > 0) rowIndicators[i] = 1;
    			else if(rowIndicator == 0) rowIndicators[i] = 0;
 			else rowIndicators[i] = -1;
		}

		for(int i = 0; i < cols; i++){
			int colIndicator = 1;
			for(int j = 0; j < rows; j++){
				colIndicator *= inputMatrix[j][i];	
			}
			if(colIndicator > 0) colIndicators[i] = 1;
    			else if(colIndicator == 0) colIndicators[i] = 0;
 			else colIndicators[i] = -1;
		}

		for(int i = 0; i < rows; i++){
			for(int j = 0; j < cols; j++){
				outputMatrix[i][j] = rowIndicators[i] * colIndicators[j];
			}
		}

		return outputMatrix;

}

public static int[][] getMatrix01(int[][] a) {

int r = a.length;
int c = a[0].length;
int[][] b = new int[r][c];

for (int i = 0; i < r; i++) {
    
    for (int j = 0; j < c; j++) {
     
     int result = 1;
     
     for (int i2 = 0; i2 < r; i2++) {
        result *= a[i2][j];     
     }

     for (int j2 = 0; j2 < c; j2++) {
         result *= a[i][j2];
     }
      
     if (result > 0) {
         b[i][j] = 1;
     } else if (result < 0) {
         b[i][j] = -1;
     } else {
         b[i][j] = 0;
     }
    
    }
}
    
 return b;
}

def pos_neg_matrix(A):
	M,N = len(A), len(A[0])
	rnegs, cnegs = M*[0], N*[0]
	rzeros, czeros = M*[False], N*[False]
	B = [N*[0] for i in range(M)]
	######################################
	for r in range(M):
		for c in range(N):
			rzeros[r] |= A[r][c]==0
			czeros[c] |= A[r][c]==0
			rnegs[r] += A[r][c]<0
			cnegs[c] += A[r][c]<0
	######################################
	for r in range(M):
		if rzeros[r]:
			continue
		for c in range(N):
			if not czeros[c]:
				negcount = rnegs[r] + cnegs[c] - (A[r][c]<0)
				B[r][c] = 1 - 2*(negcount%2)
	return B # in total M*N running time
##########################################
if __name__ =='__main__':
	A = [[1, 2, 3, 1],
		[1, 0, -1, 2],
		[-1, 1, 1, 1]]
	print pos_neg_matrix(A)
	# [[-1, 0, -1, 1], [0, 0, 0, 0], [-1, 0, 1, -1]]

first pass
-count negatives numbers in each row and column
-record zeros in each row column
second pass
- test for zero, if not then
- count total negatives for row and column of given element (without double counting if element itself is negative)

Create to auxiliary arrays
- 'row' where row[i] contains multiplication for i-th row - (-1 if product is < 0 ; 1 if product > 0; 0 if product == 0)
- 'col' where col[j] contains multiplication for j-th column. Rules are the same as for rows
I think the rest is self explaining if you check the implementation.
Code:

public static void main(String[] args) {
        int[][] m = { { 1, 2, 3, 1 }, { 1, 0, -1, 2 }, { -1, 1, 1, 1 } };
        int[] row = new int[m.length];
        int[] col = new int[m[0].length];
        Arrays.fill(row, 1);
        Arrays.fill(col, 1);
        for (int i = 0; i < m.length; i++) {
            for (int j = 0; j < m[0].length; j++) {
                if (m[i][j] < 0) {
                    row[i] *= -1;
                    col[j] *= -1;
                } else if (m[i][j] == 0) {
                    row[i] = 0;
                    col[j] = 0;
                }
                m[i][j] = 1;
            }
        }
        for (int i = 0; i < m.length; i++) {
            for (int j = 0; j < m[0].length; j++) {
                m[i][j] *= row[i] * col[j];
            }
        }
    }