InMobi Interview Question
Country: India
Interview Type: In-Person
First Array A[] should have 1 as initial element and Second Array B[] should have 1 at the end.
A[] = {1, 2 , 2*3 , 2*3*4 , 2*3*4 * 10 , 2*3*4 *10* 5}
B[] = {2 * 3 * 4 *10 *5 , 3 * 4 *10 *5 , 10 *5 , 5, 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];
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;
}
}
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;
}
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]);
}
}
}
I have another observation;
- GingerBreadMan May 21, 2012Scan 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]