There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i].

Full Question:

There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1]. Solve it without division operator and in O(n).

Simply, it can be solved in O(n²) time, by using double loop. For example,

int[] multiplicationExceptMe() {
int ret[N] = {1,};
for (int i=0; i < N; i++)
 for (int j=0; j < N; j++) {
  if(i != j)
     ret[i] *= A[j]
 }
return ret;
}

But, we have to solve in in O(n). The idea is to do multiply in both side (i.e. from start to end and from end to start) in each loop.

public static void main(String args[]) {
int input[] = {1, 2, 3, 4, 5};
int ret[] = {1,1,1,1,1};
int n = input.length, left=1, right=1;

for(int i=0; i <n; i++) {
ret[i] = ret[i]*left;  
ret[n-1-i] = ret[n-1-i]*right;
//after multiplication, set new left and right value
left *= input[i];
right *= input[n-i-1];
}

for (int i =0; i<n; i++)
System.out.print(ret[i] +"\t");
}

Obviously, it's O(n) time complexity.

Read More [...]

Posted in Big O, C, Google Interview Question, Interview Question, Java, MS interview Question, Programming, Time Complexity

Computation Complexity - Double Loop

Given a sorted array in descending order, following code counts pairs of two elements with the difference d. It is easy to give an O(n²) bound for the time complexity of the function countingDifference in below codes; n times in outer for-loop and n times inner while-loop.

But a more careful analysis shows that in fact we can give an O(2n) = O(n) bound on the time complexity of this functions.  The command j++; is executed no more than n times totally, while outer for-loop is looping n times.  So, time complexity of this function is O(n+n) = O(2n) = O(n). 

The statement 'this function(algorithm) is O(n²)' is still right. 'this algorithm is O(n)' gives more information about the function.

public class CodeTest {
static int counter1 =0;
static int counter2 =0;

public static void main(String[] args) {
int input[] = {112, 39, 34, 32, 30, 27, 12, 11, 9, 8, 5, 2, 0};
int d = 2;

System.out.print("Input: ");
for(int i = 0; i<input.length;i++)
System.out.print(input[i] + "  ");
System.out.println();
System.out.println( "For " + input.length + " -length array: " + countDiffernce(input, d) + " pairs are " + d + "-differences " );
System.out.println ("Outer Loop: " + counter1 + " times, Inner Loop: " + counter2 + " times");
}

public static int countDiffernce(int input[], int d) {
int cnt =0, n = input.length;
int j = 1;
for (int i = 0; i < n && j < n; i++) {
counter1++;
while ( (j < n-1) && (input[i] - input[j] < d)) {
counter2++;
j++;
}
if(input[i] - input[j] == d) {
cnt++;
System.out.println("\t" + input[i] + " - " + input[j] + " = " + d);
} 
}
return cnt;
}
}

Read More [...]

Posted in Big O, Computation Complexity, Java, Programming, Time Complexity