What this code prints?

Question

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)

Answer 1

This looks more like a challenge than a question to me.

Please move this to your activity feed. Thanks!

Answer 2

Thanks Diego, I moved it in my activity feed.

Answer 3

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"