Lesson 1

Welcome to a delightful lesson on **array traversal**! Today, we invite you to join an endearing bunny named Gloria on an intricate quest. Gloria has a soft spot for number games, especially when they involve hopping between arrays. Our goal on this exciting journey is to assist Gloria through her escapade and identify the maximum value she encounters along the way. Are you ready to embark on this adventure?

Gloria's quest unfolds with two arrays, both brimming with non-negative integers. Starting at the first element of `arrayA`

, she leaps to `arrayB`

based on the index she discovers in `arrayA`

. She then bounces back to `arrayA`

according to the index she stumbles upon in `arrayB`

. Gloria repeats these hops until she returns to where she started in `arrayA`

. What an adventure!

Your challenge is to craft a C++ function that aids Gloria on her trip. The function will take two arrays of integers as inputs, representing `arrayA`

and `arrayB`

. The objective is to find the highest value from `arrayB`

that Gloria jumps to during her voyage.

It is guaranteed that at some point Gloria returns to the starting position.

**Example**

If `arrayA = {2, 4, 3, 1, 6}`

and `arrayB = {4, 0, 3, 2, 0}`

, the output should be `3`

.

In this scenario, Gloria starts from the first element of `arrayA`

, which is `2`

. Then, she jumps to `arrayB`

at index `2`

, where she discovers `3`

. She then bounces back to `arrayA`

at index `3`

, where she arrives at `1`

. From there, she leaps back to `arrayB`

at index `1`

, stumbling upon a `0`

. Finally, she bounces back to `arrayA`

at index `0`

, the location where she started her adventure. Hence, she stops here. During this journey, she encountered the highest value `3`

from `arrayB`

.

Before we make headway with our code, let's kickstart with the initialization of variables. Let `indexA`

and `indexB`

denote the last positions of Gloria in `arrayA`

and `arrayB`

, respectively. We will also use `max_value`

for tracking the highest value encountered in `arrayB`

. Her quest starts from `arrayA`

, so we also maintain a Boolean flag `in_arrayA`

.

C++`1int indexA = 0; 2int indexB = -1; 3bool in_arrayA = true; 4int max_value = INT_MIN;`

Our assistant for Gloria’s hopping challenge will be a `while`

loop! This keeps iterating until Gloria returns to her starting position in `arrayA`

.

If Gloria is in `arrayA`

, we check if the value in `arrayB`

where she is going to land is greater than `max_value`

and update `max_value`

if it is. We also switch Gloria's position to the other array in each iteration.

C++`1while (true) { 2 if (in_arrayA) { 3 indexB = arrayA[indexA]; 4 if (arrayB[indexB] > max_value) { 5 max_value = arrayB[indexB]; 6 } 7 } else { 8 indexA = arrayB[indexB]; 9 if (indexA == 0) { 10 return max_value; 11 } 12 } 13 in_arrayA = !in_arrayA; 14}`

Collecting all the pieces together, here’s our ultimate function:

C++`1#include <iostream> 2#include <climits> // For INT_MIN 3#include <vector> 4 5int solution(std::vector<int> arrayA, std::vector<int> arrayB, int sizeA, int sizeB) { 6 int indexA = 0; 7 int indexB = -1; 8 bool in_arrayA = true; 9 int max_value = INT_MIN; 10 11 while (true) { 12 if (in_arrayA) { 13 indexB = arrayA[indexA]; 14 if (arrayB[indexB] > max_value) { 15 max_value = arrayB[indexB]; 16 } 17 } else { 18 indexA = arrayB[indexB]; 19 if (indexA == 0) { 20 return max_value; 21 } 22 } 23 in_arrayA = !in_arrayA; 24 } 25} 26 27int main() { 28 std::vector<int> arrayA = {2, 4, 3, 1, 6}; 29 std::vector<int> arrayB = {4, 0, 3, 2, 0}; 30 int sizeA = arrayA.size(); 31 int sizeB = arrayB.size(); 32 33 std::cout << "Maximum value encountered in arrayB: " << solution(arrayA, arrayB, sizeA, sizeB) << std::endl; 34 35 return 0; 36}`

Heartiest congratulations on guiding Gloria through her array-hopping adventure. Not only have you heightened Gloria's joy, but you've also skillfully solved a complex task. You've deftly handled arrays, tracked indices, and made careful use of conditional statements.

This experience should empower you to take on more complex coding challenges. Keep practicing, keep exploring, and keep growing. Happy coding!