/* [Challenge] Sorting Weights Bobby has some mice. He took some of them randomly and arranged them in a horizontal container. Each of them has weight (w_i). Bobby saw his container and noticed that these mice’s weights are randomly ordered. Assuming Bobby has infinitely many mouse with every number of weights, is it possible to replace just ONE mouse in the container with one of his other mouse so that their weights are sorted in non-decreasing order? Given an array of integers (W) consisting of each mouse’s weight (w_i), return True if it is possible to make the weights sorted, otherwise return False. Example: Input: W = [5, 2, 3] Output: True Change 5 to 1 or 2, W becomes non-decreasing. Input: W = [5, 3, 2] Output: False Please solve it in linear time. */ #include #include #include using namespace std; template bool IsSorted_Error(array input) { int downCnt = 0; int val = input[0]; for(int i = 1;i<(int)N;++i) { if(val>input[i]) ++downCnt; val = input[i]; } //if(downCnt>=2 || upCnt>=2) if(downCnt>=2) return false; return true; } template bool IsSorted(array input) { multiset ms; int val = input[0]; for(int i = 1;i<(int)N;++i) { cout << val << ":" << input[i] << endl; if(input[i]>=val) { ms.insert("Increased"); val = input[i]; } else { // assume that we already replaced here..... so, placing mouse weight which is less than one of current mouse's weight... we need non decreasing order so just keeping it as same as current one int newVal = input[i]; val = newVal; } } cout << ms.count("Increased") << endl; if(ms.count("Increased")>=(N-2)) return true; return false; } int main() { // Result is true //const int N = 3; //array input = {5,2,3}; // Result is false //const int N = 3; //array input = {5,3,2}; // Result is false //const int N = 4; //array input = {9,5,1,3}; // Result is false //const int N = 4; //array input = {1,9,7,8}; // Result is false const int N = 4; array input = {3,4,2,3}; // Result is True //const int N = 4; //array input = {1,6,4,5}; cout << boolalpha << IsSorted(input); return 0; }

Challenge_Sorting_Weight