We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
The idea is like this:
Suppose given n sets and needed to select 2 elements from them such that both don't belong to same set(Here we need to find 3 such elements but I'll show for 2 to give the idea).
So say that the array A={5,2,3,4,10,7} stores the size of each set. # of sets=6 and A[0]=5 ie. we use 0-based indexing. Lets state the problem mathematically: We need sum of : i * j for all distinct pairs (i,j) where i and j belong to array A. You can do it in O(n * n) by 2 loops :
for(int i=0;i < A.length-1 ; i++){for (int j=i+1;j < A.length;j++) sum+= A[i][j];
What if , instead of 2 loops , we create another array B of same size and store in B[i] the sum of all elements from A[i] to A[A.length-1].
Kundu and Tree
You are viewing a single comment's thread. Return to all comments →
The idea is like this: Suppose given n sets and needed to select 2 elements from them such that both don't belong to same set(Here we need to find 3 such elements but I'll show for 2 to give the idea). So say that the array A={5,2,3,4,10,7} stores the size of each set. # of sets=6 and A[0]=5 ie. we use 0-based indexing. Lets state the problem mathematically: We need sum of : i * j for all distinct pairs (i,j) where i and j belong to array A. You can do it in O(n * n) by 2 loops :
for(int i=0;i < A.length-1 ; i++){for (int j=i+1;j < A.length;j++) sum+= A[i][j];
What if , instead of 2 loops , we create another array B of same size and store in B[i] the sum of all elements from A[i] to A[A.length-1].
Now we can write sum as:
for(int i=0;i < A.length-1; i++) sum+=(A[i] * B[i+1]);
We were multiplying and then summing ... by this way we sum first in one loop , then multiply in another loop!