Hello Programmers, In this post, you will know how to solve the HackerRank Counting Valleys Solution. This problem is a part of the HackerRank Algorithms Series.
One more thing to add, don’t directly look for the solutions, first try to solve the problems of Hackerrank by yourself. If you find any difficulty after trying several times, then you can look for solutions.
HackerRank Counting Valleys Solution
Task
An avid hiker keeps meticulous records of their hikes. During the last hike that took exactly steps steps, for every step it was noted if it was an uphill, U, or a downhill, D step. Hikes always start and end at sea level, and each step up or down represents a 1 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 the sequence of up and down steps during a hike, find and print the number of valleys walked through.
Example
steps = 8 path = [DDUUUUDD]
The hiker first enters a valley 2 units deep. Then they climb out and up onto a mountain 2 units high. Finally, the hiker returns to sea level and ends the hike.
Function Description
Complete the countingValleys function in the editor below.
countingValleys has the following parameter(s):
- int steps: the number of steps on the hike
- string path: a string describing the path
Returns
- int: the number of valleys traversed
Input Format
The first line contains an integer steps, the number of steps in the hike.
The second line contains a single string path, of steps characters that describe the path.
Constraints
- 2 <= steps <= 106
- path[i] belongs to {U D}
Sample Input
8
UDDDUDUU
Sample Output
1
Explanation
If we represent _ as sea level, a step up as /, and a step down as \, the hike can be drawn as:
/\
\ /
\/\/
The hiker enters and leaves one valley.
HackerRank Counting Valleys Solution
Counting Valleys Solution in C
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int main() {
int n;
scanf("%i", &n);
char str[n];
scanf("%s", str);
int level = 0, result = 0, valley = 0;
for (int i = 0; i < n; i++) {
if(str[i] == 'U') {
level++;
if(level == 0 && valley) {
valley = 0;
result++;
}
}
else if(str[i] == 'D') {
if(level == 0)
valley = 1;
level--;
}
}
printf("%i", result);
return 0;
}Counting Valleys Solution in Cpp
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int l;
string str; cin>>l>>str;
int height = 0;
int count = 0;
for(int i=0;i<l;i++){
if (str[i]=='U') height++;
else {
if (height==0) count++;
height--;
}
}
if (height<0) count--;
cout<<count<<endl;
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
return 0;
}Counting Valleys Solution in Java
/* Programming Competition - Template (Horatiu Lazu) */
import java.io.*;
import java.util.*;
import java.lang.*;
import java.awt.*;
import java.awt.geom.*;
import java.math.*;
import java.text.*;
class ProblemB{
BufferedReader in;
StringTokenizer st;
public static void main (String [] args){
new ProblemB();
}
public ProblemB(){
try{
in = new BufferedReader(new InputStreamReader(System.in));
int N = nextInt();
String p = next();
int current = 0;
boolean start = false;
boolean prevUp = false; //UDDDUDUU
int mountains = 0;
int valleys = 0;
for(int x = 0; x < p.length(); x++){
if (p.charAt(x) == 'U'){
current++;
if (!start){
prevUp = true;
start = true;
}
if (current == 0){
valleys++;
}
}
else if (p.charAt(x) == 'D'){
current--;
if (!start){
prevUp = false;
start = true;
}
if (current == 0){
mountains++;
}
}
}
System.out.println(valleys);
}
catch(IOException e){
System.out.println("IO: General");
}
}
String next() throws IOException {
while (st == null || !st.hasMoreTokens())
st = new StringTokenizer(in.readLine().trim());
return st.nextToken();
}
long nextLong() throws IOException {
return Long.parseLong(next());
}
int nextInt() throws IOException {
return Integer.parseInt(next());
}
double nextDouble() throws IOException {
return Double.parseDouble(next());
}
String nextLine() throws IOException {
return in.readLine().trim();
}
}Counting Valleys Solution in Python
n = raw_input()
l = raw_input().strip().lower()
valleys = 0
level = 0
for i in xrange(len(l)):
if level == 0 and l[i] == 'd':
valleys += 1
if l[i] == 'u':
level += 1
else:
level -= 1
print valleysCounting Valleys Solution using JavaScript
function processData(input) {
var arr = input.split("");
var w = false;
var c = 0;
var l = 0;
for(var i =0; i < arr.length;i++) {
if(arr[i] == "U") {
l++;
} else if(arr[i] == "D") {
l--;
if(l == -1) {
c++;
}
}
}
console.log(c);
}
process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
_input += input;
});
process.stdin.on("end", function () {
processData(_input);
});Counting Valleys Solution in Scala
object Solution {
def main(args: Array[String]) {
scala.io.StdIn.readLine
val input = scala.io.StdIn.readLine
val res = input.foldLeft((0, 0)){ case ((level, count), c) =>
if (c == 'D') (level-1, if (level == 0) count+1 else count)
else (level+1, count)
}
println(res._2)
}
}Counting Valleys Solution in Pascal
(* Enter your code here. Read input from STDIN. Print output to STDOUT *)
uses math;
const fi='';
fo='';
var f:text;
res,n,i,j,right,left:longint;
c:char;
a:array[0..1000001]of longint;
//b:array[0..100001] of char;
begin
assign(f,fi);
reset(f);
res:=0;
readln(f,n);
a[0]:=0;
a[n+1]:=0;
for i:=1 to n do
begin
read(f,c);
if c='U' then a[i]:=a[i-1]+1;
if c='D'then a[i]:=a[i-1]-1;
end;
close(f);
left:=0;
right:=0;
{ for i:=1 to n-1 do
for j:=1+i to n do
if (a[i] = -1) and (a[i-1]=0) then
if (a[j] = -1) and ( a[j+1] =0 ) then inc(res);
}
for i:=1 to n-1 do
begin
if (a[i-1]= 0) and (a[i] = -1) then inc(left);
if (a[i]=-1 ) and (a[i+1]=0) then inc(right);
end;
assign(f,fo);
rewrite(f);
res:=math.min(left,right);
writeln(f,res);
close(f);
end.Disclaimer: This problem (Counting Valleys) is generated by HackerRank but the Solution is Provided by BrokenProgrammers. This tutorial is only for Educational and Learning purposes.
Next: HackerRank Queen’s Attack II Solution
