- vừa được xem lúc

The Solution of "Product of Array Except Self" under my thinking

0 0 15

Người đăng: Văn Lê Đình

Theo Viblo Asia

This post is just my thinking of the solution for the famous coding problem which is a problem #238 posted in Leetcode in which you can refer from here.

I will asume that you all have read and understood the requirement of this problem so I would not repeat it in this post.

Actually I write this post to enhance my skill of solving problems using my non-native language in writing (of course no marketing intended). So please forgive me if you may see this post without satisfaction or I will somehow show my weak explanation or mistakes. Much appreciation if you give some feedbacks to this post so that I can make this post better.

To think of this solution quickly, it is more likely to think of the nested loops which can easily solve the problem. But if you are in an interview session and you are asked to solve this problem. A solution like nested loops for this problem is not usually appreciated. Another better solution that I just have thought after researching prefix sum (I studied it again) 😄. This will be my beginning of the post. For example, this will be an input: [1, 2, 3, 4] and the output should be [24, 12, 8, 6]. Look at the input, how can I handle to have the expected output? Now it's time to adopt the prefix sum approach. But prefix sum would not work here, we should use "prefix product" (I named it) 😄.

So to use prefix product, aka accumulative product, I would introduce a new variable whose length is as same as the size of the input array. After handling the prefix product, the solution is 50% achieved. You can handle the prefix product by watching the steps and the implementation below.

  1. Introduce the output array variable out with the size is similiar to the one which is of the input array.
  2. Initialize the out variable with value 1 so that we can easily accumulate the sequential product.
  3. Make a loop to finally get a prefix product of the input array.
int[] out = new int[inp.Length];
out[0] = 1;
for (int i = 1; i < inp.Length; i++) { out[i] = out[i-1] * inp[i-1];
}

In the above implementation, you can figure out the big O notation in terms of time complexity and space complexity are both O(n). So that's it, O(n) is taken just to have a prefix product.

Now this will be the most difficult part which requires us to stay more focus. Only by doing some observation after having a prefix product can we realize a rule. When you know this rule, you have the key weapon to finalize this problem.

out[i] = a[0]. ... .a[i-1]
out[n-1] = a[0]. ... .a[n-2] (n is a size of the input array)
out[n-x] = a[0]. ... .a[n-x-1] (x is always smaller than n)

But do you realize that out[n-x] is missing its product from a range of inp[n-x+1] to inp[n-1]???

How can we solve that miss? Do we need something like a multiplier? A key is here, only by forming a multiplier which is the product from a range of inp[n-x+1] to inp[n-1] can we realize that we solved this problem.

The rest of the implementation is here:

  1. Make a reverse loop to form a multiplier and use it to multiple with the item which is missing its product result within a prefix product array.
int multiplier = 1;
for (int i = inp.Length - 1; i >= 0; i--) { out[i] = out[i] * multiplier; multiplier = multiplier * inp[i];
}

Again this would cost O(n) in terms of time complexity.

So in general, it takes only O(n) to solve this problem in terms of time complexity and space complexity. On the contradict, the brute force one would cost O(n^2).

Bình luận

Bài viết tương tự

- vừa được xem lúc

Thuật toán quay lui (Backtracking)

Quay lui là một kĩ thuật thiết kế giải thuật dựa trên đệ quy. Ý tưởng của quay lui là tìm lời giải từng bước, mỗi bước chọn một trong số các lựa chọn khả dĩ và đệ quy.

0 0 38

- vừa được xem lúc

Các thuật toán cơ bản trong AI - Phân biệt Best First Search và Uniform Cost Search (UCS)

Nếu bạn từng đọc các thuật toán trong AI (Artificial Intelligence - Trí tuệ nhân tạo), rất có thể bạn từng nghe qua về các thuật toán tìm kiếm cơ bản: UCS (thuộc chiến lược tìm kiếm mù) và Best First Search (thuộc chiến lược tìm kiếm kinh nghiệm). Khác nhau rõ từ khâu phân loại rồi, thế nhưng hai th

0 0 152

- vừa được xem lúc

Sử dụng vector trong lập trình C++ - giải bài toán lập trình muôn thủa

Chào buổi tối mọi người, hôm nay lang thang trên mạng bắt gặp bài toán quen thuộc một thời của quãng đường sinh viên IT. Đấy chính là câu số 1 trong đề thi dưới đây:.

0 0 35

- vừa được xem lúc

MÔ PHỎNG THUẬT TOÁN VƯƠNG HẠO TRONG PROLOG

. 1. Các luật suy diễn trong thuật toán Vương Hạo. Luật 1: Chuyển vế các giả thuyết và kết luận ở dạng phủ định. Ví dụ: p v q, !(r ^ s), !q, p v r -> s, !p <=> p v q, p v r, p -> s, r ^ s, q.

0 0 76

- vừa được xem lúc

A* Search Algorithm

What is A* Search Algorithm. How it works. . Explanation.

0 0 42

- vừa được xem lúc

Python: Jump Search

Search là một từ khóa khá là quen thuộc đối với chúng ta. Hiểu theo đúng nghĩa đen của nó chính là "Tìm kiếm".

0 0 35