Large Sub-Arrays | Hackerearth

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

 

 

Sree Hari Sanjeev

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

Leave a Reply

Your email address will not be published. Required fields are marked *