Question

Cisco | OA Coding Questions and Solutions | Set - 13 | 2022

Answer 1

Can anyone share the approach for solving this Problem?
Please share Any Other Similer Problem you have ever solved so that I practice.

Answer 2

/**
 * @brief for ith index prefixCost gives the cost of setting the stick length to ith length from (1st to ith) element
 * @param curr_single_length is the total cost to increase or decrease all the 1 st to i-1th length to 1 unit
*/

void findPrefixCost(vector<int> &prefixCost, vector<pair<int, int>> &sticks)
{
    int n = prefixCost.size();
    prefixCost[0] = 0;
    int curr_single_length = sticks[0].second;
    for (int i = 1; i < n; i++)
    {
        int diff = sticks[i].first - sticks[i - 1].first;
        prefixCost[i] = prefixCost[i - 1] + diff * curr_single_length;
        curr_single_length += sticks[i].second;
    }
}

/**
 * @brief for ith index suffixCost gives the cost of setting the stick length to ith length from (ist to end) element
 * @param curr_single_length is the total cost to increase or decrease all the i+1 th to end length to 1 unit
*/

void findSuffixCost(vector<int> &suffixCost, vector<pair<int, int>> &sticks)
{
    int n = suffixCost.size();
    suffixCost[n - 1] = 0;
    int curr_single_length = sticks[n - 1].second;
    for (int i = n - 2; i >= 0; i--)
    {
        int diff = sticks[i + 1].first - sticks[i].first;
        suffixCost[i] = suffixCost[i + 1] + diff * curr_single_length;
        curr_single_length += sticks[i].second;
    }
}

int magicSticks(int n, vector<int> &len, vector<int> &cost)
{
    vector<pair<int, int>> sticks;
    for (int i = 0; i < n; i++)
    {
        sticks.push_back({len[i], cost[i]});
    }
    sort(sticks.begin(), sticks.end());
    vector<int> prefixCost(n), suffixCost(n);
    findPrefixCost(prefixCost, sticks);
    findSuffixCost(suffixCost, sticks);
    int ans = 1e9;
    for (int i = 0; i < n; i++)
    {
        ans = min(ans, prefixCost[i] + suffixCost[i]);
    }
    return ans;
}

Answer 3

For this type of questions, i.e. minimal cost to equalize a list of numbers, the key is to note that

 

the minmum cost is always achieved when the equal length = one number from the list

 

e.g. if sticks' heights are [1,4,7], the equal length with minimum cost must be one from 1,4,7, rather than those from 0,5,6,8. etc. Try to prove it by contradiction.

 

With this obseration, sort stick heights, for every possible height, calculate the total cost to equalize all sticks in O(n), and then pick the smallest cost.

def magic(n,sticks,cost):
#costs=[0]*n #cost[i] is the cost to make all sticks equal to stick[i] length

 

prices=set()

for i in range(len(sticks)):
    req=sticks[i]
    
    tot=0
    
    for j in range(len(sticks[:i])):
        k=sticks[j]

        while(k<req):
            k+=1
            tot+=cost[j]
        
        while(k>req):
            k-=1
            tot+=cost[j]

    for j in range(i+1,len(sticks)):
        k=sticks[j]

        while(k<req):
            k+=1
            tot+=cost[j]
        
        while(k>req):
            k-=1
            tot+=cost[j]

    prices.add(tot)
return min(prices)       

 

print(magic(2,[1,2],[10,20]))
print(magic(3,[1,2,3],[20,30,40]))