To make elements of array equal

#1

there are two arrays are given first array is having lengths of n sticks and another array have cost to change the length of stick by one unit(either increase or decrease) such that 1st index value of 2nd array is cost for 1st index length stick. we have to make all sticks of equal lenght at minimum cost and to print minimum cost . what approach should i follow for this question.

#2

can we decrease/increase lenght by one unit or by any other unit
Also post the question for more clarification

#3

Bhaiya at single time we can decrease it by only one unit. It was my placement paper question bhaiya dats y cant post it.

#4

But i can give u examples suppose 1st array is { 1 2 3} and 2nd cost array is { 10 20 30 }
Then we eill first incease th 0th stick cost= 10 array will become 2 2 3 , den next iteration we can decrse 2nd index by one nd cost will become 40 rs with final array as 2 2 2 but v can also do other chnges nd in last v hve to choos minimum cost operation

#5

check this its complexity is o(n^2 ),is it ok according to given constraint or should be reduced
https://ide.codingblocks.com/#/s/20040
And of which company this question is?

#6

American express was the company. Can we do this by dynamic programming also ?? If yes please share the code of that also bhaiya.

#7

sir this link do not have any code please look at it

#8

ya its not saving
check this

#9

#include <bits/stdc++.h>
using namespace std;
bool compare(pair<int,int> a,pair<int,int> b){

if(a.first==b.first){
return a.second<b.second;
}
else{
return a.first<b.first;
}
}
int main()
{
int n;cin>>n;
int a[100],b[100];
for(int i=0;i<n;i++)cin>>a[i];
for(int i=0;i<n;i++)cin>>b[i];
pair<int,int>p[100];
for(int i=0;i<n;i++){
p[i]=make_pair(a[i],b[i]);
}
sort(p,p+n,compare);
long long int ans=INT_MAX;
int startingLenght=p[0].first;
int endingLenght=p[n-1].first;
for(int i=startingLenght;i<=endingLenght;i++){
long long int mincost=0;
for(int j=0;j<n;j++){
long long int M=abs(p[j].first-i);
mincost+=(M*p[j].second);
}
ans=min(ans,mincost);
}
cout<<ans;
return 0;
}

#10

#include <bits/stdc++.h>

using namespace std;

bool cmp(pair<int,int> a,pair<int,int> b){

if(a.first==b.first){

return a.second<b.second;

}

else{

return a.first<b.first;

}

}

int main()

{

int n;

cin>>n;

int a[n]={2,1,3,4};

int b[n]={30,20,40,50};

pair<int,int>p[n];



for(int i=0;i<n;i++)

{

   p[i]= make_pair(a[i],b[i]);

}



sort(p,p+n,cmp);

int mid=0;



if(n%2==0)

    mid=p[n/2].first;

   //cout<<p[n/2].first;

else

    mid=p[(n-1)/2].first;



int res=0;

// cout<<mid;

for(int i=0;i<n;i++)

{

    res=res+(abs(p[i].first-mid))*p[i].second;

}

cout<<res;

// your code goes here



return 0;

}

#11

This ones is O(n) solution it works , I am not sure about edge cases.

#12

def minCost(self, nums: List[int], cost: List[int]) -> int:

l = sorted([(nums[i], cost[i]) for i in range(len(nums))])

lef = [0]

last = l[0][1]

# print(l)

for i in range(1, len(nums)):

    lef.append(lef[-1] + last*(l[i][0]-l[i-1][0]))

    last += l[i][1]

right = [0]

last = l[-1][1]

for i in range(len(nums)-2, -1, -1):

    right.append(right[-1] + last*(l[i+1][0] - l[i][0]))

    last += l[i][1]

mini = float("inf")

right = right[::-1]

for i in range(len(lef)):

    mini = min(mini, lef[i] + right[i])

return mini