Given N number of students sitting in a line and each of them is having marks they got scored in the exam. The task is to distribute teddy as they satisfy given conditions
- All students must have at least 1 teddy
- If two students sit next to each other then the one with the higher marks must get more teddies.
So, the task is to minimize the total number of teddies.
Examples:
Input: n = 3, marks = [ 1, 2, 2 ] Output: 4 Here 1, 2, 2 is the marks. Note that when two students have equal marks they are allowed to have a different number of teddies. Hence optimal distribution will be 1, 2, 1. Input: n = 6, marks = [ 1, 4, 5, 2, 2, 1 ] Output: 10
Approach: The approach is to use the dynamic programming to solve given problem:
- Initialize the table of size n.
- Run loop for n times.
- If left adjacent student is having higher marks review and change all the table values assigned before as solution until assigned table values as a solution are found wrong according to given constraints.
- If right adjacent student is having higher marks add one in solution for left adjacent and assign to solution for right one.
Below is the implementation of the above approach:
C++
// C++ implementation of the// above approach#include<bits/stdc++.h>using namespace std;long long fun(int marks[],int n){ // Initializing one tablet // for each student long long dp[n], temp; fill(dp, dp + n, 1); for(int i = 0; i < n - 1; i++) { // if left adjacent is having // higher marks review and change // all the dp values assigned before // until assigned dp values are found // wrong according to given constrains if (marks[i] > marks[i + 1]) { temp = i; while (true) { if ((marks[temp] > marks[temp + 1]) && temp >= 0) { if (dp[temp] > dp[temp + 1]) { temp -= 1; continue; } else { dp[temp] = dp[temp + 1] + 1; temp -= 1; } } else break; } } // if right adjacent is having higher // marks add one in dp of left adjacent // and assign to right one else if( marks[i] < marks[i + 1]) dp[i + 1] = dp[i] + 1; } int sum = 0; for(int i = 0; i < n; i++) sum += dp[i]; return sum;}// Driver Codeint main(){ // n number of students int n = 6; // marks of students int marks[6] = { 1, 4, 5, 2, 2, 1}; // solution of problem cout << fun(marks, n); return 0;}// This code is contributed by ash264 |
Java
// Java implementation of the // above approach public class GFG { static long fun(int marks[],int n) { // Initializing one tablet // for each student long dp[] = new long[n] ; int temp; for (int i = 0;i < n;i ++) dp[i] = 1 ; for(int i = 0; i < n - 1; i++) { // if left adjacent is having // higher marks review and change // all the dp values assigned before // until assigned dp values are found // wrong according to given constrains if (marks[i] > marks[i + 1]) { temp = i; while (true) { if ((marks[temp] > marks[temp + 1]) && temp >= 0) { if (dp[temp] > dp[temp + 1]) { temp -= 1; continue; } else { dp[temp] = dp[temp + 1] + 1; temp -= 1; } } else break; } } // if right adjacent is having higher // marks add one in dp of left adjacent // and assign to right one else if( marks[i] < marks[i + 1]) dp[i + 1] = dp[i] + 1; } int sum = 0; for(int i = 0; i < n; i++) sum += dp[i]; return sum; } public static void main(String args[]) { // n number of students int n = 6; // marks of students int marks[] = { 1, 4, 5, 2, 2, 1}; // solution of problem System.out.println(fun(marks, n)); } // This code is contributed by ANKITRAI1} |
Python 3
# Python implementation of the above approachdef fun(marks, n): # Initializing one tablet for each student dp = [ 1 for i in range(0, n) ] for i in range(0, n-1): # if left adjacent is having higher marks # review and change all the dp values assigned before # until assigned dp values are found wrong # according to given constrains if marks[i] > marks[i + 1]: temp = i while True: if marks[temp] > marks[temp + 1] and temp >= 0: if dp[temp] > dp[temp + 1]: temp -= 1 continue else: dp[temp] = dp[temp + 1] + 1 temp -= 1 else: break # if right adjacent is having higher marks # add one in dp of left adjacent and assign to right one elif marks[i] < marks[i + 1]: dp[i + 1] = dp[i] + 1 return(sum(dp))# driver code# n number of studentsn = 6# marks of studentsmarks = [ 1, 4, 5, 2, 2, 1]# solution of problemprint(fun(marks, n)) |
C#
// C# implementation of the // above approach using System; class GFG { public static long fun(int[] marks,int n) { // Initializing one tablet // for each student long[] dp = new long[n]; long temp; for(int i = 0; i < n; i++) dp[i] = 1; for(int i = 0; i < n - 1; i++) { // if left adjacent is having // higher marks review and change // all the dp values assigned before // until assigned dp values are found // wrong according to given constrains if (marks[i] > marks[i + 1]) { temp = i; while (true) { if ((marks[temp] > marks[temp + 1]) && temp >= 0) { if (dp[temp] > dp[temp + 1]) { temp -= 1; continue; } else { dp[temp] = dp[temp + 1] + 1; temp -= 1; } } else break; } } // if right adjacent is having higher // marks add one in dp of left adjacent // and assign to right one else if( marks[i] < marks[i + 1]) dp[i + 1] = dp[i] + 1; } long sum = 0; for(int i = 0; i < n; i++) sum += dp[i]; return sum; } // Driver Code static void Main() { // n number of students int n = 6; // marks of students int[] marks = new int[]{ 1, 4, 5, 2, 2, 1}; // solution of problem Console.Write( fun(marks, n) ); } //This code is contributed by DrRoot_} |
Javascript
<script> // Javascript implementation of the above approach function fun(marks, n) { // Initializing one tablet // for each student let dp = new Array(n); let temp; for(let i = 0; i < n; i++) dp[i] = 1; for(let i = 0; i < n - 1; i++) { // if left adjacent is having // higher marks review and change // all the dp values assigned before // until assigned dp values are found // wrong according to given constrains if (marks[i] > marks[i + 1]) { temp = i; while (true) { if ((marks[temp] > marks[temp + 1]) && temp >= 0) { if (dp[temp] > dp[temp + 1]) { temp -= 1; continue; } else { dp[temp] = dp[temp + 1] + 1; temp -= 1; } } else break; } } // if right adjacent is having higher // marks add one in dp of left adjacent // and assign to right one else if( marks[i] < marks[i + 1]) dp[i + 1] = dp[i] + 1; } let sum = 0; for(let i = 0; i < n; i++) sum += dp[i]; return sum; } // n number of students let n = 6; // marks of students let marks = [ 1, 4, 5, 2, 2, 1]; // solution of problem document.write( fun(marks, n) ); // This code is contributed by divyesh072019.</script> |
Output:
10
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
