Chocolate Distribution Problem | Set 2 | Function to return minimum number of chocolates ; decreasing sequence ; add the chocolates received by that person ; end point of decreasing sequence ; val = 1 reset value at that index ; increasing sequence ; flat sequence ; add value of chocolates at position n - 1 ; Helper function to get sum of decreasing sequence ; value obtained from decreasing sequence also the count of values in the sequence ; assigning max of values obtained from increasing and decreasing sequences ; sum of count - 1 values & peak value sum of natural numbers : ( n * ( n + 1 ) ) / 2 ; Driver code
def minChocolates ( a , n ) : NEW_LINE INDENT i , j = 0 , 0 NEW_LINE val , res = 1 , 0 NEW_LINE while ( j < n - 1 ) : NEW_LINE INDENT if ( a [ j ] > a [ j + 1 ] ) : NEW_LINE INDENT j += 1 NEW_LINE continue NEW_LINE DEDENT if ( i == j ) : NEW_LINE INDENT res += val NEW_LINE DEDENT else : NEW_LINE INDENT res += get_sum ( val , i , j ) NEW_LINE DEDENT if ( a [ j ] < a [ j + 1 ] ) : NEW_LINE INDENT val += 1 NEW_LINE DEDENT else : NEW_LINE INDENT val = 1 NEW_LINE DEDENT j += 1 NEW_LINE i = j NEW_LINE DEDENT if ( i == j ) : NEW_LINE INDENT res += val NEW_LINE DEDENT else : NEW_LINE INDENT res += get_sum ( val , i , j ) NEW_LINE DEDENT return res NEW_LINE DEDENT def get_sum ( peak , start , end ) : NEW_LINE INDENT count = end - start + 1 NEW_LINE peak = max ( peak , count ) NEW_LINE s = peak + ( ( ( count - 1 ) * count ) >> 1 ) NEW_LINE return s NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT a = [ 5 , 5 , 4 , 3 , 2 , 1 ] NEW_LINE n = len ( a ) NEW_LINE print ( ' Minimum ▁ number ▁ of ▁ chocolates ▁ = ' , minChocolates ( a , n ) ) NEW_LINE DEDENT