Minimum Gifts

Introduction

In this article, we’ll write a program to find out the minimum number of gifts required by a company. This coding problem is one of the TCS Codevita's previous year's questions. 

Now let us understand the problem statement clearly.

Problem Statement

A company has decided to offer all of its staff presents. Each employee has a rank in the company as a result of this. The company has established specific regulations for the distribution of gifts based on that level.

The following are the rules for gift distribution:

• At least one gift must be given to each employee.
• Employees with higher ranks receive more gifts than their coworkers.

What is the minimum number of gifts required by the company?

Constraints

1 < T < 10

1 < N < 100000

1 < Rank < 10^9

Input

The First line contains integer T, denoting the number of test cases.

For each test case:

First-line contains integer N, denoting the number of employees.

The Second-line contains N space-separated integers, denoting the rank of each employee.

Output

For every test case, print the number of minimum gifts required by the company on a new line.

Now let us understand the statement with the help of an example.

Input

2
5
1 2 1 5 2
2
1 2

Output

7
3

Explanation

For test case 1, adhering to the rules mentioned above,

Employee - 1 whose rank is 1 gets one gift

Employee - 2 whose rank is 2 gets two gifts

Employee - 3 whose rank is 1 gets one gift

Employee - 4 whose rank is 5 gets two gifts

Employee - 5 whose rank is 2 gets one gift

Therefore, total gifts required is 1 + 2 + 1 + 2 + 1 = 7

Similarly, for testcase 2, adhering to rules mentioned above,

Employee - 1 whose rank is 1 gets one gift

Employee - 2 whose rank is 2 gets two gifts

Therefore, total gifts required is 1 + 2 = 3

Solution

Java Solution

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            int n = sc.nextInt();
            int[] ar = new int[n];
            for (int i = 0; i < n; i++)
                ar[i] = sc.nextInt();
            int[] gifts = new int[n];
            gifts[0] = 1;
            // Left to Right Neighbors
            for (int i = 1; i < n; i++) {
                if (ar[i] > ar[i - 1])
                   gifts[i] = gifts[i - 1] + 1;
                else
                    gifts[i] = 1;
            }
            // Right to Left Neighbors
            for (int i = n - 2; i >= 0; i--) {
                if (ar[i] > ar[i + 1] && gifts[i] <= gifts[i + 1])
                    gifts[i] = gifts[i + 1] + 1;
            }
            long total = 0;
            for (int gift : gifts)
                total += gift;
            System.out.println(total);
        }
    }
}

Output

2
5
1 2 1 5 2
2
1 2
7
3

C++ Solution

#include<bits/stdc++.h>
using namespace std;
long long arr[100010];
long long brr[100010];
int main()
{
  int t;
  cin >> t;
  for(int i = 1; i <= t; i++)
  {
    int n;
    long long gift_num = 0, temp = 0;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
      cin >> arr[i];
    }
    brr[0] = 1;
    for(int i = 1; i < n; i++)
    {
      if(arr[i] > arr[i-1])
      {
        brr[i] = brr[i-1] + 1;
      }
      else
      {
        brr[i] = 1;
      }
    }
   gift_num = brr[n-1];
    for(int i = n-2; i >= 0; i--)
    {
      if(arr[i] > arr[i+1])
      {
        temp = brr[i+1] + 1;
      }
      else
        temp = 1;
      gift_num = gift_num + max(temp, brr[i]);
      brr[i] = temp;
    }
    cout << gift_num << endl;
  }
  return 0 ;
}

You can also try this code with Online C++ Compiler

Run Code

Output

2
5
1 2 1 5 2
2
1 2
7
3

You can also try this code with Online C++ Compiler

Run Code