Short Problem Definition:
Gary is an avid hiker. He tracks his hikes meticulously, paying close attention to small details like topography. During his last hike he took exactly n steps. For every step he took, he noted if it was an uphill, U, or a downhill, D step. Gary’s hikes start and end at sea level and each step up or down represents a 1 unit change in altitude.
Link
Complexity:
time complexity is O(N)
space complexity is O(1)
Execution:
All is required is a simple counter.
I find this problem specification oddly satisfying since I am currently finishing off my list of 48 4000 footers in New Hampshire, US.
Solution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#!/bin/python n = input () s = raw_input () level = 0 valleys = 0 for direction in s: if direction = = "U" : level + = 1 if level = = 0 : valleys + = 1 else : level  = 1 print valleys 