Accolite software Interview Question Developer Program Engineers
Country: India
Interview Type: Phone Interview
public class NoDivide {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};
int len = arr.length, prod;
for (int i = 0; i < len; i++) {
prod = 1;
for (int j = 0; j < len; j++) {
if (j == i) continue;
prod *= arr[j];
}
System.out.println(prod);
}
}
}
Not the most efficient, but easily understood and convenient for a phone interview.
public class IntegerMulProblem {
static int[] arr={1,2,3,4,5,6,7};
static int[] resArray=new int[arr.length];
static int temp;
static int j=0;
static int result=1;
public static void main(String[] args) {
for(int i=0;i<arr.length;i++){
for(int k=0;k<arr.length;k++){
if(i==k){
temp=arr[k];
arr[k]=1;
}
result=result*arr[k];
}
arr[i]=temp;
resArray[i]=result;
System.out.println(resArray[i]);
result=1;
}
}
}
public class DivideBy {
public void ArrayOutput(int arr[]){
int output[]=new int[arr.length];
int multiply=1;
for(int i=0;i<arr.length;i++){
for(int j=0;j<arr.length;j++){
multiply=multiply*arr[j];
}
output[i]=divide(multiply,arr[i]);
multiply=1;
}
for(int i=0;i<output.length;i++){
System.out.println(output[i]);
}
}
public int divide(int dividend,int divisor){
int count=0;
int sign=1;
if(dividend<0){
dividend=-dividend;
sign=-sign;
}
if(divisor<0){
divisor=-divisor;
sign=-sign;
}
while(dividend>0){
dividend=dividend-divisor;
count++;
}
return (count*sign);
}
public static void main(String[] args) {
DivideBy divideBy=new DivideBy();
int arr[]={1,2,3,4,5};
divideBy.ArrayOutput(arr);
}
}
public class CarrierCupByShashi {
public static void main(String []args)
{
//take an input array first
int input[]={1,2,3,4,5};
int output[]=new int[input.length];
int mul=1;
//instead of calculating multiplication of whole array each time let do this
for(int i=0;i<input.length;i++)
{
mul*=input[i];
}
//now do the code for result array
for(int x=0;x<input.length;x++)
{
output[x]=divide(mul,input[x]);
}
//print res
for(int y=0;y<output.length;y++)
{
System.out.print(output[y]+" ");
}
}
private static int divide(int a, int b) {
// TODO Auto-generated method stub
boolean n = false;
if(b==0) return -1;
if(b==1) return a;
if(a<0)
{
n = true;
a = -a;
}
if(b<0)
{
n = true;
b = -b;
}
if(a<0 && b<0) n = false;
while(b!=1){
a = (a>>1);
b = (b>>1);
}
if (n)
return -a;
else
return a;
}
}
Similar to zortlord analysis but not recursive
public static int[] recalculateArray(int arr[]){
len = arr.length();
int[] result= new int[len];
int[] resultI= new int[len];
int[] resultD= new int[len];
//Basic case
resultI [0] = 1
resultI [1] = arr[0]
//multiply left side elements
for(int i = 2; i < len; i--){
resultI [i] = resultI [i-1] * arr[i-1]
}
//Basic case
resultD [len] = 1
resultD [len-1] = arr[len]
//multiply right side elements
for(int i =len-1; i => 0; i--){
resultD [i-1] = resultD[i] * arr[i]
}
for(int i =1; i < len; i++){
result[i] = resultI[i] * resultD[i]
}
return result
}
public static void main(String[] args) {
int arr[]={1,2,3,4,5};
int [] result = recalculateArray(arr);
}
#include <iostream>
#include <vector>
using namespace std;
vector<int> Calc(const vector<int>& arr)
{
vector<int> rv(arr.size(), 1);
int size = arr.size();
int prev = rv[0];
for( int i = 1; i < size; ++i )
{
rv[i] = prev;
prev *= arr[i];
}
prev = arr[size-1];
for( int i = size-2; i >=0 ; --i )
{
rv[i] *= prev;
prev *= arr[i];
}
return rv;
}
int main( int argc, const char* argv[] )
{
cout << "Hello World" << endl;
int x[] = { 1, 2, 3, 4, 5 };
vector<int> v(std::begin(x), std::end(x));
vector<int> rv = Calc(v);
return 0;
}
#include <iostream>
#include <vector>
using namespace std;
vector<int> Calc(const vector<int>& arr)
{
vector<int> rv(arr.size(), 1);
int size = arr.size();
int prev = rv[0];
for( int i = 1; i < size; ++i )
{
rv[i] = prev;
prev *= arr[i];
}
prev = arr[size-1];
for( int i = size-2; i >=0 ; --i )
{
rv[i] *= prev;
prev *= arr[i];
}
return rv;
}
int main( int argc, const char* argv[] )
{
cout << "Hello World" << endl;
int x[] = { 1, 2, 3, 4, 5 };
vector<int> v(std::begin(x), std::end(x));
vector<int> rv = Calc(v);
return 0;
}
#include<stdio.h>
#include<conio.h>
int main ()
{
int arr[] = {1,2,3,4,5};
int mul_for[6];
int mul_back[6];
int i;
mul_for[0] = 1;
mul_for[1] = arr[0];
for(i = 2; i<5 ; i++)
{
mul_for[i] = arr[i-1] * mul_for[i-1];
}
mul_back[4] = 1;
mul_back[3] = arr[4];
for(i = 2; i>=0 ; i--)
{
mul_back[i] = arr[i+1] * mul_back[i+1];
}
int temp;
for(i=0; i<5; i++)
{
temp = mul_for[i]*mul_back[i];
printf("%d ",temp);
}
}
#include<stdio.h>
#include<conio.h>
int main ()
{
int arr[] = {1,2,3,4,5};
int mul_for[6];
int mul_back[6];
int i;
mul_for[0] = 1;
mul_for[1] = arr[0];
for(i = 2; i<5 ; i++)
{
mul_for[i] = arr[i-1] * mul_for[i-1];
}
mul_back[4] = 1;
mul_back[3] = arr[4];
for(i = 2; i>=0 ; i--)
{
mul_back[i] = arr[i+1] * mul_back[i+1];
}
int temp;
for(i=0; i<5; i++)
{
temp = mul_for[i]*mul_back[i];
printf("%d ",temp);
}
}
O(n) time complexity
public int[] mutiply(int[] arr) {
int[] res = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
res[i] = 1;
}
int product = 1;
for (int i = 0; i < arr.length - 1; i++) {
product *= arr[i];
res[i + 1] *= product;
}
product = 1;
for (int i = arr.length - 1; i > 0; i--) {
product *= arr[i];
res[i - 1] *= product;
}
return res;
}
O(n) time complexity
public int[] mutiply(int[] arr) {
int[] res = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
res[i] = 1;
}
int product = 1;
for (int i = 0; i < arr.length - 1; i++) {
product *= arr[i];
res[i + 1] *= product;
}
product = 1;
for (int i = arr.length - 1; i > 0; i--) {
product *= arr[i];
res[i - 1] *= product;
}
return res;
}
O(n) time complexity
public int[] mutiply(int[] arr) {
int[] res = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
res[i] = 1;
}
int product = 1;
for (int i = 0; i < arr.length - 1; i++) {
product *= arr[i];
res[i + 1] *= product;
}
product = 1;
for (int i = arr.length - 1; i > 0; i--) {
product *= arr[i];
res[i - 1] *= product;
}
return res;
}
public class TestClass {
public static void main(String[] args) {
int[] a={1,2,3,4,5};
int[] b=new int[5];
for(int i=0;i<b.length;i++)
{
int temp=1;
for(int j=0;j<a.length;j++)
{
if((i+1)!=a[j])
{
temp=temp*a[j];
}
b[i]=temp;
}
}
for(int i=0;i<b.length;i++)
{
System.out.println(b[i]);
}
}
}
AS we can't multiply that number i.e we are avoiding divide .
public class TestClass {
public static void main(String[] args) {
int[] a={1,2,3,4,5};
int[] b=new int[5];
for(int i=0;i<b.length;i++)
{
int temp=1;
for(int j=0;j<a.length;j++)
{
if((i+1)!=a[j])
{
temp=temp*a[j];
}
b[i]=temp;
}
}
for(int i=0;i<b.length;i++)
{
System.out.println(b[i]);
}
}
}
int[] intArray=new int[5]{1,2,3,4,5};
List<int> intList = intArray.ToList();
int intMulOfList = 0;
foreach (int i in intList)
{
if (intMulOfList == 0)
intMulOfList = i;
else
intMulOfList = intMulOfList * i;
}
//Without using Divide(/) operator Divide Code.
foreach(int j in intList)
{
Expression divExp = Expression.Divide(Expression.Constant(intMulOfList), Expression.Constant(j));
Response.Write(Expression.Lambda<Func<Int32>>(divExp).Compile()()+" "+" ");
}
public class InputArrayQuest {
public double[] m1(double arr[]){
double temp [] = new double[arr.length];
double flag =1;
for(int i=0;i<arr.length;i++){
flag *=arr[i];
}
for(int i=0;i<arr.length;i++){
temp[i]=flag;
temp[i]/=arr[i];
}
return temp;
}
public static void main(String[] args){
double inputArray[] = {1,2,3,4,5};
double outputArray[] = new double[inputArray.length];
InputArrayQuest iaq = new InputArrayQuest();
outputArray =iaq.m1(inputArray);
for (int i =0;i<outputArray.length;i++){
System.out.println("out arrray val are "+outputArray[i]);
}
}
}
public class InputArrayQuest {
public double[] m1(double arr[]){
double temp [] = new double[arr.length];
double flag =1;
for(int i=0;i<arr.length;i++){
flag *=arr[i];
}
for(int i=0;i<arr.length;i++){
temp[i]=flag;
temp[i]/=arr[i];
}
return temp;
}
public static void main(String[] args){
double inputArray[] = {1,2,3,4,5};
double outputArray[] = new double[inputArray.length];
InputArrayQuest iaq = new InputArrayQuest();
outputArray =iaq.m1(inputArray);
for (int i =0;i<outputArray.length;i++){
System.out.println("out arrray val are "+outputArray[i]);
}
}
}
public class InputArrayQuest {
public double[] m1(double arr[]){
double temp [] = new double[arr.length];
double flag =1;
for(int i=0;i<arr.length;i++){
flag *=arr[i];
}
for(int i=0;i<arr.length;i++){
temp[i]=flag;
temp[i]/=arr[i];
}
return temp;
}
public static void main(String[] args){
double inputArray[] = {1,2,3,4,5};
double outputArray[] = new double[inputArray.length];
InputArrayQuest iaq = new InputArrayQuest();
outputArray =iaq.m1(inputArray);
for (int i =0;i<outputArray.length;i++){
System.out.println("out arrray val are "+outputArray[i]);
}
}
}
If you consider the division operation to simply be not multiplying with that value, then it could be considered that every index value would be the product of all values to the left and all values to the right:
That observation lends itself well to a recursive function with O(n) complexity and O(n) memory:
- zortlord December 18, 2014public static int[] setValues(int[] arr){ if(arr == null){ throw new NullPointerException(); } if(arr.length == 0){ throw new IllegalArgumentException(); } int[] results = new int[arr.length]; setValueRecur(arr, results, 0, 1); return results; } private static int setValueRecur(int[] arr, int[] results, int index, int productToTheLeft){ if(index == results.length){ return 1; } int productToTheRight = setValueRecur(arr, results, index+1, productToTheLeft* arr[index]); results[index] = productToTheLeft * productToTheRight; return productToTheRight * arr[index]); }