The problem of “Repeated String” – C Source code

T

Lilah has a string, s , of lowercase English letters that she repeated infinitely many times. Given an integer, n, find and print the number of letter a‘s in the first n letters of Lilah’s infinite string.

For example, if the string s=’abcac’ and n=10, the substring we consider is ‘abcacabcac’ , the first 10 characters of her infinite string. There are occurrences 4 of a in the substring.

More information about this ‘problem’ can be found at: https://www.hackerrank.com/challenges/repeated-string

#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 repeatedString function below.
long repeatedString(char* s,long long n)
{
    long full_repetition = 0;
    long  partial_repetition = 0;
    int partial_repetition_sz = n % strlen(s);
    char* current_position = s-1;
    
    while ((current_position = strchr(current_position + 1, 'a')) != NULL)
    {
        full_repetition++;
        //Splitted in two 'if' for readability
        if(partial_repetition_sz!=0)
            if ((strlen(s) - strlen(current_position)) < partial_repetition_sz)
                partial_repetition++;
    }

    return full_repetition * (n / strlen(s)) + partial_repetition;
}

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

    char* s = readline();

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

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

    long result = repeatedString(s, n);

    fprintf(fptr, "%ld\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;
}

Disclaimer: The present content may not be used for training artificial intelligence or machine learning algorithms. All other uses, including search, entertainment, and commercial use, are permitted.

Categories

Tags