0

# What this code prints?

What will the following program print? Note that n is large in this case, making this code too slow. Try to come up with the answer without running the code. n = 1000 count = 0 for i in range(n): for j in range(n): for k in range(n): if i < j and j < k: count += 1 print(count)

27th Jan 2019, 6:12 PM
Bhanu Pratap Singh Bais + 7
This looks more like a challenge than a question to me. Please move this to your activity feed. Thanks!
27th Jan 2019, 6:30 PM
Diego 0
Thanks Diego, I moved it in my activity feed.
31st Aug 2019, 6:47 AM
Bhanu Pratap Singh Bais 0
Hi, I just saw this question on Coursera (Combinatorics & Probability). So, 166167000 is the answer I came up with, which is correct according to the grading system. Let's say n = 10. Then, subsets such that i< j < k follow this counting pattern: for i = 0: for j = 1 : [0, 1, 2], [0, 1, 3], ... [0, 1, 9] # 8 subsets. ... for j = 8: [0, 8, 9] # 1 subset. counter0 = 8 + 7 + ... + 1 for i = 1 for j = 2: [1, 2, 3], [1, 2, 4], ... [1, 2, 9] # 7 subsets. ... for j = 8: [1, 8, 9] # 1 subset. counter1 = 7 + 6 + ... + 1 ... # And so until counter7 = 1 Finally, recall 1 + 2 + ... + n = n * (n+1) / 2 . Then, counter0 + counter1 + ... + counter7 = 120 Then, applying the same logic for n = 1000, you should end up with this pattern: (998 + 997 + ... + 1) + (997 + 996 + ... 1) + (...) + (1) = 166167000 Notice that, with that apriori observation, you get this simplified code, which reduces O(n^3) to O(n): counter = 0 for i in range(998): counter += (999-i) * (998-i) / 2 Hopefully, I made myself clear enough. If it is not the case, consider the following Coursera's grading system feedback: "Exactly! Here we are counting all triples of different integers i,j,k such that 1 ≤ i < j < k ≤ 1000. It is the same as the number of ways of selecting three different integers out of 1000 since one can always arrange them in decreasing order. Thus, the answer is C(1000, 3) = 166167000"
13th Oct 2020, 5:05 AM
wmlzz