'Counting valleys question from hacker rank
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 steps. For every step he took, he noted if it was an uphill, , or a downhill, step. Gary's hikes start and end at sea level and each step up or down represents a unit change in altitude. We define the following terms: A mountain is a sequence of consecutive steps above sea level, starting with a step up from sea level and ending with a step down to sea level. A valley is a sequence of consecutive steps below sea level, starting with a step down from sea level and ending with a step up to sea level. Given Gary's sequence of up and down steps during his last hike, find and print the number of valleys he walked through. For example, if Gary's path is , he first enters a valley units deep. Then he climbs out an up onto a mountain units high. Finally, he returns to sea level and ends his hike.
Function Description Complete the countingValleys function in the editor below. It must return an integer that denotes the number of valleys Gary traversed.
I have tried writing this code in python and it runs well but cannot figure out a code logically
#n is the number of steps and s is the sequence of steps taken
def countingValleys(n, s):
level=valley=0
for i in range(n):
if(s[i]=='U'):
level+=1
if(level==0):
valley+=1
else:
level-=1
return valley
Results are fine
Questions: Can someone explain me the logic starting from if(level==0). If we increase the level by one unit when the person moves uphill, shouldn't we increase valley by 1 then. Why should valley increase by one when level is zero. Confused about the logic- can someone please help me understand this
Solution 1:[1]
Does
level=0 valley=0
make any difference, they both are similar level=valley=0
The logic is simple you just have to count if the no if "U"-uphill assigned as '1' and number of 'D'-Downhills assigned as '-1' and on adding the both count one should get '0' as in [DDDUUU] which will increment valley by '1'.
Solution 2:[2]
If the step is uphill if(s[i]=='U')
And the level is 0 if(level==0)
Then it is a valley valley+=1
The function works by counting the valleys when you come out of them, and it tells that you come out of them because you reach the sea level giving an uphill step.
Solution 3:[3]
Its simple,
What the code means is, if you have encountered an up symbol it means you have climbed. Now if you have climbed from plane or mountain your level would be greater than 0. But if you have climbed from a valley to level then only your level would become 0.
basically if level<0 it means you are still in valley, level>0 means you are in mountain, level 0 means you are in sea level.
So if you have encountered a up symbol denoting climb action and then your level is 0 that means you have climbed up a valley that's all.
Solution 4:[4]
We can assign values to uphill and downhill as uphill=1, downhill=-1 and sea level=0 and as valley can be defined as when we reached the sea level from downhill, i.e from a negative value to zero
so if we are at a negative level and moving to sea level by adding the next step we can increment the valley.
Find the code snippet below
def returnCode(step):
if step=='U':
return 1;
return -1;
def countingValleys(steps, path):
# Write your code here
level=valley=0
for element in path:
code = returnCode(element)
if level< 0 and level+code == 0:
valley=valley+1
level = level+code
return valley
Solution 5:[5]
When level=0 Gary has reached sea level meaning he has covered a valley
Solution 6:[6]
Javascript Solution:
function countingValleys(steps, path) {
var altitude = 0;
var numberOfValleys = 0;
path.split('').forEach(step => {
if(step === 'U'){
altitude ++;
if(altitude === 0){
numberOfValleys++;
}
}else{
altitude--
}
})
return numberOfValleys;
}
Solution 7:[7]
Counting valley hacker solution in php
function countingValleys($steps, $path) {
$valley = 0;
$sealevel = 0;
$newPath = str_split($path);
$c = count($newPath);
if ($steps == $c && $c >= 2) {
for($i = 0; $i < $c; $i++) {
if ($newPath[$i] == "D") {
$sealevel -= 1;
} else {
$sealevel += 1;
}
if ($sealevel == 0 && $newPath[$i] == "U") {
$valley += 1;
}
}
return $valley;
}
}
Solution 8:[8]
Track the altitude. Any time you return back to sea-level and you came from below, you know you've found a valley. Keep count of these finding.
Time-complexity: O(steps)
Space-complexity: O(steps)
Java 8
public static int countingValleys(int steps, String path)
{
int altitude = 0; // 0 = sea-level
int countedValleys = 0;
//Loop through path evaluating each change in altitude
for(char altChange: path.toCharArray())
{
//'U' increases altitude. Otherwise, decrease altitude ('D')
altitude = altChange == 'U' ? altitude + 1 : altitude - 1;
//If you've reached sea-level and you came from below, you've found a valley
if(altitude == 0 && altChange == 'U')
countedValleys++;
}
//Return count of found valleys
return countedValleys;
}
Solution 9:[9]
#JavaScript(Nodejs) solution
function countingValleys(steps, path) {
// Write your code here
let a = Array.from(path);
let valleys=0;
let pos=0;
let prevpos=0;
for(let i=0;i<a.length;i++){
if(a[i]==='U'){
prevpos=pos++;
if(pos===0){
valleys++;
}
}
else
{
prevpos = pos--;
}
}
return valleys;
}
Solution 10:[10]
you can try this code with go
func countingValleys(steps int32, path string) int32 {
// Write your code here
var lv int;
var count int32;
var lembah bool;
for i := 0; i< int(steps); i++{
if path[i]== 'U' {lv ++;}else if path[i]== 'D'{lv--}
if lv<0 {lembah = true}
if lembah {
if(lv>=0){
count ++;
lembah = false;
}
}
}
return count;
}
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow