Minimum Price DSA Problem Solution

Minimum Price DSA Problem Solution

In this post, we are going to solve Minimum Price DSA Problem from Oracle, Online Assessments conducted on 13th October,2022. Let’s have a look at the problem statement first and then try to solve the problem.

Minimum Price DSA Problem Statement

There are N stones in a line . The cost and type of the ith stone is

ai units and i respectively. You are initially having zero stones and you wish to collect all the N types of stones type1,type2…….,typeN.

You can perform the following operation multiple times (probably zero) to change the type of all the stones in one step:

The stone of the type i will be changed to the type i+1. If i is N then change its type to 1 (

1iN)

Apply this operation single time cost x units.

Your task is to print the minimum price that you have to pay to get all N types of stones in your collection.

Input

The first line contains two integers N, and X. (

1N2000) (

0x109)

Next line N space-separated integers representing the price of each stone (

1ai109)

Output

For each output print the minimum price that you have to pay to get all N types of stones

Example
Input
3 5 
50 1 50
Output
13

Problem Solution in C++

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
ll n,x,res=2e18;
cin >> n >> x;
vector<ll> a(n),minn;
for(int i=0;i<n;i++){
cin >> a[i];
}
minn=a;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
minn[(i+j)%n]=min(minn[(i+j)%n],a[j]);
}
ll sum=x*i;
for(int j=0;j<n;j++){
sum+=minn[j];
}
res=min(res,sum);
}
cout << res;
return 0;
}