In: Computer Science
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 1 (standard input):
8
1 2 3 4 5 1 2 3
Sample Output 1 (standard output):
5 3
Sample Input 2 (standard input):
10
1 2 1 1 2 3 4 1 2 3
Sample Output 2 (standard output):
2 1 4 3
Sample Input 3 (standard input):
5
1 2 3 4 5
Sample Output 3 (standard output):
5
Note 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.
*Note: Use C language and long long int (must be the same as the constraint)
Code to copy:
#include <stdio.h>
#include <stdlib.h>
// function to return count of stairs in each set
of stairs.
int* climbing_Stairs(int arrs[], 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 index = 0;
int* res = (int*)malloc(n *
sizeof(int));
// maintaining to variables to
point at indices of 1 to calculate the difference between them to
give number of stairs.
int prev_index = 0, curr_index =
0;
for (int i = 1; i < N; i++)
{
if (arrs[i] ==
1) {
curr_index = i;
res[index++] = curr_index - prev_index;
prev_index = curr_index;
}
}
// this is handling the last set of
steps case as mentioned in the explanation above.
res[index] = N - curr_index;
return res;
}
int main()
{
// added this print statements for
clarity, remove if you want.
printf("Enter number of numbers :
\n");
int N;
scanf("%d", &N);
// arrsay to hold the sequence
of stairs.
int* arrs = (int*)malloc(N *
sizeof(int));
for (int i = 0; i < N; i++)
{
scanf("%d",
&arrs[i]);
}
// variable to store the number
of sets.
int no_of_Steps = 0;
for (int i = 0; i < N; i++)
{
if (arrs[i] ==
1) {
no_of_Steps++;
}
}
// calling the function to return
pointer to arrsay.
int* res1 = climbing_Stairs(arrs,
no_of_Steps, N);
printf("number of steps in each
set: \n");
// above print just for
clarity.
// below loop is printing the
res.
for (int i = 0; i < no_of_Steps;
i++) {
printf("%d ",
res1[i]);
}
printf("\n");
return 0;
}
Code Screenshot:
Output Screenshot: