# Re: [JUG-Indonesia] Kode menarik

```Cara itu terkenal dengan nama Dynamic Programming.

```
Ini ada problem yang lebih menantang:

Diberikan array of integer A (0-based index).
Saya ingin mencari bilangan integer terkecil di array A dengan index
antara [i, j] (inclusive).
Jawabannya harus dalam O ( log N )

Jelas kalo looping dari i sampai j itu gak boleh karena itu O ( N ).

Kalau tertarik soal2 seperti itu, anda harusnya masuk Programming Contest.

FYI, Google suka orang2 yang tahu banyak algorithms ;)

Milis yang membahas Programming Contest di indo itu:

http://groups.yahoo.com/group/indo-algo

Tapi sepi nih... disini malah seru :D, bener2 aneh...

Felix Halim

On Fri, Jun 6, 2008 at 4:57 PM, Jecki Sumargo <[EMAIL PROTECTED]> wrote:
> 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
>>
>> 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 :)
>
> ------------------------------------
>
> Kalau mau keluar dari mailing list ini, caranya kirim sebuah email ke [EMAIL
> PROTECTED]
>
> Jangan lupa, website JUG Indonesia adalah http://www.jug.or.id
>