Large Sub-Arrays | Hackerearth

Question
You are given an array A with size N and two integers M and K.
Let’s define another array B with size N×M as the array that’s formed by concatenating M copies of array A.
You have to find the number of sub-arrays of the array B with sum ≤K.
Input Format:
The first line contains an integer T denoting the number of test cases.
The first line of each test case contains 3 space separated integers N and M and K.
Next line contains N space separated integers denoting the array elements.
Output Format:
For each test case, print the required answer in a new line.
Logic
- Get the Number of test cases and get N, M, K for each test case
- Get the array elements and concatenate M copies and store in the new array.
- Generate all the sub-arrays and find sum by adding the elements of sub-array.
- Increase the count if the sum<= k for any sub-array.
- Print the output and continue the next test case.
Program
[code lang=”c”]
#include<iostream>
using namespace std;
int main()
{
int flag=1,n,m,l,i,j,k,count=0,sum,t;
int *arr1;
int *arr2;
cin>>t;
while(t)
{ t–; //decrease test case count
cin>>n>>m>>k;
count=0;
arr1 = new int[n]; //dynamic allocation
arr2 = new int[n*m]; //array of size N*M
for( i=0;i<n;i++)
{
cin>>arr1[i];
}
/*concatenating M copies of array*/
l=0;
for(i=0;l<n*m;i++) //run till concatenation finish
{ //Ex: n=3,m=2 then result array contain 6 elements
ar[l]=arr[i];
if(i==n-1)
{
i=-1; //resetting array index if reached end
}
l++;
}
/*Using two loops to generate all combinations of sub-array
* Ex: Sub-arrays of {1,2,3} are {1}{1,2}{1,2,3}{2}{2,3}{3} */
for(i=0;i<n*m;i++)
{
sum =0 ; //reset sum for new sub array
for(j=i;j<n*m;j++)
{
sum += ar[j]; //increase sum of sub-array
if(sum<=k)
{
count++;
}
else
break; //sub-array sum exceeded given
}
}
cout<<count<<‘\n’; //print output for each test case
}
return 0;
}
[/code]
You might also like…
To find the next greater element in an array