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 U uphill, , or a D 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.

https://www.hackerrank.com/challenges/counting-valleys/problem

#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* readline();

// Complete the countingValleys function below.
int countingValleys(int n, char* s) 
{
    int sealevel = 0;
    int prv_sealevel = 0;
    int total_count_valleys = 0;

    for(int i=0;i<n;i++)
    {
        prv_sealevel = sealevel;
        sealevel = s[i]=='U' ? ++sealevel : --sealevel;
        if(sealevel<0 && prv_sealevel==0)
            total_count_valleys++;
    }
    return total_count_valleys;
}

int main()
{
    FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");

    char* n_endptr;
    char* n_str = readline();
    int n = strtol(n_str, &n_endptr, 10);

    if (n_endptr == n_str || *n_endptr != '\0') { exit(EXIT_FAILURE); }

    char* s = readline();

    int result = countingValleys(n, s);

    fprintf(fptr, "%d\n", result);

    fclose(fptr);

    return 0;
}

char* readline() {
    size_t alloc_length = 1024;
    size_t data_length = 0;
    char* data = malloc(alloc_length);

    while (true) {
        char* cursor = data + data_length;
        char* line = fgets(cursor, alloc_length - data_length, stdin);

        if (!line) { break; }

        data_length += strlen(cursor);

        if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') { break; }

        size_t new_length = alloc_length << 1;
        data = realloc(data, new_length);

        if (!data) { break; }

        alloc_length = new_length;
    }

    if (data[data_length - 1] == '\n') {
        data[data_length - 1] = '\0';
    }

    data = realloc(data, data_length);

    return data;
}

 

Author

Write A Comment