CareerCup

I have another observation;
Scan through the input array :- 2 ,3 ,4 ,10 ,5
and create an array of the products in order. And create another array which finds the products in reverse

ie new arrays will be

2 , 2*3 , 2*3*4 , 2*3*4 * 10 , 2*3*4 *10* 5, -> A[]
2 * 3 * 4 *10 *5 , 3 * 4 *10 *5 , 10 *5 , 5 -> B[]

Now an element in the resulting array, i = A [i-1] * B [i +1]

suppose array is :
int arr[]={a,b,c,d,e};
int size=sizeof(arr)/sizeof(int);
int arr1[size];
int arr2[size];
int arr3[size];
arr1[0]=1;arr2[size-1]=1;
for(int i=1;i<size;i++)arr1[i]=arr1[i-1]*arr[i-1];
for(int i=size-2;i>=0;i--)arr2[i]=arr2[i+1]*arr[i+1];
for(int i=0;i<size;i++)arr3[i]=arr1[i]*arr2[i];

s = 1
for (int i=0; i<len-1; i++) {
	s *= a[i];
	b[i+1] = s;
}
s = 1; b[0] = 1;
for (int i=len-1; i>0; i--) {
	s *= a[i];
	b[i-1] *= s;
}

O(2n)

whats the time limitation ??
One can easily do it in O(n^2) time.

public class ProductWithoutDivision {

	public static void main(String args[]){
		int a[]={1,7,1,-1,5,4};
		int b[]={0,0,0,0,0,0};
		int prod_a = getProduct(a);
		int zerocount = countZerosInArray(a);
		if (zerocount >1) 
		{
			print_b_array(a.length, b);
			System.exit(0);
		}
		else if (zerocount == 1) {
			for (int i=0;i<a.length;i++)
			{
				if (a[i]==0) 
				{
					b[i]=prod_a;
					break;
				}
			}
			print_b_array(a.length, b);
			System.exit(0);
		}

		for (int i=0;i<a.length;i++)
		{
			if (prod_a<0 && a[i]>0) 
				b[i]= - func(prod_a, -a[i]);
			else
				b[i]=func(prod_a, a[i]);
		}
		print_b_array(a.length, b);
	}
	private static void print_b_array(int len, int[] b) {
		for (int i=0; i<len;i++)
		{
			System.out.println("b["+i+"]="+b[i]);
		}
	}
	private static int countZerosInArray(int x[])
	{
		int zerovalcount=0;
		for (int i=0; i<x.length;i++)
		{
			if (x[i]==0) 
			{
				zerovalcount++;
			}
		}
		return zerovalcount;
	}

	private static int getProduct(int x[])
	{  
		int val=1;
		for (int i=0; i<x.length;i++)
		{
			if (x[i]==0) 
			{
				continue;
			}
			val = val * x[i];
		}
		return val;
	}

	private static int func(int prod, int y)
	{
		int count = 0;
		while (prod != 0)
		{
			count++;
			prod = prod - y;
		}
		return count;
	}
}

public class ProductOfItemsInArray {
	public static void main(String args[])
	{
		int a[]={4,5,2,3};
		int b[]={1,1,1,1};
		for(int i=0; i<a.length;i++)
		{
			for (int j=0;j<a.length;j++)
			{
				if(i==j) continue;
				else {
				b[i]=b[i]*a[j];
				}
			}
		}
		for(int i=0;i<a.length;i++)
		{
			System.out.println(b[i]);
		}
	}
}

private int[] calc(int[] input) {
        int[] output = new int[input.length];
        int product = 1;
        int zeroCount = 0;
        int zeroIdx = -1;
        for (int i = 0; i < input.length; i++) {
            // Kepp track of number of 0's in input
            if (input[i] == 0) {
                zeroCount++;
                zeroIdx = i;
            } else {
                product *= input[i];
            }
            // If input has more than 1 zero, all the output elements will be 0
            if (zeroCount > 1) {
                for (int j = 0; j < input.length; j++) {
                    output[j] = 0;
                }
                return output;
            }
        }

        for (int i = 0; i < input.length; i++) {
            if (zeroIdx != -1 && input[i] == 0) {
                output[i] = product;
            } else {
                output[i] = product / input[i];
            }
        }
        return output;
    }

can be solved with o(n).
take every element take mod of it with N. put that as arr[ele%N] += ele*N.

and before putting that check if ele == arr[ele/N] then it is the repeated element.

Keep omitting the present index while taking the product which can be done by cyclic indexing.
Following is the code with O(n) complexity:

void main()
{

int a[]= {1,2,3,4,5};
int prod[]= {1,1,1,1,1};
int i=0,j=0;

for(i=0;i<5;i++)
{
j=i+1;
if(j==5)
j=0;

while(i!=j)
{
printf("entered logic\n");
prod[i]*=a[j];

if(j==4)
j=0;
else
j++;

}
}
i=0;
while(i<5)
{
printf("%d\n",prod[i]);
i++;
}

return;
}

sorry it is o(n*2) complexity

let c[i]=log(a[i]) , C=sum(c[i]),b[i] = exp(C-c[i]) assume no 0 ina[i]

public class ElementProductWithoutDivision {
public static int[] getProductsofItemsInArray(int[] arr) {
if(arr == null)
return null;
int size = arr.length;

int product = 1;
int[] forward = new int[size+1];
int[] backward = new int[size+1];
int[] result = new int[size];

forward[0] = 1;
backward[size] = 1;
for(int i=1; i <= size; i++) {
product *= arr[i-1];
forward[i] = product;
}

product = 1;
for(int i=size-1; i >=0; i--) {
product *= arr[i];
backward[i] = product;
}

for(int i=0; i<size; i++) {
result[i] = forward[i] * backward[i+1];
}
return result;
}

public static void main(String[] args) {
int[] arr = {2 ,3 ,5 ,10 ,5};
int[] result = getProductsofItemsInArray(arr);
for(int i=0; i< result.length; i++) {
System.out.printf("%5d", result[i]);
}
}
}

C[n-1] = 1;
D[0] = 1;
for(int i = n-1,j = 1; i > 1 && j <= n-1;i++,j++)
{
	C[i - 1] = c[i] * A[i]
	D[j] = D[j-1]*A[j - 1]
}

for(int i = 0; i<n-1; i++)
{
	B[i] = C[i] * D[i];
}