Question

C Programming Language

Problem Title : Climbing Stairs

Bibi climbs stairs of a multi-leveled building. Every time Bibi climbs a set of stairs, she counts the steps starting from 1 to the number of steps in that particular set of stairs while climbing the stairs. For example if she climbs two set of stairs, the first containing 5 steps and the second containing 3 steps, she will say 1, 2, 3, 4, 5, 1, 2, 3 and the total number of steps would be 8. Find the number of steps that Bibi climbed in each set of steps.

Format Input

The first line of the input contains an integer N, the number of numbers Bibi said. The second line of the input contains N integers Ai , the i-th number Bibi said. The given sequence of Ai will be a valid sequence, that means the whole input can be cut into sequences of 1, 2, . . . , X, where X is the number of steps in a set of stairs.

Format Output

Print the number of steps that Bibi climbed for each set of steps, in the order of the input sequence, separated by single spaces. There is no leading and trailing spaces in the output.

Constraints

• 1 ≤ N ≤ 1, 000
• 1 ≤ Ai ≤ 1, 000
• The given sequence of Ai will be a valid sequence, that means the whole input can be cut into sequences of 1, 2, . . . , X, where X is the number of steps in a set of stairs

Sample Input & Output (1) (standard input & output)

8
1 2 3 4 5 1 2 3
5 3

Sample Input & Output (2) (standard input & output)

10
1 2 1 1 2 3 4 1 2 3
2 1 4 3

Sample Input & Output (3) (standard input & output)

5
1 2 3 4 5
5

Explanation:

The first sample is the example from the problem description.

In the second sample:
The first set of stairs have 2 steps, current sequence is ”1, 2”
second set have 1 steps, current sequence is ”1, 2, 1”
third set have 4 steps, current sequence is ”1, 2, 1, 1, 2, 3, 4”
last set have 3 steps, current sequence is ”1, 2, 1, 1, 2, 3, 4, 1, 2, 3”, just like the input

In the third sample, there is only one set of stairs which contains 5 steps.

Answer 1

#include <stdio.h>

#include <stdlib.h>

 

// function to return count of stairs in each set of stairs.

int* climbingStairs(int arr[], int n, int N) {

 

    // dynamically creating an array to store the count of stairs in each set of stairs. Variable 'n' stores the number of sets. 'N' is the size of sequence.

    int* result = (int*)malloc(n * sizeof(int));

    int idx = 0;

     

    // maintaining to variables to point at indices of 1 to calculate the difference between them to give number of stairs.

    int prev_idx = 0, curr_idx = 0;

    for (int i = 1; i < N; i++) {

        if (arr[i] == 1) {

            curr_idx = i;

            result[idx++] = curr_idx - prev_idx;

            prev_idx = curr_idx;

        }

    }

    // this is handling the last set of steps case as mentioned in the explanation above.

    result[idx] = N - curr_idx;

    return result;

}

 

int main()

{

    // added this print statements for clarity, remove if you want.

    printf("Enter number of numbers\n");

    int N;

    scanf("%d", &N);

 

    // array to hold the sequence of stairs.

    int* arr = (int*)malloc(N * sizeof(int));

    for (int i = 0; i < N; i++) {

        scanf("%d", &arr[i]);

    }

 

    // variable to store the number of sets.

    int set_of_steps = 0;

    for (int i = 0; i < N; i++) {

        if (arr[i] == 1) {

            set_of_steps++;

        }

    }

      

    // calling the function to return pointer to array.

    int* ans = climbingStairs(arr, set_of_steps, N);

    printf("number of steps in each set:\n");

 

    // above print just for clarity.

    // below loop is printing the result.

    for (int i = 0; i < set_of_steps; i++) {

        printf("%d ", ans[i]);

    }

 

    return 0;

}