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

You might also like…

To find the next greater element in an array