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

#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;
}


Sree Hari Sanjeev

The founder of Wisdom Overflow. Software Developer at Zoho Corporation.