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.)

Please write the code in the comments? We will add them here.

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

    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.