Problem - Difference Between Square of Sums and Sum of Squares

diketahui sebuah persoalan dimana kita diperlukan untuk mencari perbedaan antara nilai dari kuadrat atas penjumlahan angka dari 1 ke N dan nilai dari jumlahan dari angka 1 ke N yang dikuadratkan, dimana N adalah bilangan asli. apabila ditulis dalam notasi matematika, kita mencari hasil dari (Σn)² - (Σn²).

masalah ini dapat diselesaikan menggunakan dua pendekatan:

• brute force O(N)
• pendekatan yang lebih efisien O(1)

Brute force#

dengan pendekatan ini, kita akan melakukan looping untuk melakukan penjumlahan yang kemudian hasilnya kita proses kembali.

masukkan: N adalah bilangan asli

definisikan SUM dengan nilai awal nol
definisikan SUM_OF_SQUARE dengan nilai awal nol

untuk setiap nilai I dari satu hingga N:
  SUM ditambahkan dengan I
  SUM_OF_SQUARE ditambahkan dengan hasil pangkat 2 dari I

keluaran: SUM dikali SUM dikurangi SUM_OF_SQUARE

apabila kita implementasikan dengan Zig, maka akan menjadi:

pub fn differenceOfSquare(number: usize) usize {
  var sum: usize = 0;
  var sumOfSquare: usize = 0;

  for(1..number+1) |i| {  // for loop Zip is exclusive at the end
    sum += i;
    sumOfSquare += i*i;
  }

  return sum*sum - sumOfSquare;
}

karena ada for loop di situ, maka proses dilakukan sebanyak N kali.

Pendekatan Optimal#

pendekatan yang lebih optimal dilakukan dengan mengetahui sifat dari soal itu sendiri. dimana kita melakukan penyerderhanaan persamaan. mari kita lihat sebuah fungsi F(N) yang merupakan jumlahan dari angka 1 hingga N dan G(N) yang merupakan jumlahan dari angka 1 hingga N yang dikuadratkan.

F(N) = 1 + 2 + 3 + ... + N

yang apabila ditulis dengan dibalik, akan menjadi:

F(N) = N + (N-1) + (N-2) + ... + 1

ini menarik karena dua bentuk F(N) memiliki pola ketika disandingkan. yaitu setiap nilai pada index akan membuat persamaan N+1.

F(N) = 1 +   2   +   3   + ... + N
F(N) = N + (N-1) + (N-2) + ... + 1
-----------------------------------(+)
2*F(N) = (N+1) + (N+1) + (N+1) + ... + (N+1) = N * (N+1) / 2

kita dapat menyerderhanakan F(N) = Σn = N * (N+1) / 2. tidak perlu loop. dengan menggunakan pendekatan yang sama, kita dapat lakukan penyerderhanaan pada G(N).

pendekatan penyerdehanaan G(N) berakar atas persamaan kubik sebuah polinomial.

a^3 - b^3 = (a - b)(a^2 + ab + b^2)

apabila nilai a kita ganti menjadi n dan b menjadi n-1 terus menerus hingga a bernilai 1 dan b menjadi 0, maka kita akan mendapatkan hubungan dengan penyerderhanaan fungsi G(N).

H(N) = n^3 - (n-1)^3 = (n - (n-1))[(n^2) + (n*(n-1)) + (n-1)^2]
H(N) = n^3 - (n-1)^3 = 3n^2 - 3n + 1

H(N-1) = (n-1)^3 - (n-2)^3 = 3(n-1)^2 - 3(n-1) + 1
H(N-2) = (n-1)^3 - (n-2)^3 = 3(n-1)^2 - 3(n-1) + 1
...
...
H(2) = 2^3 - 1^3 = 3(2)^2 - 3(2) + 1
H(1) = 1^3 - 0^3 = 3(1)^2 - 3(1) + 1

apabila seluruh fungsi H dijumlahkan dari 1 hingga ke N, maka akan menjadi G(N). kita dapat melihat pola yang dapat menjadi 0 ketika dijumlahkan.

H(N) = n^3 - (n-1)^3 = 3n^2 - 3n + 1

H(N-1) = (n-1)^3 - (n-2)^3 = 3(n-1)^2 - 3(n-1) + 1
H(N-2) = (n-1)^3 - (n-2)^3 = 3(n-1)^2 - 3(n-1) + 1
...
...
H(2) = 2^3 - 1^3 = 3(2)^2 - 3(2) + 1
H(1) = 1^3 - 0^3 = 3(1)^2 - 3(1) + 1
-----------------------------------------------------------------+
G(N) = ΣH(N) = n^3 = 3Σn^2 - 3Σn + n
G(N) = 3Σn^2 = n^3 + 3(n(n+1))/2 + n
G(N) = Σn^2 = [n(n+1)(2n+1)]/6

setelah kita mendapatkan fungsi F(N) dan G(N), kita dapat mengimplemtasikannya ke dalam kode.

pub fn differenceOfSquare(number: usize) usize {
  var sum: usize = 0;
  var sumOfSquare: usize = 0;

  for(1..number+1) |i| {  // for loop Zip is exclusive at the end
    sum += i;
    sumOfSquare += i*i;
  }

  return number * (number+1) / 2 - number * (number+1) * (2*number+1) / 6;
}

hasilnya akan sama dengan menggunakan O(1) operasi.

Dah.#

sering kali untuk melakukan peningkatan performa kita harus memahami pola dan karakter sebuah persoalan. seperti penjumlahan ini yang ternyata dapat dihubungkan dengan sebuah persamaan binominal. yah walaupun dalam pekerjaan sehari-sehari penulis sangat cukup menggunakan for-loop.

sampai bertemu di post lain.