Programming: Whiteboard Solutions – has12
Updated: Feb 26, 2019
A student asked me for help with a logic problem he was struggling with today that dealt with arrays and loops. The prompt was as follows: Given an array of ints, return true if there is a 1 in the array with a 2 somewhere later in the array. His initial attempt at solving the challenge was close, but he was missing one key component that many students of programming tend to struggle with initially.
His initial code looked like this:
His for loop looked good, he was properly iterating through the length of the array, he was accessing the elements in the array for each iteration of the loop correctly. Overall, a solid attempt.
What he missed, however, was the need to check if the array contained a 2 anywhere after containing a 1. Instead, the code above checks to see if any given element in the array is both 1 and 2, which is impossible as a the int cannot be both numbers at the same time. What needs to happen, is we need to check for an element to be 1 first, then, if we find a 1, we need a way to remember that we’ve found a 1 so that we can look for a 2 from that point to the end of the array. What’s something we could use to say whether we’ve found a 1 yet or not? Hmmm… well, any time we need to store any kind of data, we will need a variable; the question though, is what data type should this variable be? What data type can represent whether something has been found or not? It seems like there are only two possible values for this variable, found or not found… hopefully the picture is starting to get clearer. What data type can only hold two values, each the opposite of the other? Boolean!
We can create a boolean variable, let’s call it has1 and set it equal to false to start (because before we iterate through the array we have not found 1 yet). Then, as we iterate through the array, we can check if each element in the array is a 1 with a conditional if statement. If an element is 1, we can flip the switch on our boolean has1 and set it to true so that we now know, going forward, that we have found a 1. Then, we can check for any of the remaining elements to be 2 by just adding another condition. If we find a 2 now, we can return true. If we don’t find a 2 after the 1, or if we don’t find a 1 at all, then we can return false outside the loop. What this does is if the loop never returns true, meaning the 1 and 2 were never found in that order, then we return false.
Here is what the code could look like:
Notice how we are checking for 1 first, and if the number is not 1 we are checking to see if we have already found a one and if the current number is 2 with has1 && nums[i] == 2.
Remember, if you need your program to “remember” something – use a variable. Think about what it is that your program needs to remember and what values that piece of data could be represented as, and pick the best data type to represent it. If the data you need to remember is a simple switch, either something has or has not, or is or is not, then boolean is your friend!