CareerCup

Maintain two arrays - front [ ] and rear [ ]
front maintains the product before the current index
rear maintains the product after the current index
then the product of current index i = front[i]*rear[i]

int [] product (int [] input) {
	int [] front = new int[input.length];
	int [] rear = new int[input.length];
	int [] output = new int[input.length];
	front[0] = 1;
	rear[input.length-1] =1;
	for(int i = 1; i < input.length; i++)
		front[i] = front[i-1]*input[i-1];
	for(int i = input.length-2; i >=0; i--)
		rear[i] = rear[i+1]*input[i+1];
	for(int i = 0;i<input.length;i++)
		output[i] = front[i]*rear[i];
	return output;
}

python

def multiplyList(input,pos,val):
    if pos == len(input):
        return 1
    retVal = multiplyList(input,pos+1,input[pos]*val)
    newretVal = retVal*input[pos]
    input[pos] = retVal*val 
    return newretVal

input = [2,3,1,4]
multiplyList(input,0,1)
print input

I would like to explain it with example instead of code. Because code would be really easy:

arr = 2, 3, 1, 4

// maintain two arrays which can be done in O(n)

arr1 = 2,  6,   6,  24 (arrays multiply each number with previous and current)
arr2 = 24, 12, 4, 4    (arrays multiplied from end)

In above two arrays, put 1 in beginning of arr1 and end of arr2:
arr1 = 1, 2,  6,   6,  24, 1
arr2 = 24, 12, 4, 4,   1

Then to find number at index 'i' you would just do:

arr1[i]*arr2[i+1]

Does division as repeated subtraction also doesn't count?

void multiplyAllOthers(int arr[], int n)
{
	int* copy = new int[n];
	memcpy(copy, arr, sizeof(int) * n);

	//multiply all others in the left
	for(int productSoFar = 1, i = 0; i < n; ++i){
		arr[i] *= productSoFar;
		productSoFar = arr[i];
	}
	//multiply all others in the right
	for(int productSoFar = 1, i = n-1; i >= 0; --i){
		arr[i] *= productSoFar;
		productSoFar *= copy[i];
	}

        delete[] copy;
}

time:O(n), space:O(n)

public int GetQuotient(int a, int b)
{
	if (a < b)
		return 0;
	if (a == b)
		return 1;
	else 
	{
		int q = (int) Math.Pow(e, (Math.Log(a) - Math.Log(b)));
		return q;
	}
}

public void ChangeArray(int[] arr, int n)
{
	int product = 1;
	for (int i = 0; i< n; i++)
	{
		product *= arr[i];
	}

	for(int i = 0; i< n; i++)
	{
		arr[i] = GetQuotient(product, arr[i]);
	}
}

The GetQuotient method does not add complexity because its a formulated mathematical calculation.

So the complexity of the program is still O(n).

#include <stdio.h>
int main()
{
int a[4],b[4],i,n;
for(i=0;i<4;i++)
{
scanf("%d",&a[i]);
}
for(i=0;i<4;i++)
{
if(i==0)
{
b[i]=a[i+1]*a[i+2]*a[i+3];
}
else if(i==1)
{
b[i]=a[i-1]*a[i+1]*a[i+2];
}
else if(i==2)
{
b[i]=a[i-2]*a[i-1]*a[i+1];
}
else
{
b[i]=a[i-3]*a[i-2]*a[i-1];
}
}
for(i=0;i<4;i++)
{
printf("%d ",b[i]);
}
return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int main()
{
    vector<double> A = {1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0};
    vector<double> M(A.size()); 

    const int N = A.size();
    double m = 1.0;

    for (int i = 0; i < N; i++) {
        M[i] = m;       // m = A[0] * A[1] * .... * A[i - 1]
        m *= A[i];      // update m
    }    

    m = 1;
    for (int i = N - 1; i >=0; i--) {
        M[i] *= m;      // m = A[i+1] * ... * A[N-1]
        m *= A[i];      // update m
    }
   
    for (double d : M) cout << d << " "; cout << endl;

    return 0;
}

Shouldn't it be so simple...
1. Multiple all element in first go
2. Divide the result by current element to get result at that position.

multiply all the array elements and then divide the product with present element.

Multiplying anagram values

Multiplying anagram values

public static void main(String[] args) {
		
		for (int i = 0; i < a.length; i++) {
			
			System.out.println(multiply(i, a.length, 1, a, 0));
			System.out.println("countAll : "+countAll);
		}
	}
public static int multiply(int i, int n, int r, int a[], int count) {
			
			int j = i + 1;
			
			if(j >= n)
				r = r * a[j - n];
			else
				r = r * a[j];
		
			count++;
			
		
			if(count+1 == n)
				return r;
			
			return multiply(j, n, r, a, count);
		}

Here is my code

1. Identify the current index and set the value of that element as 1
2. Multiple the elements in the array , that will be product of 3 numbers

public class MultiplyNumber {
	
	public static int[] Multiply(int[] arr,int len)
	{
		int[] output = new int[arr.length];
		int start = 0;
		int k = 1;
		int temp = 0;
		int currentIndex = 0;
		for(int i = 0 ; i < arr.length; i ++)
		{
			start = 0;
			k = 1;
			temp = arr[i];
			arr[i] = 1;
			currentIndex = i;
				while(start != len)
				{
					k =  k * arr[start];
					start ++;
				}
				arr[currentIndex] = temp;
				output[i] = k;
		}
		return output;
	}

	public static void main(String[] args) {

		int[] a = {2,3,1,4};
		int[] out = Multiply(a,a.length);
		for(int i = 0 ; i <out.length; i ++)
		{
			System.out.print(out[i]+",");
		}
	}

}

function insideOutProduct(a) {
    if (!a || a.length <= 1) {
        return a;
    }
    var before = a.map(function(n, i) { return a.reduce(function(prev, curr, j) { return j < i ? prev*curr : prev; }, 1); });
    var after = a.map(function(n, i) { return a.reduce(function(prev, curr, j) { return j > i ? prev*curr : prev; }, 1); });
    var product = a.map(function(n, i) { return before[i] * after[i]; });
    return product;
}

public class FaceBookProblem1 {

public static void main(String[] args) {
int input[] = { 2, 3, 1, 4 };
fillArray(input, 0, input.length, 1);
for (int i = 0; i < input.length; i++) {
System.out.println(input[i]);
}
}

private static int fillArray(int[] array, int index, int length, int value) {
if (index == (length - 1)) {
int val = array[index];
array[index] = value;
return val;
} else {
int val = fillArray(array, index + 1, length, value * array[index]);
int retVal = val * array[index];
array[index] = value * val;
return retVal;
}
}
}

{
public static void main(String[] args) {
int[] input = {2, 3, 1, 4};
int[] output = new int[input.length];

int index;
for (index = 0; index < input.length; index ++) {
output[index] = 1;
}

int m = 1;
for (index = 0; index < input.length; index ++) {
output[index] = m;
m = m * input[index];
}

m = 1;
for (index = input.length - 1; index >= 0; index --) {
output[index] = output[index] * m;
m = m * input[index];
}

for (index = 0; index < output.length; index ++) {
System.out.println(output[index]);
}
}



}

-(int)products:(int [])a :(int )currIndex :(int )forIndex :(int )len
{
    int static output[] = {1,1,1,1};
    
    if(currIndex == len)
        return 1;
    
    int result = [self products:a :currIndex+1 :forIndex :len];
    output[forIndex] = result;
    
    if(currIndex == forIndex)
        return result;
    else
        return a[currIndex] * result;
}
// Input
int a[] = {2,3,1,4};
    printf("\nproducts : ");
    for(int i=0;i<4;i++)
    {
        int result = [self products:a :0 :i :4];
        printf("%d, ",result);
    }
// Output
/*
products : 12, 8, 24, 6, 
*/

public static void main(String[] args){
int[] a={2,3,1,4};
solve(a,0);
}


static void solve(int[] a,int index){
//result array
int[] r = new int[a.length];
int t=1;

//multiple from left
for(int i=0;i<a.length;i++){
r[i]=t;
t=t*a[i];
}

t=1;

//multiple from right
for(int i=(a.length-1);i>=0;i--){
r[i]=t*r[i];
t=t*a[i];
}

//complete
for(int i=0;i<a.length;i++){
System.out.println(r[i]);
}

private static int[] multiplyOthers(int [] a) {
int [] p = new int[a.length];

for (int i = 0; i < a.length; i ++) {
int multiplior = 1;
for(int j=0; j<a.length; j++) {
if(i != j) {
multiplior = multiplior * a[j];
}
}
p[i] = multiplior;
}
return p;
}

1. long product = a[0]*a[1]*..*a[n]
2. return [product/a[0], product/a[1].. product/a[n]]

int[] solve(int[] input) {
    int[] output = new int[input.length];

    int product = 1;
    for (int i = 0; i < input.length; i++) {
      output[i] = product;
      product = product * input[i];
    }

    product = 1;
    for (int i = input.length - 1; i >= 0; i--) {
      output[i] = output[i] * product;
      product = product * input[i];
    }
    return output;
  }

Or you could just implement the division function with a while-loop. It's sneaky but it fulfills the requirements.

def mult_rest_indices(array):
    sum = 1
    for i in array: 
        sum*=i
        
    result= []
    for i in array:
        k=0
        x=sum
        while x>0:
            x-=i
            k+=1
        result.append(k)
    print result

function mul(a, b) {
return a * b;
}

function genArray(a) {
var res = [];

a.map(function(item, i) {
res.push(a.filter(function( ai) {
return ai !== item;
}).reduce(mul));
});
return res;
}

console.log(genArray(a));

{{ iinput = [2,3,1,4]

def main():
output = []
allMulti = reduce(lambda x, y: x*y, iinput)

for i in xrange(0, len(iinput)):
output.append(allMulti / iinput[i])

return output

print main() }}

is it O(n)?

I came up with two different solutions, one using recursion and one one without it. I'm not sure of the big o for the one with recursion but the one with out t should meet the requirements.

def multi(a_list, count, nlist):
    total = 1
    if count >= len(a_list):
        return
    for element in a_list:
        if a_list[count] != element:
            total *= element
    nlist.append(total)
    count += 1
    multi(a_list, count, nlist)
    return nlist

def mulit1(a_list):
    nlist = []
    total = 1
    for element in a_list:
        total *= element
    count = len(a_list)
    for element in a_list:
        nlist.append(total)
    i = 0
    for element in a_list:
        nlist[i] /= element
        i += 1
    return nlist

nlist = []
li = [1, 4, 5, 2, 3]
print multi(li, 0, nlist)
print mulit1(li)

C# with Linq:

var l = new List<int>() {2, 3, 1, 4, 2};
            var m = l.Select(i =>
            {
                var sl = new List<int>(l);
                sl.Remove(i);
                return sl.Aggregate((a, b) => a*b);
            });

input = 8
output =
1 1 1 1 1 1 1 2
3 2 2 2 2 2 2 2
3 3 3 3 3 3 3 4
5 4 4 4 4 4 4 4
5 5 5 5 5 5 5 6
7 6 6 6 6 6 6 6
7 7 7 7 7 7 7 8
pattern program in java

input = 8
output =
1 1 1 1 1 1 1 2
3 2 2 2 2 2 2 2
3 3 3 3 3 3 3 4
5 4 4 4 4 4 4 4
5 5 5 5 5 5 5 6
7 6 6 6 6 6 6 6
7 7 7 7 7 7 7 8
pattern program in java

input = 8
output =
1 1 1 1 1 1 1 2
3 2 2 2 2 2 2 2
3 3 3 3 3 3 3 4
5 4 4 4 4 4 4 4
5 5 5 5 5 5 5 6
7 6 6 6 6 6 6 6
7 7 7 7 7 7 7 8

import java.util.*;
class Test 
{
	int n;
	Scanner sc;
	void readNumber()
	{
	    sc=new Scanner(System.in);
            n = sc.nextInt();
	}
	void printPattern()
	{                  
	    // need to write the logic 

	}
	public static void main(String[] args) 
	{
        Test t = new Test();
		t.readNumber();
		t.printPattern();
	}
}

multiply :: [Int] -> [Int]
multiply xs =
  -- [1,2,3]
  let
    accum y ys =
      case ys of
        [] ->
          y : 1 : []
        z : zs ->
          z * y : z : zs

    -- [1,1,2]
    fromLeft =
      List.reverse (List.drop 1 (foldl (flip accum) [] xs))

    -- [6,3,1]
    fromRight =
      List.drop 1 (foldr accum [] xs)

  in
    -- fixed number (3) of traversals of xs => O(n)
    List.zipWith (*) fromLeft fromRight

JavaScript solution:

function product(input) {
    let front = []
    let rear = []
    let output = []
    front[0] = 1
    rear[input.length - 1] = 1
    for (let i = 1; i < input.length; i++) {
        front[i] = front[i - 1] * input[i - 1]
    }
    for (let i = input.length - 2; i >= 0; i--) {
        rear[i] = rear[i + 1] * input[i + 1]
    }

    for (let i = 0; i < input.length; i++) {
        output[i] = front[i] * rear[i];
    }
    return output
}

I have not looked at all the solutions in this thread, but the ones I did look at had O(N**2) complexity metric. Below I offer 2 solutions: one naive O(N**2) and one that executes in O(N) time.

# input [2,3,1,4]
# output [12,8,24,6]
#
# Multiply all fields except it's own position.
#
# Restrictions:
# 1. no use of division
# 2. complexity in O(n)
#

# O(N**2) solution
def multiply_list_O_nn(l: list) -> list:
    res = [1] * len(l)
    for i in range(len(l)):
        for j in range(len(l)):
            res[i] *= l[j] if i != j else 1

    return res


# O(N) solution
def multiply_list_O_n(l: list) -> list:
    tree_mul_children = []
    tree_mul_others = []

    # First compute tree_mul_children
    last_row = l
    tree_mul_children.append(l)
    while len(last_row) > 1:
        new_row = []
        for i in range(0, len(last_row), 2):
            if i + 1 < len(last_row):
                s = last_row[i] * last_row[i + 1]
            else:
                s = last_row[i]

            new_row.append(s)
        tree_mul_children.append(new_row)
        last_row = new_row

    tree_mul_children.reverse()

    # Now compute tree_mul_others
    tree_mul_others.append([1])
    for i in range(1, len(tree_mul_children)):
        row = tree_mul_children[i]
        new_row = []
        for j in range(len(row)):
            mul_others = tree_mul_others[i - 1][j // 2] * row[(j % 2 + 1) % 2 + j // 2 * 2]
            new_row.append(mul_others)
        tree_mul_others.append(new_row)

    return tree_mul_others[-1]


print(multiply_list_O_nn([2, 3, 1, 4]))

print(multiply_list_O_n([2, 3, 1, 4]))

Just use modular arithmetic with a large prime. Instead of divide, multiply by the inverse mod(p).
1. Calculate tp = the total product mod p
2. For each x: x = tp * x^(p - 2) mod p
note: p must be picked larger than the largest result