We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
We only care about the number of valleys...
So just figure out the number of times you came back up to sea level.
publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intn=sc.nextInt();Strings=sc.next();intv=0;// # of valleysintlvl=0;// current levelfor(charc:s.toCharArray()){if(c=='U')++lvl;if(c=='D')--lvl;// if we just came UP to sea levelif(lvl==0&&c=='U')++v;}System.out.print(v);}
The problem statement says consecutive steps below sea level. Does this solution work for 4 DUDU or does it return 1? Based on the problem statement that input should return 0.
Edit: I removed the condition to check that the previous step was also below sea level and all the tests passed. However, this no longer matches the definition of a valley "consecutive steps below sea-level"... unless I am misunderstanding the implied multiplicity in the word consecutive.
I think the word consecutive is misleading here. Think about it, the number of valleys is just the number of times you went down below sea level and back up again. Every time it starts at sea level and goes down then back up to sea level, that is a valley. It doesn't need the word 'consecutive' in there.
I totally agreed. When I analyse the test case and even I manually count the number of valleys and I also got the different answer from the test case. The word "consecutive" makes me think it needs at least two "D" to start with. I strongly reccommend to remove the word "consecutive" which is misleading!
Yes, the word "consecutive" make me lost about 3 hours trying to understand where I was wrong. So, removing the constraint that I was considering (at least 2 steps below sea level), makes all test pass
Totally agree with you, consecutives steps down means at least 2 steps down. It means 1 step down from sea level than 1 step up is not a valley according to the description.
Completely agree!!! The word 'consecutive' is misleading and if I have not had a look in the discussion tab, I would have never known about this. Thanks guys!!!
Entirely misleading wording. It is assumed you need two "D" steps from sea level in order for a valley to start. They obviously include DUDU as two separate valleys.
I think you are right.* "A valley is a sequence of consecutive steps below sea level, "* to me, means Gary took two or more steps below sea level.
Problem description is misleading.
Because at the end of the journey, the hiker will always return to sea level. So if you check every time the hiker goes back to sea level, and in this case, if the hiker comes from below, it means that the hiker went through a valley on the last walk.
Yes, I think the word "consecutive" is misleading; it threw me off as well.
One could argue it doesnt say "consecutive steps down". Unlocking one of the test case helped clear the doubt for me though.
I think that if we consider that for making even an only one-level-deep valley we need two consecutives steps (D and U) below sea level, there is no problem with the description.
In other words, if we take into account only where (above/below sea level) the steps themselves took place (and not wheter they are uphill or downhill, nor what are their starting or edning points) to classify them as being above or below sea level, the tests match with the statement:
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.
I think if we take into account only where (above/under sea level) the steps themsleves took place (not wheter they are downhill or uphill) to classify them as being above or under sea level, the tests match with the statement:
A valley is a sequence of consecutive steps below sea level, (...)
In other words, I think we sould consider where the "body" of each step is to solve this problem.
Exactly, I also was stuck because of the definition-'consecutive steps below sea-level'.. After seeing the solution here, I also thought of the same situation with case DUDU.
And if a move up while current level is 0 counts as a valley, then a move down while current level is 0 should also work as a solution, but it doesn't.
d[i] is value not key.
The logic is brilliant. a is taking the sum of the consequitive steps of the path.So, after decending a valley if someone ascending to sea level then a=0 and if again it is negative that means new valley is explored so b will be increased 1 otherwise no change.
Nice try but i know how it looks when u r at the begginer level of coding and all other are giving answers like one line python code and very small code
#include<stdio.h>intmain(){intn;scanf("%d",&n);intj=0,i=0,cnt=0;chara[n];// INPUT THE STEPSfor(j=0;j<n;j++){scanf("%c",&a[j]);}for(j=0;j<n;j++){if(a[j]=='U'){i=i+1;if(i==0)cnt++;}elseif(a[j]=='D'){i=i-1;}}printf("%d",cnt);return0;}
I've implemented the same logic as yours...
Still it does not pass many testcases.
Please help
#include<iostream>#include<cstddef>intmain(){std::size_tn;std::cin>>n;intsea_level=0,Ans=0;while(n--){charinput;std::cin>>input;input=='U'?++sea_level:--sea_level;// else case is reductant heresea_level==0&&input=='U'?++Ans:Ans;}std::cout<<Ans<<std::endl;return0;}
In the third if condition, we are checking if we returned to sea level (0) from a valley by moving upwards (U). So we are verifying and incrementing the answer with respect to these 2 parameters
if one mountain is ended it again start again mountain then ur count value is increased but in actually it is not increased.so u must add this line in ur code also
for(i=0;i
I have used the same logic, but still it doesn't passes many test cases ! If I replace 'U' in if statement by 'D' and 'D' in else if statement by 'U' , it passes all the test cases ! I don't understand why this happen ? please help !
i find your mistake, char array's last element should be reserved for null.
you need to take extra size and after the array is sifted towards right b'coz each elements moved by 1 in right side . you nedd to strat array with i=1;
include
int main()
{
int n;
scanf("%d", &n);
int j = 0, i = 0, cnt = 0;
char a[n];
// INPUT THE STEPS
for(j = 0; j < n+1; j++)
{
scanf("%c", &a[j]);
}
if you don't shift the array you can't read the input correclty. I'm just manipulate the char array in this way so that it can read the input char element correclty. if you want to do this without shifting you can see the buffer code of this problem. and then complete the code.
the constrain given is n<10^6
the loop variable i is of type int and it does not hold that much values .
so use data types of higher bits like int32_t and int64_t
The following code in C will not get the segmentation error:
#ifdef bool#undef bool#endif#define bool int#define true 1#define false 0longcountingValleys(longn,char*s){// Complete this functionlongvalleys=0;longlevel=0;boolneg=false;for(longi=0;i<n;i++){if(s[i]=='U'){level++;if(level>=0&&neg==true){neg=false;}}else{level--;if(level<0&&neg==false){neg=true;valleys++;}}}returnvalleys;}intmain(){intn;scanf("%i",&n);/* Change the default from 512000 to 1024000 */char*s=(char*)malloc(1024000*sizeof(char));scanf("%s",s);longresult=countingValleys(n,s);printf("%ld\n",result);free(s);return0;}
The code given as a default does not allocate enough space for the array. You can also do this:
char*s=(char*)malloc((n+1)*sizeof(char));
A better solution is not to use the function provided and just parse the array while it is being entered. So, you can do something like this:
charbuf;for(inti=0;i<n;i++){scan("%c",&buf);/* embed the logic of the function here */}
I got the exact same code:)
import java.io.;
import java.util.;
import java.text.;
import java.math.;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
String s = sc.next();
int v = 0;
int lvl = 0;
for(char c : s.toCharArray()){
if(c == 'U') ++lvl;
if(c == 'D') --lvl;
if(lvl == 0 && c == 'U')
++v;
}
System.out.print(v);
}
In this code
if(lvl==0 && c=='U')
++v;
this will count the uphill steps
but in this question they are asking for the down hill steps when level ==0
so instead of that if you can write
if(lvl==0 && c=='U')
for downhill steps
Am I missing something, or does this code assume that there will always be at least one valley, and that there will always be a valley inbetween any two mountains? If so, it should fail with something like:
I believe you are referring to the following code segment. It increments/decrements lvl prior to checking for valley. It does not assume a valley nor that one exists between any two mountains, as it only increments the valley count if the level is zero.
for(charc:s.toCharArray()){if(c=='U')++lvl;if(c=='D')--lvl;// if we just came UP to sea levelif(lvl==0&&c=='U')++v;
I have a different issue with this code: it counts the valley only if it is climbed out of. Therefore, it would be wrong for any journey that ended in a valley. For example, DUDUD would respond 2, when the correct answer is 3. To count the valleys on entry, check elevation on descent:
Actually, I've realized my mistake. I was failing to notice that the move was incremented first, then the current level and how it was obtained was checked. So, this should work just fine.
As for the issue you brought up, it's not possible within the confines of the question. It was stated that all journies will begin and end at zero, so any valley entered will be exited, and thus registered.
Whenever you encounter a 'U' , increment count. And encounter 'D', decrement count.
A valley ends at such a point when the count becomes 0 after encountering a 'U'. Thus increment valley_count when such a thing occurs
i see a problem with your logic, if the first letter is U and the second letter is D your code will enter the elif hgt == 0 and its going to add a 1 in vallies even thought maybe next letter is another U so for example in [U,D,U,D] your code will add to vallies twice, even though you never actually entered a valley, just climbed two mountains, what you need to do is a try: and then see if the next letter is a D, if it true then you add 1 to valley, if not then just continue with the code
It worked for my test cases. Just take a look at it.
Joe loves to travel. In her journey she notes 'U' when she travel from low to high (Uphill)
and notes 'D' when she travels from high to low (down hill)
Here high to low means from higher sea level to lower sea level
low to high means from lower sea level to higher sea level
when she travels above sea level it is a hill
when she travels below sea level she travels a valley
Count the number of valley she travelled
You are using the length of the string to use your for loop, that will work as well as the number of steps n, since each step is a single letter in your String, but you should place n in that for loop and not the length of the string, since the specification gives you that value, if you dont put it, you are not considering the problem as someone could bring to you
I compacted that a bit because for me, since you know that a valley will always come back up to sea level, you only care about the transition from 0 height to -1 height.
static int countingValleys(int n, String s) {
int height = 0;
int valleyCount = 0;
for(int i = 0; i < n; i++) {
if(s.charAt(i) == 'D') {
if(height == 0) {
valleyCount++;
}
height--;
}
if(s.charAt(i) == 'U') {
height++;
}
}
return valleyCount;
}
Kudos for using the foreach loop syntax! To save up space, the alternative String.charAt() is also an interesting improvement, and it's the one I used for my attempt.
Could you please help me understand the question first ?
When i need to check count of comeback at sea level then why we need to check
if(lvl == 0 && c == 'U')
++v;
Though we can check it only with
if(lvl == 0)
++v;
The condition check combo you mentioned has two parts to it:
a) if lvl == 0 signifies if we are currently at sea level (but we don't know at which level we came from previously)
b) if c == U means if we just climbed from a lower place to a higher one.
A AND B results in the condition check: if we came back to sea level from a lower place, then we just came from a valley; thus, we add that valley into the number of valleys we already visited.
yes, what you say is correct, BUT, considering the different test cases that might test this , you could get an input of TTTYYYUUUDDDDUUDD where T and Y are not U and D , and those could broke your method, if you doble check for U and D only , you are considering just those two letters, and that is what the problem suggests to check for.
steps=0
count_valleys=0
for x in s:
if steps==(-1) and x.upper()=='U':
count_valleys+=1
if x.upper()=='D':
steps-=1
elif x.upper()=='U':
steps+=1
return count_valleys
But they didn't guaranteed that he will climb back to sea level from valley. Then how did you use this logic. What if he doesn't climb up the valley.
Note: I used your logic and all test case is passed.
Please Reply
GREAT SOLUTION.......i did not consider the fact that at the end of the journey we are always coming upwards to sea level
so c=='U' in if(level==0 && c=='U')...... will eventually eliminate the cases where we are going upward from sealevel and then coming backwards to sealevel
if you double check you are considering the boundings of the problem, if you do an else after just checking 1 letter you could have TTZZZPPP or whatever letter there , and that is not what the problem suggest you to check for, its always a good practice if someone asks for something in a problem to give the code back with the exact request.
Nice and simple solution. We can avoid String.toCharArray() and use just one if else as the String contains only 'U' and 'D'. Count how many times Gary moved to vally from sea level. Example-
static int countingValleys(int n, String s) {
int valleyCount = 0;
int currentState = 0;
for(int i=0; i<s.length(); i++) {
if(s.charAt(i)=='U') {
currentState++;
} else {
currentState--;
// Moved from sea level to vally
if(currentState == -1){
valleyCount++;
}
}
}
return valleyCount;
}
what made u to find out " if we just came up to the sea level"??? .
I got an idea upto incrementing and decrementing the levels.. but later i did not understand why u have checked for 3rd 'if' loop
We will have to "find and print the number of valleys Gary walked through". What is a valley? Vally is nothing but step below the sea level (no matter how many steps walked belew the sea level, it's just 1 vally until Gary comes back to sea level again). Whice is equvalent to moving from 0 (sea level) to -1 (one level below the sea).
So third if is counting the the number of valleys (move from 0 to -1). We don't need to check the privious state as we got -1 after the decrement (0 - 1 = -1, it's possible only when Gary is moving from sea level to the below).
i think this can be improved a little bit, lets say that you have count of 'D's that's greater than the half of the length of s. this will keep looping can u stop it since you will never be able to come to the sea level?
I had a very similar solution, but I counted the valleys as we went below sea level instead of coming back up.
static int countingValleys(int n, String s) {
final int SEALVL = 0;
int alt = 0; //current altitude
int valleys = 0; //number of valleys
for (int i = 0; i < n; i++){
if (s.charAt(i) == 'D'){
if (alt == SEALVL) valleys++; //dipping into a valley
alt--;
}
if (s.charAt(i) == 'U') alt++;
}
return valleys;
}
What will happen if the input is UUUDDD?
Techically it is not a valley, but the programm will increment valley count since a sea level will be 0 at the end.
I ended up in a similar solution, but there's something that has bothered me for a while and it is the fact that when you go deep into a valley, you know that you must eventually come up, which means that if (|altitude| = remaining-steps ) then we know this is the last valley and there's no need to count the remaining steps.
In a string of 10^6 characters, where the first half are 'D' and the second half 'U', we shouldn't need to sum the second half to know this is the final valley.
Interestingly, that optimization was not necessary to pass the test and actually derailed my efforts for a while.
Actually you dont need to track with two variables, you could use the same variable to track up and down and check at what point it becomes zero and use the condition that we are coming from below.
Counting Valley's problem solving is the task that is handled on this page. The clear idea of the topic explained with the proper example and tries to share some different types of agricultural technology facts codes to make it very clear for the readers.
hey man it's nothing but in this problem you have to find out like how many mountains are created below the see level or downside the see level I hope this will help you
nice solution but i recommend you to use if-else because you double check every time a step is taken. It's either up or down. Check my solution if you like! Cheers!
Thanks. Still new at this and learning the complexity thing I have never used before. Some of the solutions are very interesting and make me learn new things. Thanks for the comment :)
I was stuck here, I just counted number of times we came back to surface, this is the reason my program was counting valleys even hicker came down from mountain to sea level. Thanks buddy...
In the above code, I have applied the condition that whenever there is upward trend, sum increases by 1 else decreases by 1. When Gary reaches sea level during upward trend and reaches sea level(sum = 0), it is counted as crossing a valley. So, D = -1; U = +1. We forget the Ds and focus on Us.
Hi,
I don't understand this. Can you please explain how is this code right for the input "DDDUUUUUUUDDDUUUDDDD". If the valley is determined by climbing down and climbing up to same level then there should 2 vallies in my case. Can you explain this?
ar=s.split('');
newarr=Array.new;
v=0;
lvl=0;
ar.each do |item|
if item == 'U'
lvl=lvl+1;
else
lvl=lvl-1;
end
if lvl==0 && item == 'U'
v+=1;
end
end
return v;
Same solution as above but using switch case instead.
static int countingValleys(int n, String s) {
int valleyCount = 0;
int seaLevel = 0;
for (int i = 0; i < n; i++) {
switch(s.charAt(i)) {
case 'U':
seaLevel++;
if (seaLevel == 0) valleyCount++;
break;
case 'D':
seaLevel--;
break;
}
}
return valleyCount;
}
Actually, based on the problem statement, we can assume the hiker always returns to sea level so what you really want to do is count any down transition out of sea level (i.e. if(lvl == -1 && c == "D")). Your way, I think you could potentially miss a valley if the hiker never explictly reached sea level at the end.
Please suggest any glitch correction or code optimization if you don't mind! (Btw this solution passed all test cases, but just wondered whether it would other test cases apart from the 21 test cases given here)
If not that each hike ends at sea level as declared in the question, this concept would have missed cases where hikes end within the valley like 'UDD', 'D', 'DD', etc
def countingValleys(steps, path):
uc = 0
dc = 0
vel = False
vc = 0
for s in path:
if (s == 'D'):
if(uc > 0):
uc -= 1
else:
dc += 1
vel = True
elif (s == 'U'):
if(dc > 0):
dc -= 1
if (dc == 0):
vc += 1
vel = False
else:
uc += 1
return vc
int n = sc.nextInt() is unused here! So if I provide 4 steps but path -> DDDDUU(6 steps) it is still going to accept the input and return 0! I think that's where the code fails.
Thank U very much...I was stuck at the problem statement and could not figure it out that what it want to say..but..by read your code line that says..."We only care about the number of valleys... So just figure out the number of times you came back up to sea level." I understand and solved it..
publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intn=sc.nextInt();Strings=sc.next();intnOV=0;// no of valleysintaltitude=0;// current levelfor(charc:s.toCharArray()){if(altitude==0&&c=='D')nOV++;altitude=(c=='D')?--altitude:++altitude;}System.out.println(nOV);}
Thanks a lot bro , applied your logic , happened in 1st attempt , used a variable to store the current position of the hiker and after every loop iteration of the path string added the new value of the position in a vector and from that vector checked for position 0 (sea level) and checked if the previous position was -ve(below sea level)
this is great. i figured the same logic soon but it took me so long to write it down and i made the code more complicated than it needed to be. im not used to dealing with char, so i used split() and transformed it in a string array, waste of time. thanks for your comment
Counting Valleys
You are viewing a single comment's thread. Return to all comments →
Java solution
We only care about the number of valleys... So just figure out the number of times you came back up to sea level.
Brilliant
The problem statement says consecutive steps below sea level. Does this solution work for 4 DUDU or does it return 1? Based on the problem statement that input should return 0.
Edit: I removed the condition to check that the previous step was also below sea level and all the tests passed. However, this no longer matches the definition of a valley "consecutive steps below sea-level"... unless I am misunderstanding the implied multiplicity in the word consecutive.
I think the word consecutive is misleading here. Think about it, the number of valleys is just the number of times you went down below sea level and back up again. Every time it starts at sea level and goes down then back up to sea level, that is a valley. It doesn't need the word 'consecutive' in there.
Right.
Here comes the solution in python.
Hackerrank - Counting Valleys Solution
here is solution of problem in Python java c++ and c programming. https://solution.programmingoneonone.com/2020/07/hackerrank-counting-valleys-solution.html
That's right.
I am equally seeing it from your own point of view, that word "consecutive" is misleading
I totally agreed. When I analyse the test case and even I manually count the number of valleys and I also got the different answer from the test case. The word "consecutive" makes me think it needs at least two "D" to start with. I strongly reccommend to remove the word "consecutive" which is misleading!
Yup, this confusion took me down the wrong path. Pulled my hairs when the submission failed.
Yes, the word "consecutive" make me lost about 3 hours trying to understand where I was wrong. So, removing the constraint that I was considering (at least 2 steps below sea level), makes all test pass
No wonder... I was think the same that it needs 2 D to start a valley..
yeah ,you are right
yes. right. it misleads me too.
Please suggest the edit in the question.
I totally thought 'consecutive' meant DU would not count as 1.
That's right..In the explanation part the answer should be 2 not 1 as per the definition because the hiker is coming 2 times to the sea level.
Totally agree with you, consecutives steps down means at least 2 steps down. It means 1 step down from sea level than 1 step up is not a valley according to the description.
Exactly spent half an hour cuz of this misleading consective statment!
Completely agree!!! The word 'consecutive' is misleading and if I have not had a look in the discussion tab, I would have never known about this. Thanks guys!!!
Ya, i'm also totally agreed with you i was failed to execute after checking the test cases and got the word 'consecutive' is missleading. good!!
thank you, that was my problem, i i though i need to be atleast 2levels down from sea level.. after making it only 1 level, everything worked out...
Entirely misleading wording. It is assumed you need two "D" steps from sea level in order for a valley to start. They obviously include DUDU as two separate valleys.
I think you are right.* "A valley is a sequence of consecutive steps below sea level, "* to me, means Gary took two or more steps below sea level. Problem description is misleading.
Yes I agree with this,The description is misleading
Please suggest editing.
excatly my doubt is what about case dudu?
that's 2 vallys
in the case dudu the function must returned 2
this is my c++ solution it works for all cases
int countingValleys(int steps, string path) {
}
This is python 3
In case of DUDU, there will be 2 valleys.
Explantion
sea-level \/\/ sea-level
You can verify my correct solution, using the custom test case
4 DUDU
Because at the end of the journey, the hiker will always return to sea level. So if you check every time the hiker goes back to sea level, and in this case, if the hiker comes from below, it means that the hiker went through a valley on the last walk.
get u with that dudududu!
it means 2 valleys
Yes, I think the word "consecutive" is misleading; it threw me off as well. One could argue it doesnt say "consecutive steps down". Unlocking one of the test case helped clear the doubt for me though.
Even i thought for climbing from or into a valley we need 2 steps.
Yes I agree your you . I had similar understanding. Looks like the word 'consecutive ' is misleading in the question
Yeah, "consecutive" lead me astray for a while. Always fun when test questions are wrong :D
I think that if we consider that for making even an only one-level-deep valley we need two consecutives steps (D and U) below sea level, there is no problem with the description.
In other words, if we take into account only where (above/below sea level) the steps themselves took place (and not wheter they are uphill or downhill, nor what are their starting or edning points) to classify them as being above or below sea level, the tests match with the statement:
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.
I hope it makes sense.
I think if we take into account only where (above/under sea level) the steps themsleves took place (not wheter they are downhill or uphill) to classify them as being above or under sea level, the tests match with the statement:
A valley is a sequence of consecutive steps below sea level, (...)
In other words, I think we sould consider where the "body" of each step is to solve this problem.
I hope it makes sense.
Exactly, I also was stuck because of the definition-'consecutive steps below sea-level'.. After seeing the solution here, I also thought of the same situation with case DUDU. And if a move up while current level is 0 counts as a valley, then a move down while current level is 0 should also work as a solution, but it doesn't.
nice one!
Here comes the solution in python.
Hackerrank - Counting Valleys Solution
Can you please explain what you were doing here:
if not a+d[i] and a <0: b+=1 a+=d[i]
How is it possible to add (a = 0) to d[i] (a key). Please just explain oyour overall logic to me. Thanks in advance.
d[i] is value not key. The logic is brilliant. a is taking the sum of the consequitive steps of the path.So, after decending a valley if someone ascending to sea level then a=0 and if again it is negative that means new valley is explored so b will be increased 1 otherwise no change.
here is problem solution in java python c++ and c javascript programming. https://programs.programmingoneonone.com/2021/03/hackerrank-counting-valleys-solution.html
Here is my c++ solution, you can watch the explanation here : https://youtu.be/fgJ-i8RJ1Qw
simple and superb
the most optimized fastest code: c#
in if condition u r passing as a string but array is required. We can use like this: if(s.charAt(i)=='U') i got correct solution
In c# a string is an array of char.
what logic behind this
Why are you using static int type fuction when int type serves our purpose?
This code is correct but the test cases are getting failed. I think they are pulling us into wrong track.
I checked the above code but it didn't passed the test cases. This problem can be solved like this...
int countingValleys(int steps, char* path)
{
int c=0; int valley_count=0; for (int i=0;i
} return valley_count;
}
short, simple and stright to the point. love it!
the most optimized fastest code: c#
why are u using function type as static int?? can you explain that bro?
I can't understand what u r trying to say...plz explain in detail
whats the problem in this code??\
I thought i did well but looking at the very first commment, I realized im not good
Nice try but i know how it looks when u r at the begginer level of coding and all other are giving answers like one line python code and very small code
I'd rather see well-commented code than magical one-liners. Unless the performance increases to the roof.
great i didn't know how to solve this....
The problem is that it is not visible to the compiler.
its blurry
I've implemented the same logic as yours... Still it does not pass many testcases. Please help
Ya mine also many test case did not pass in he same logic
I have done the same,but may of my test cases failed.
try this logic:
Yeah yours is cool! Thanks
Hi, I think we can get by without using the character array. My submission below (translated to reflect your variable names). Passes all test cases.
y hav you taken ch=='u' in the third if loop, iam nt getting y it is... can u pls explain it
In the third if condition, we are checking if we returned to sea level (0) from a valley by moving upwards (U). So we are verifying and incrementing the answer with respect to these 2 parameters
then y didnt you consider "D"- moving downwards?? please answer?
I guess that would lead to hill, not valley, so that's why.
what's cin.ignore()?
Why don't you just google, rather asking here: https://en.cppreference.com/w/cpp/io/basic_istream/ignore
motherfucker, we are here to learn, and discuss in case of any doubt. Stop with your bullshit suggestions, asshole.
what is roll of a cin.ignore(); in these code
Nice Observation!
Change the size of the array initialized in the main function. It should work! 1*10^6.
what that n<=1000000 is for ??
C++14? I don't think that means what you think it means ;-)
what alteration can we do in the above code to pass all the test case and why ?
if one mountain is ended it again start again mountain then ur count value is increased but in actually it is not increased.so u must add this line in ur code also for(i=0;i
I have used the same logic, but still it doesn't passes many test cases ! If I replace 'U' in if statement by 'D' and 'D' in else if statement by 'U' , it passes all the test cases ! I don't understand why this happen ? please help !
i find your mistake, char array's last element should be reserved for null. you need to take extra size and after the array is sifted towards right b'coz each elements moved by 1 in right side . you nedd to strat array with i=1;
include
int main() { int n; scanf("%d", &n); int j = 0, i = 0, cnt = 0; char a[n]; // INPUT THE STEPS for(j = 0; j < n+1; j++) { scanf("%c", &a[j]); }
}
thank you
this is right. but why array elements shifted to right ? m not getting? plz explain?
#include
include
using namespace std; int main() { int n; cin>>n; int j , i = 0, cnt = 0;
for(j = 0; j < n; j++) { if(s[j] == 'U') { i = i + 1; if(i == 0) cnt++; } else if(s[j] == 'D') { i = i - 1; } }
return 0; }
The idea do work my program was success fully run in C But I wanna know theoretical reason behind why array elements got shifted to
if you don't shift the array you can't read the input correclty. I'm just manipulate the char array in this way so that it can read the input char element correclty. if you want to do this without shifting you can see the buffer code of this problem. and then complete the code.
Ok thank you but buffer was not working
Thank You
put a space infornt of "%c"..... or replace with this [ scanf(" %c", &a[j]); ] Hope,it will work!
It workss thx!!
the constrain given is n<10^6 the loop variable i is of type int and it does not hold that much values . so use data types of higher bits like int32_t and int64_t
here you scan only n char but last char is '\n' so that use n+1 in instead of n
in the abouve code you are also calculating the hill crossed ,but only valley is asked so edit if(i==0 && s[j]=='U') { cnt++; }
// Complete the countingValleys function below. int countingValleys(int n, string s) {
int sea_level = 0; bool sea_level_cross = false; int valley;
for(int i=0; i if(s[i]=='U') { sea_level++; if (sea_level < 0 && sea_level_cross == false) { sea_level_cross = true; valley++; } if(sea_level>= 0 && sea_level_cross == true) { sea_level_cross = false; } } else { sea_level--; if (sea_level < 0 && sea_level_cross == false) { sea_level_cross = true; valley++; } if (sea_level >= 0 && sea_level_cross == true) { sea_level_cross = false; } } } return valley; }
for for loop use for(j=0;j<=n;j++)
i have implemented the same logic as yours but it's work in all testcases.
you should execute the loop for <= in voth loops,during inputs of elemnt and during logic part as well
I implemented the same, nice to see concepts matching :P
it is not able to pass all the test cases,as input constrain is 1000000; and we are getting segmentation error
The following code in C will not get the segmentation error:
The code given as a default does not allocate enough space for the array. You can also do this:
A better solution is not to use the function provided and just parse the array while it is being entered. So, you can do something like this:
Excellent.
Would this work if "we only care about the number of" mountains?
I think no. Because you can go to valley, come back to sea level, again go to valley, so on... without ever climbing the mountain.
Yea you could just add another if statement testing basically the opposite.
superb!!!
Beautiful Solution
Awesome .... just brilliant
I came up with same concept, but yours is better executed. the use of s.toCharArray() is nice.
I got the exact same code:) import java.io.; import java.util.; import java.text.; import java.math.; import java.util.regex.*;
public class Solution {
}
In this code if(lvl==0 && c=='U') ++v; this will count the uphill steps but in this question they are asking for the down hill steps when level ==0 so instead of that if you can write if(lvl==0 && c=='U') for downhill steps
superb...
True, but only because he had to end at sea level. Without that it becomes messier. In any case - awesome!
Am I missing something, or does this code assume that there will always be at least one valley, and that there will always be a valley inbetween any two mountains? If so, it should fail with something like:
2 UD expected: 0 actual: 1
or
4 UDUD expected: 0 actual: 2
For comparison (Python 3):
I believe you are referring to the following code segment. It increments/decrements lvl prior to checking for valley. It does not assume a valley nor that one exists between any two mountains, as it only increments the valley count if the level is zero.
I have a different issue with this code: it counts the valley only if it is climbed out of. Therefore, it would be wrong for any journey that ended in a valley. For example, DUDUD would respond 2, when the correct answer is 3. To count the valleys on entry, check elevation on descent:
Actually, I've realized my mistake. I was failing to notice that the move was incremented first, then the current level and how it was obtained was checked. So, this should work just fine.
As for the issue you brought up, it's not possible within the confines of the question. It was stated that all journies will begin and end at zero, so any valley entered will be exited, and thus registered.
...and that's why I should start reading the instructions in their entirety, lol.
def countingValleys(n, s): l=list(s) count=0 up=0 down=0 for step in l: if step=='U': up+=1 if(up==down): count+=1 else: count+=0 else: down+=1 return count
will you please explain the above code?
Whenever you encounter a 'U' , increment count. And encounter 'D', decrement count. A valley ends at such a point when the count becomes 0 after encountering a 'U'. Thus increment valley_count when such a thing occurs
Thanks
i see a problem with your logic, if the first letter is U and the second letter is D your code will enter the elif hgt == 0 and its going to add a 1 in vallies even thought maybe next letter is another U so for example in [U,D,U,D] your code will add to vallies twice, even though you never actually entered a valley, just climbed two mountains, what you need to do is a try: and then see if the next letter is a D, if it true then you add 1 to valley, if not then just continue with the code
It worked for my test cases. Just take a look at it.
Joe loves to travel. In her journey she notes 'U' when she travel from low to high (Uphill) and notes 'D' when she travels from high to low (down hill)
Here high to low means from higher sea level to lower sea level low to high means from lower sea level to higher sea level
when she travels above sea level it is a hill when she travels below sea level she travels a valley Count the number of valley she travelled
see the image "6-valley.png" for example
header('Content-type: application/json'); echo countingValleys('DDUUDDUDUUUD');
function countingValleys($s) {
counts and returns the number of valleys joe has travelled
} }
}
That's what I thought; For those who are in love with C++,
same code in c isn't giving correct output?y?
what z "a" here you has taken?
You are using the length of the string to use your for loop, that will work as well as the number of steps n, since each step is a single letter in your String, but you should place n in that for loop and not the length of the string, since the specification gives you that value, if you dont put it, you are not considering the problem as someone could bring to you
This won't work for "UUUDDUUDDD"
There should be one valley here right? This solution gives 0.
Actually not! The valley you are assuming is not a valley because it is above the sea level.
Read the 2nd term in the problem: A valley is a sequence of consecutive steps below sea level...
Ohh yeah! Correct. Sorry my bad.
Can you believe? I spent 3 hour using that as one of my test case.
How did you figure out that s[i] == 'U'?
Best of all, Thankyou
precise and easy to understand! amazing code!
10/10 solution. Simple,efficient and short.
thank you
same code in c is giving segmentation fault for some cases
include
include
include
include
include
include
include
int countingValleys(int n, char* s) { int count1=0; int count=0;
for (int i=0;i
Thanks man !! It's Simple braining sol.
I compacted that a bit because for me, since you know that a valley will always come back up to sea level, you only care about the transition from 0 height to -1 height.
static int countingValleys(int n, String s) { int height = 0; int valleyCount = 0; for(int i = 0; i < n; i++) { if(s.charAt(i) == 'D') { if(height == 0) { valleyCount++; } height--; } if(s.charAt(i) == 'U') { height++; } } return valleyCount; }
Wonderful solution
brilliant logic man
Brilliant
Brilliant
A Quick Tip:
Kudos for using the foreach loop syntax! To save up space, the alternative String.charAt() is also an interesting improvement, and it's the one I used for my attempt.
Hi,
Could you please help me understand the question first ? When i need to check count of comeback at sea level then why we need to check if(lvl == 0 && c == 'U') ++v;
Though we can check it only with if(lvl == 0) ++v;
Please help me to understand.
The condition check combo you mentioned has two parts to it: a) if lvl == 0 signifies if we are currently at sea level (but we don't know at which level we came from previously) b) if c == U means if we just climbed from a lower place to a higher one.
A AND B results in the condition check: if we came back to sea level from a lower place, then we just came from a valley; thus, we add that valley into the number of valleys we already visited.
Good logic!
can any one can write simpler than this "python" land=0
Best solution I've seen so far; very "Pythonic"
I had about the same solution. Isn't it necessary to declare your 'land'?
why you used this
if level == 0: val += 1
Second if is of no use.. directly else would work. But Best program dude:)
yes, what you say is correct, BUT, considering the different test cases that might test this , you could get an input of TTTYYYUUUDDDDUUDD where T and Y are not U and D , and those could broke your method, if you doble check for U and D only , you are considering just those two letters, and that is what the problem suggests to check for.
brilliant solution!
Using your land==0 and i=='U' test
nice
Mindblown !!
mind blowing
Very succint
Did something similar:
this is awesome bro
Awesome! simple and brilliant logic.
Awesome
Perfect solution.
Just a side subtle question - what is the advantage of pre-incrementing the variable rather than post incrementing ? i.e. ++lvl vs lvl++, in general ?
Brilliant! I missed the && c == 'U' part in mine. Thanks
Awesome!!!!!!!!
how did you get this logic??
Simple and short.
But they didn't guaranteed that he will climb back to sea level from valley. Then how did you use this logic. What if he doesn't climb up the valley. Note: I used your logic and all test case is passed. Please Reply
valley condition occurs when he climbs up .this is basic knowledge
What if he doesn't climb up?.
doesn't occurs valley
As soon as he moves downside, valley counts. So the checking should be at starting of valley not at end of
the wording of the problem explains that a valley js created when the man returns to sea level from below it
if(lvl == 0 && c == 'U')
Could you please Explain why You wrote c == 'U'?
great and simple one, super
What if the input is DDDDDDD Shouldnt it return a valley, but will it do so in the above code
The problem states that he always returns to sea level.
Good solution, be sure to give meaningful names to your variables. I wouldn't use 'v' or 'c', just for good practices.
GREAT SOLUTION.......i did not consider the fact that at the end of the journey we are always coming upwards to sea level
so c=='U' in if(level==0 && c=='U')...... will eventually eliminate the cases where we are going upward from sealevel and then coming backwards to sealevel
Please note that second if statement should replace by else if statement cause of same character at a time does not need double check!
if you double check you are considering the boundings of the problem, if you do an else after just checking 1 letter you could have TTZZZPPP or whatever letter there , and that is not what the problem suggest you to check for, its always a good practice if someone asks for something in a problem to give the code back with the exact request.
Nice and simple solution. We can avoid String.toCharArray() and use just one if else as the String contains only 'U' and 'D'. Count how many times Gary moved to vally from sea level. Example-
static int countingValleys(int n, String s) {
cool
what made u to find out " if we just came up to the sea level"??? . I got an idea upto incrementing and decrementing the levels.. but later i did not understand why u have checked for 3rd 'if' loop
We will have to "find and print the number of valleys Gary walked through". What is a valley? Vally is nothing but step below the sea level (no matter how many steps walked belew the sea level, it's just 1 vally until Gary comes back to sea level again). Whice is equvalent to moving from 0 (sea level) to -1 (one level below the sea).
So third if is counting the the number of valleys (move from 0 to -1). We don't need to check the privious state as we got -1 after the decrement (0 - 1 = -1, it's possible only when Gary is moving from sea level to the below).
Great!
PHP Version:
(y)
i think this can be improved a little bit, lets say that you have count of 'D's that's greater than the half of the length of s. this will keep looping can u stop it since you will never be able to come to the sea level?
if think you can do this
Any one please explain why c==='u' in the if condition? The level can be 0 at downward step also right?
what about if case is DUDU?
if we use String s=sc.nextLine(); the output is 0. Can you please tell me why it's giving zero.
Brilliant. Thank you :)
well described.
100 % working code with video explanation -- All Test Case Passed..!!
Here is the video explanation of my simple solution -
https://youtu.be/MMmFELo0QjM
and you can find most of the hackerrank solutions with video explaination here-
https://github.com/Java-aid/Hackerrank-Solutions
and many more needs to be addeed.
Regards,
Kanahaiya Gupta
Git Hub URL | https://github.com/Java-aid/
It not true, I do not help me problem, I do not like your channel.
May i konw what is not true? what is the problem you have seen in my algo?
Similar slightly better(imho) C++ solution, but not while reading in chars
cool..(Y).
awesome
what?
the if statements are on point, I had a tough time communicating that simply.
did you saw the video tutorial?
it's great, thank you.
If you dont mind can you please like, dislike or leave your feedback on my video. it motivates me and help other too find the solution over internet.
Simple and good approach. Thanks
hey just wanted to confirm you are talking about the video tutorial or something else..:)
@I0000
I had a very similar solution, but I counted the valleys as we went below sea level instead of coming back up.
static int countingValleys(int n, String s) { final int SEALVL = 0; int alt = 0; //current altitude int valleys = 0; //number of valleys
You can avoid doing the test lvl == 0 when Gary goes down and retest if c == 'U'.
Domain : {U or D}
Two less tests.
Do like this :
Nicely done, i was very close to a similar solution. Just couldnt quite figure out the right way to count the valleys
Hey here is my code for "how many time we came back to sea level"
"UDDDUDUU".chars.map{|i| i == 'U' ? 1 : -1}.reduce([0]) { |a, v| a.push(a.last.to_i + v.to_i); a}.count(0) - 1
What will happen if the input is UUUDDD? Techically it is not a valley, but the programm will increment valley count since a sea level will be 0 at the end.
UDUD It gives 0 output why ? but there is 1 valley
you are right but there was a condition the valley must be dawnword. above the line valley will not be count.
It's cool. By the way, we have to check whether it is valley or not first before modifying the level. Don't we?
static int countingValleys(int n, String s) {
we can solve this problem by graph and i did exactly this
nice
char[] steps = s.ToArray(); int level = 0; int valleys = 0; for (int i =0;i
you explained the question in very simple way... thank you
the most optimized fastest code: c#
Spammer
Thank you so much ! Helped a lot..
I ended up in a similar solution, but there's something that has bothered me for a while and it is the fact that when you go deep into a valley, you know that you must eventually come up, which means that if (|altitude| = remaining-steps ) then we know this is the last valley and there's no need to count the remaining steps.
In a string of 10^6 characters, where the first half are 'D' and the second half 'U', we shouldn't need to sum the second half to know this is the final valley.
Interestingly, that optimization was not necessary to pass the test and actually derailed my efforts for a while.
My solution still suffers from that shortcoming.
Great Logic
Brillant
nice
Javascript
Hola ! Sabrian decirme porqué mi código no soporta todas las pruebas ? (11/22) JavaScript:
function countingValleys(n, s) {
var result = Array.from(s).reduce((lvl,path)=> {
return result; }
Actually you dont need to track with two variables, you could use the same variable to track up and down and check at what point it becomes zero and use the condition that we are coming from below.
Simple and brilliant. How long it took in minutes to solve this? :)
Thankyou, well formed algo.I also though something similar to this but this one is better.
It's execellent, but more he content in spanish
Thanks
I also used same approach. Kudos.
Babbbooskha...nice one!
Counting Valley's problem solving is the task that is handled on this page. The clear idea of the topic explained with the proper example and tries to share some different types of agricultural technology facts codes to make it very clear for the readers.
anyone explain me the question first plzzzzzzzzzzzzzzz.
hey man it's nothing but in this problem you have to find out like how many mountains are created below the see level or downside the see level I hope this will help you
thank u bhaiiii.i understand now.
this working in symmertry for valley so, we consider count(v) which comes under when "U" with lvl == 0, not for "D"....
i understood thanks,
tqsm buddy!
amazing
it's too simple solution dude.
nice solution but i recommend you to use if-else because you double check every time a step is taken. It's either up or down. Check my solution if you like! Cheers!
Awesome
Used the same approach. Works fine.
Other way to achieve result. But your solution is much cleaner.
Thanks. Still new at this and learning the complexity thing I have never used before. Some of the solutions are very interesting and make me learn new things. Thanks for the comment :)
I was stuck here, I just counted number of times we came back to surface, this is the reason my program was counting valleys even hicker came down from mountain to sea level. Thanks buddy...
had similar idea in python
I am a beginner. I am confused now. Can u plz tell me why are we checking c == 'U' in the last if statement. I did not get it.
for(int i=0;i
In the above code, I have applied the condition that whenever there is upward trend, sum increases by 1 else decreases by 1. When Gary reaches sea level during upward trend and reaches sea level(sum = 0), it is counted as crossing a valley. So, D = -1; U = +1. We forget the Ds and focus on Us.
i
this code fails for the test DDUUUUDD it gives a answer 1 whereas the answer should be 2 as per the problem statement
I tried the same logic in JS but it gives me only 0
Great!!!
Thank you. It was really helpful. It took long enough for me to figure it out. Your trick is very easy and understandable. Thank you very much.
Hi, I don't understand this. Can you please explain how is this code right for the input "DDDUUUUUUUDDDUUUDDDD". If the valley is determined by climbing down and climbing up to same level then there should 2 vallies in my case. Can you explain this?
Used your logic in Ruby - Thanks for the hint !!
ar=s.split(''); newarr=Array.new; v=0; lvl=0; ar.each do |item| if item == 'U' lvl=lvl+1; else lvl=lvl-1; end if lvl==0 && item == 'U' v+=1; end end return v;
Same solution as above but using switch case instead.
Actually, based on the problem statement, we can assume the hiker always returns to sea level so what you really want to do is count any down transition out of sea level (i.e. if(lvl == -1 && c == "D")). Your way, I think you could potentially miss a valley if the hiker never explictly reached sea level at the end.
Similar approach in python, was trying this for over 1 hour so forgot how I arrived at the solution 😂
https://www.hackerrank.com/challenges/counting-valleys/forum/comments/818842
Please suggest any glitch correction or code optimization if you don't mind! (Btw this solution passed all test cases, but just wondered whether it would other test cases apart from the 21 test cases given here)
Wow didn't think this problem could be solved so easily...Great work!
I used the same logic, but why write the condition to count valley separately, write it this way:
If not that each hike ends at sea level as declared in the question, this concept would have missed cases where hikes end within the valley like 'UDD', 'D', 'DD', etc
these hike are not valleys these will be mountains and we don't have to count them
excellent approach
hey bro i think this code won't work for this case 15 DUDUDUDUDUDDDD Just try this out
it says that starting will be a down first. how this condition statisfy?
okk thnx it was my mistake
your mindset is great.
I am just starting here in HackerRank:
def countingValleys(steps, path): uc = 0 dc = 0 vel = False vc = 0 for s in path: if (s == 'D'): if(uc > 0): uc -= 1 else: dc += 1 vel = True elif (s == 'U'): if(dc > 0): dc -= 1 if (dc == 0): vc += 1 vel = False else: uc += 1 return vc
can you explain me the problem statement once.....
int n = sc.nextInt() is unused here! So if I provide 4 steps but path -> DDDDUU(6 steps) it is still going to accept the input and return 0! I think that's where the code fails.
Why do pre increment and pre decrements?
Why pre increment?
Same in py3 :)
Your logic is brilliant .How can i improve my logical ability and problem solving skills ? please give me suggestions and tips .Thanks in advance !
In case you all need the Golang version:
Thank U very much...I was stuck at the problem statement and could not figure it out that what it want to say..but..by read your code line that says..."We only care about the number of valleys... So just figure out the number of times you came back up to sea level." I understand and solved it..
Brilliant!
OMG I was using strange logics😂, and you solved it in such an easy way like a magic....
Hey! Can you please explain the code logic.
@mandingaro I just wanted to know the output for the test case : 10 DDUUUUDDUD......here it crosses the sealevel twice but the output is one.
python3:
you should include the test lvl==0 in c=='D' to avoid test repitation and also minimize test quantity
let level=0,res=0; for (let i=0;i
Didnt understand if this part, somebody please help - if(lvl == 0 && c == 'U')
Thanks a lot bro , applied your logic , happened in 1st attempt , used a variable to store the current position of the hiker and after every loop iteration of the path string added the new value of the position in a vector and from that vector checked for position 0 (sea level) and checked if the previous position was -ve(below sea level)
Why did you use Pre-increment? Is that make any difference to the above code?
Because, I tried the same above with post-increment and post-decrement but it worked as expected.
Why did you use Pre-increment? Is that make any difference to the above code?
Because, I tried the same above with post-increment and post-decrement in C++ but it worked as expected without any issues.
this is great. i figured the same logic soon but it took me so long to write it down and i made the code more complicated than it needed to be. im not used to dealing with char, so i used split() and transformed it in a string array, waste of time. thanks for your comment