Programming Geek
Rated 4.1/5 based on 446 reviews

Evernnote Coding Challenge

Recently I took Evernote coding challenge powered by Interviewstreet. Here goes one of the problem of the contest.

Given a list of integers, your task is to write a program to output an integer-valued list of equal length such that the output element at index 'i' is the product of all input elements except for the input element at 'i'.
In other words, let inputArray by an integer array of length 'n'. The solution,computed into outputArray, would be:
for each j from 1 to n-2:
outputArr[ j ] = inputArray[0] * inputArray[1] * inputArray[2] * ... * inputArray[j-1] * inputArray[j+1] * inputArray[j+2] *...* inputArray[n-1]
for j = 0
outputArray[0] = inputArray[1] * outputArray[2] * ... * outputArray[n-1]
for j = n-1
outputArray[n-1] = outputArray[0] * outputArray[1] * outputArray[2] * ... * outputArray[n-2]
As an example, if inputArray = { 1, 2, 3, 4 }, then
outputArray = { 2*3*4, 1*3*4, 1*2*4, 1*2*3 }.
Your program should run in O(n) time and should be space efficient.

Input format

First line of input contains N , number of elements in list.
Next N lines will each contain an element (a signed integer)

Output format

Print the output list of numbers.

Sample input

4
5
2
2
3

Sample output

12
30
30
20

Constraint

You may assume that:
  • The input array size will always have at least two elements in it, that is, n >= 2.
  • The product of any subset of the input will never exceed the value of a 64 bit integer.
  • The maximum length of input array is 1000.
My Solution for this problem:
import java.util.Scanner;

/**
*
* @author VIK
*/
public class Solution {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int n = n=sc.nextInt();;
		int flag=0;
		int[] arr = new int[n];
		long mul = 1;
		for (int i = 0; i < arr.length; i++) {
			
			arr[i] = sc.nextInt();
			if(arr[i]==0)
			flag++;
			if(arr[i]!=0)
			mul *= arr[i];
		}
		for (int i = 0; i < arr.length; i++) {
			
			if(flag >0)
			
			if(arr[i]==0)
			if(flag>1)
			System.out.println(0);
			else
			System.out.println(mul);
			else
			System.out.println(0);
			else
			System.out.println(mul/arr[i]);
		}
		
	}
}