This was taken March 18, 2020, two days into the Philly work from home order
with most restaurants converting to take out only
Reading Terminal Market, Philly. March 2020
This seems like a suspiciously easy problem. It involves finding the number of times a value appears in a multiplication table
From the problem it does seem evident that we will need a nested loop that traverses the table and looks for occurrences. The inner loop would be responsible for determining if a product exists that matches X. The following diagram is my initial algorithm, however after thinking about it some more I realized that it could be further optimized by skipping the inner loop
Solving it
- Initialize a count variable
- The outer loop needs to traverse all values between 1 to N
- The inner loop though, is different, we can traverse in the reverse order N to 1
- This will allow us to short circuit the inner loop if the product at that position is less than the value we are looking for
- On the other hand if we encounter a product that matches the value we are looking for we can increment the count and terminate the inner loop
- At the end of the nested loop operation, we have the result in our count variable
Optimization
We can skip the inner loop with a simple mathematical test
if X mod i == 0 and X < i * N
- The Value we are looking for should be divisible by the current row that we are on
- And, The Value should be in range since this is a N by N multiplication table after all
