Question

Assume you have a necklace of stones. Some of the stones have positive value and some have negative value. You have the opportunity to snip the necklace in two places (creating two bands) and weld the endpoints of one of the two bands back into a necklace. You would like your new necklace to be as valuable as possible. You can assume the necklace has n stones with values O,,vn-1. (1) Give an efficient algorithm to find the value of the new necklace. If all of the stones have negative value your answer should be 0. Make your algorithm as clean and elegant as possible (2) Give an efficient algorithm to determine where you should snip the original necklace (not just its value). Make your algorithm as clean and elegant as possible. If all of the values are positive you should not snip and your algorithm should print: Do not snip. If all of the values are negative you should not snip and your algorithm should print: Throw the necklace away. If possible the algorithm should determine these two situations without explicitly checking for them

Answer 1

#include <iostream>
#include <vector>
using namespace std;
int find_value_of_necklace(vector<int> temp)//function to find new value of necklace
{
    int ret = 0;//return value
    bool negative = 1;//initialy we assume all values are negative
    for (auto it = temp.begin(); it != temp.end(); it++)
    {
        if (*it >= 0)//if any value is positive
            negative = 0;//negative=false
        ret += *it;
    }
    if (negative)//if all values are negative
        return 0;
    return ret;
}
void should_snip(vector<int> temp)//function to calculate if i should snip necklace or not
{
    bool negative = 1, positive = 1;//initially we
    for (auto it = temp.begin(); it != temp.end(); it++)
    {
        if (*it >= 0)//if any value is positive
            negative = 0;
        if (*it < 0)//if any value is negative
            positive = 0;
    }
    if (negative)//if all values are neagtive
    {
        cout << "Throw the necklace away\n";
        return;
    }
    if (positive)//if all values are positive
    {
        cout << "Do not snip\n";
        return;
    }
    cout << "Snip\n";
}
int main()
{
    vector<int>necklace;
    int size,temp;
    cout<<"Enter number of stones in necklace\t";
    cin>>size;
    cout<<"Enter space saparated value of stones\n";
    for(int i=0;i<size;i++)
    {
        cin>>temp;
        necklace.push_back(temp);
    }
    cout<<"New value of necklace is\t"<<find_value_of_necklace(necklace)<<endl;
    should_snip(necklace);
}

Enter number of stones in necklace Enter space saparated value of stones New value of necklace is Do not snip PS Efixer> a. exe Enter number of stones in neck lace Enter space saparated value of stones 1 2 34 5 New value of necklace is Do not snip PS Efixer> a. exe Enter number of stones in neck lace Enter space saparated value of stones 0 New value of necklace is Throw the necklace away PS E:fixer .a.exe Enter number of stones in neck lace Enter space saparated value of stones 1 2 3-9 4 New value of necklace is Sni p 0

COMMENT DOWN FOR ANY QUERY

PLEASE GIVE A THUMBS UP