1 ~ n : n items
This is easy. You only need to read the last item's number to get the number of items.
8 ~ 11 : 4 numbers
11 - 8 = 3 numbers? WRONG!!!
Why? Subtraction = the number of spans between numbers, NOT a count of how many things
A span = distance or some quantity measure.
- 8am ~ 11am has 3 units (hours) of time
- 8cm ~ 11cm has 3 units (cm) of distance
8 ~ 11 floors means we are counting the number of things in the range, not the magnitude of the range.
Conclusion 1 : Two ways to Count! "Number of things in the range" vs "Magnitude of the range"
- first type of counting : b - a + 1
- second type of counting : b - a
The Fencepost Problem:
You are building a fence 100ft long, with fence posts every 10ft. How many posts do you need?
Using our newly found framework, we can think of the problem this way.
This fence needs ten 10ft spans. But we need the number of posts, which is actually the first type of counting. We need one extra.
Hence, we need 11 posts.
Days Worked : April 8th ~ April 13th = 6 days (first type)
Hours/Min/Seconds : 4am ~ 6am = 2 hours (second type)
Credits to https://betterexplained.com/articles/learning-how-to-count-avoiding-the-fencepost-problem/
|How to Count - Number of Ways (경우의 수) (0)||2018.04.26|
|How to Count (The Fencepost Problem) - Off by One Errors! (0)||2018.04.26|
|Proof by Induction on Graphs - Why You Should Always Remove a Vertex (0)||2018.01.07|
|How to Design - Case by Case (0)||2017.12.18|
|How to Iterate over a fixed range of integers (0)||2017.12.15|
- Proof of Correctness
- Two Pointer