 # Editorial: Learning Sprint-1 (CodeChef College Chapters - Beginner Track)

Contest Link: Learning Sprint-1 (Beginner Track)

Problem: Print Sub-Array
Problem Setter: @vok_8

Tutorial

We have to just input the array and print the array from position `l` (index `l-1`) to position `r` (index `r-1`).

Algorithm Snippet (If input of array is in 0-indexing)
``````for i=l-1 to i=r-1
{
print(a[i])
}
``````
Algorithm Snippet (If input of array is in 1-indexing)
``````for i=l to i=r
{
print(a[i])
}
``````

• Time Complexity: `O(n)`

• Space Complexity: `O(n)` (Also, possible in `O(1)`)

Problem Setter's Code (C++)
``````#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int arr[n];
for(int i=0; i<n; i++) //0-indexing
{
cin>>arr[i];
}
int l,r;
cin>>l>>r; //Input is in 1-indexing (Position)
for(int i=l-1; i<=(r-1); i++) //0-indexing
{
cout<<arr[i]<<" ";
}
cout<<"\n";
return 0;
}
``````

Problem: Derive Good String
Problem Setter: @vok_8

Hint-1

We don’t have to do anything about the characters which only occur once.

Hint-2

Also, we don’t have to do anything about the characters which don’t occur in the string.

Tutorial

We only need to remove `x-1` occurrences of all the characters, which occur `x` times, where `x>1`.

• Time Complexity: `O(string length)`, per test case.

• Space Complexity: `O(string length)`, per test case. (Also, possible in `O(1)`, per test case)

Problem Setter's Code (C++)
``````#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t; //'t' test cases
while(t--)
{
string s;
cin>>s;
int n=int(s.length());
int countt; //to store count of characters
for(int i=0; i<26; i++) //initialise count of all characters to 0
{
countt[i]=0;
}
for(int i=0; i<n; i++) //traverse the string to derive count of all characters
{
int index_of_character=s[i]-'a'; //for 'a'=0, 'b'=1, 'c'=2, .. , 'z'=25
countt[index_of_character]++;
}
int ans=0;
for(int i=0; i<26; i++)
{
if(countt[i]>1) //if count of character is > 1
{
ans+=(countt[i]-1);
}
}
cout<<ans<<"\n";
}
return 0;
}
``````

Problem: Get on the String
Problem Setter: @vok_8

Hint

There is only `1` subsequence of length `n` for a string, of length `n`.

Tutorial

Since, there is only `1` subsequence of length `n` for a string, of length `n`, the answer will be the string itself.

• Time Complexity: `O(n)`

• Space Complexity: `O(n)` (Also, possible in `O(1)`)

Problem Setter's Code (C++)
``````#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
string s;
cin>>s;
cout<<s<<"\n";
return 0;
}
``````

Problem: Is Sum Possible
Problem Setter: @vok_8

Hint-1

The minimum sub-array sum will be `0` and maximum sub-array sum will be `100*n`, for the given array, according to the given constraints.

Hint-2

Pre-compute the sub-array sums and the store the count of each sub-array sum (in `O(n^2)` or `O(n^3)`), before the queries, so that you don’t have to compute the count of queried sum, for each query.

Tutorial

Pre-compute the sub-array sums and the store the count of each sub-array sum (in `O(n^2)` or `O(n^3)`), before the queries, so that you don’t have to compute the count of queried sum, for each query.

For each query,

• If x<0 or x>100*n, output `0`. (Since those sums aren’t possible for any sub-array of given array)
• Else, output the pre-computed count.

• Time Complexity: `O(n^3)` (Also, possible in `O(n^2)`)

• Space Complexity: `O(n)`

Problem Setter's Code (C++)
``````#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int arr[n];
for(int i=0; i<n; i++) //get the array input
{
cin>>arr[i];
}
int countt[(100*n)+1]; //to store count of possible sub-array sums, of given array
for(int i=0; i<(100*n)+1; i++) //initialise values in countt[] array
{
countt[i]=0;
}
for(int l=0; l<n; l++) //precompute count of possible sub-array sums (in O(n^3))
{
for(int r=l; r<n; r++)
{
int sum_of_subarray_from_l_to_r=0;
for(int ind=l; ind<=r; ind++) //to calculate sub-array sum of sub-array [l,r]
{
sum_of_subarray_from_l_to_r+=arr[ind];
}
countt[sum_of_subarray_from_l_to_r]++; //increment the count of current sub-array sum
}
}
int q;
cin>>q; //input 'q', the number of queries
{
int x;
cin>>x;
if(x<0 || x>(100*n)) //case when 'x' isn't a possible sum of any sub-array of the given array
{
cout<<0<<"\n";
}
else
{
cout<<countt[x]<<"\n";
}
}
return 0;
}
``````