On Fri, Jun 6, 2008 at 3:16 PM, naray citra <[EMAIL PROTECTED]> wrote: > Gw dapet cuplikan kode menarik neh, untuk share aja, sapa tau ada yang butuh > :D > sumber : http://linkmingle.com/details/865 > > There is an array A[N+1] of N integers. You have to compose an array > Output[N+1] such that Output[i] will be equal to the productof all the > elements of A[] except A[i]. > Example: > INPUT:[4, 3, 2, 1, 2] > OUTPUT:[12, 16, 24, 48, 24] > > Solve it without division operator and in O(n) with out using division > > import java.util.Arrays; > > public class PArray { > > public int[] PSub(int[] inp){ > int[] out = new int[inp.length]; > out[0]=1;out[1]=inp[0]; > for (int i = 2; i <inp.length ; i++) > out[i] = inp[i-1]*out[i-1]; > int P = 1; > for(int i=inp.length-2;i>=0;i--){ > P*=inp[i+1]; > out[i]=out[i]*P; > } > return out; > } > public static void main(String[] args) { > PArray pArray = new PArray(); > int in[] = new int[]{4,3,2,1,2}; > System.out.println("INPUT:"+ > Arrays.toString(in)); > System.out.println("OUTPUT:"+ > Arrays.toString(pArray.PSub(in))); > } > } >
Wah ini hasilnya O(n) ato ga ya? Dilihat2 sepertinya ini O(n^2) soalnya ada inner loop yg jumlahnya mendekati n. CMIIW. Seru juga. Masih blom ketemu caranya nih :)