Doubt in problem

#1

In this question what is the logic which I should apply?
Please give me some kickstart so that I can think over the problem that how to code it?

#2

Hey @yashsharma4304

Think of it this way. There are three possibilities in total

The sequence is completely increasing.
The sequence is completely decreasing
The sequence is first decreasing then increasing.
These are the three situations where we print true or else we print false.
If we plot the graph for the three situations the first one will be a simple increasing curve.
The second one will be a simple decreasing curve.
Both of these cases can be checked and verified using a simple loop.

The only case you are left to check now is the third one which forms a V-like graph , first decreasing then increasing.
To check this we can see how many turning points are there in the sequence. A turning point would be the element before which all elements were increasing and from thereon start decreasing or before which all elements were decreasing and then start increasing.
Assume your sequence to be decreasing at first since that is specified in the problem that the sequence is first decreasing. After that check for such turning points. From the graph we can infer that this would be the lowermost point in the V-graph. Also there would be only one such point atmost and no more. So simply count such turning points. Check if the no of turning points is more than 1. If so , print false. Else print true.

1 Like
#3

Ok. Thank you :slightly_smiling_face:

1 Like
#4

Hello, Please explain me the logic of this problem? How many variables should I take? How should I handle this problem ? Explain me its pseudocode.

#5

hello @yashsharma4304

About the input, you need not to take array, one can also perform the question without using array. As every time we just check two consecutive numbers to tell whether the seqeunce is increasing or decreasing, so why should we store all of the numbers.

  • A sequence is true if you can split it into two sub sequence such that first sequence is strictly increasing and second sequence is strictly decreasing.
  • For e.g.,
    1 2 3 4 5
    This sequence is also true as we can split it into two sequence like., sequence one is empty and sequence two is 1 2 3 4 5.
  • Let’s take another example.,
    5 4 3 2 1
    This is also true as we can split it such that sequence one is5 4 3 2 1 and sequence two is empty.
    According to the problem statement, we can say the if the sequence decreases then it should not increase, if this is the case one can directly print false else print true.
  • The third case is when the sequence is first strictly decreasing then strictly increasing.
    For example :
    9 5 2 7 10
    The sequence first decreases starting from 9 to 2 - { 9, 5, 2 } and then starts increasing - { 7, 10}. Note that it can also be broken as { 9, 5} and { 2, 7, 10} .
    Since the sequence fulfills the required condition , we would also print “true” for this.

If a sequence does not meet any of the above criteria , we return “false” for it.

Implementation : First we assume that our sequence is decreasing only. We also assume that our sequence is initially valid and only try to disprove it during the course.
We compare our current element with the previous element and based on that comparison make our decision.
If the curr element is equal to the prev element , we see that the sequence is neither strictly increasing or decreasing so we mark our sequence as invalid.
If the curr element is greater than the prev element, then we realise that the sequence has started increasing and we mark it so using a flag variable “goingUp” which we had initially marked as false based on our assumption that the sequence is decreasing.
If the curr element is less than the previous element and the current sequence is also proceeding as decreasing , we are to do nothing. However if the current sequence is increasing and we get a pair for a decreasing sequence then we mark our sequence as invalid since we cannot have a decreasing part after the increasing sequence.
After each iteration , store the value of the curr element into the prev element so that we can compare it with the next input element.

bool increasingDecreasing(int n)
{
    int prev;
    cin >> prev;

    bool isValid = true;
    bool isDecreasing = true;

    while (--n)
    {
        int curr;
        cin >> curr;
        if (curr == prev)
        {
            isValid = false;
            break;
        }
        else if (curr > prev)
        {
            isDecreasing = false;
        }
        else if (!isDecreasing && curr < prev)
        {
            isValid = false;
            break;
        }

        prev = curr;
    }

    return isValid;
}
1 Like
#6

Ok so prev is nothing but the first number from which we have to start compare. And then again inside the loop we have taken the second number with which we are going to compare. And at the end of loop eachtime the current value is assigned to previous value so that it can be compared with the next number. By the way the explanation was really awesome. Really thank you :heavy_heart_exclamation:

#7

yeah correct… … … …

1 Like