# HackerRank Coding Question for Placements 3

We are given a count of songs to be played – n, highest volume allowed – h, initial volume – i, and list of allowed volume change A[] of size n. The singer can either increase/decrease the volume of sound system for the next song by the allowed volume change A[j] for jth song from the volume of the j-1th song. The aim is to maximize the volume of last sound. Find the maximum volume that can be attained, or return -1 if there is no possibility of changing volume due to the given constrains. (Volume cannot be in negative.)

### 6 comments on “HackerRank Coding Question for Placements 3”

• saketh

static int maxvalue=-1;
public static void count(int a[],int low,int high,int index,int curr)
{
if(index==0)
{
if(curr+a[index]>high || curr+a[index]high || curr<low)
return;
maxvalue=Math.max(maxvalue, curr);

if(index==a.length)
return;

count(a, low, high, index+1, curr+a[index]);
count(a, low, high, index+1, curr-a[index]);
}
O(n*max) time complexity using DP approach

• saketh

I used inclusion and exclusion in DP

• saketh

The approach to this question is that
( i ) if we increase or decrease the volume for the songs from 1 to n-1 it shouldn’t cross h-A[last_song] since for attaining the maximum sound we have to increase the volume of the last song.
( ii ) consider a prefix sum array which stores the sum of the volume change from i+1th song to n-1th volume change. This array will help you while decrementing the volume. All we have to do while decrement is to check if the present_volume(p)-A[i]+prefix sum>max-A[last_volume_change].
( iii ) Use dynamic programming for reducing the time complexity.
I think using these hints we can solve the question.

• PrepInsta