Nested Array loop iterations

Question

I was trying to understand the solution to this problem. The question is to see if any three numbers in an array return a certain value. This answer is what I found online.

public bool numberequal(int sum, int[] array) { int i, k, j; bool answer = false; for (i = 0; i < array.Length - 2; i++) { for (k = i + 1; k < array.Length - 1; k++) { for (j = k + 1; j < array.Length; j++) { if (array[i] + array[k] + array[j] == sum) { answer = true; return true; } } } } return answer; }

My questions was for the i iteration of the first loop have -2 on array.length. The second k iteration has -1 as well. Could someone be kind enough to explain why? Don't we need to loop over every element to get the correct answer?

Try to run it line-by-line in a debugger and you should understand why it is correct. — user202729
– user202729, Commented Feb 24, 2018 at 15:34

Mark Benningfield · Accepted Answer · 2018-02-24 17:11:23Z

When you have a loop structure that you don't understand, sometimes it's clearer if you print the loop iterations as they execute. This can make it easier to satisfy yourself about how the loop progresses. If you modify the function just a little bit to just concentrate on the loops themselves (and change the type so the values are more easily discernible), like so:

// call this with "ABCDEFGH".ToCharArray() public void LoopWriter(char[] array) { for (int i = 0; i < array.Length - 2; i++) { for (int k = i + 1; k < array.Length - 1; k++) { for (int j = k + 1; j < array.Length; j++) { Console.WriteLine("{0}-{1}-{2}\n", array[i], array[k], array[j]); } } } }

The output makes it easier to trace the execution for each loop.

A-B-C A-B-D A-B-E A-B-F A-B-G A-B-H A-C-D A-C-E A-C-F A-C-G A-C-H A-D-E A-D-F A-D-G A-D-H A-E-F A-E-G A-E-H A-F-G A-F-H A-G-H B-C-D B-C-E B-C-F B-C-G B-C-H B-D-E B-D-F B-D-G B-D-H B-E-F B-E-G B-E-H B-F-G B-F-H B-G-H C-D-E C-D-F C-D-G C-D-H C-E-F C-E-G C-E-H C-F-G C-F-H C-G-H D-E-F D-E-G D-E-H D-F-G D-F-H D-G-H E-F-G E-F-H E-G-H F-G-H

The interesting bit is here at the very bottom. You can see that the last iteration checks the last 3 items in the array. Since each inner loop indexes itself from the position of its immediate outer loop, the 2 outer loops have to be "stopped short", or the addition will take the inner loops past the end of the array. That's why the outer loops are limited to Length - 2 and Length - 1, respectively.

Artak · Accepted Answer · 2018-02-24 15:46:34Z

It's done to exclude selection of the same number (at the same index) more than once, when the loop will get to the end. Think about the triplet of the selected numbers. The first one shouldn't really be the last two indexes, as that case is already covered by a different combination, where the third number is the last element of the array. Same applies to the second index of the triplet .

Collectives™ on Stack Overflow

Nested Array loop iterations

2 Answers 2

Comments

1 Comment

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Related