FastPrepFastPrep
Problem Brief

Newton's Beautiful Sequence

OA

Newton, a curious young mathematician, enjoys exploring the beauty of numerical sequences. Every evening, he sits under his favorite apple tree, contemplating the mathematical elegance hidden within sequences of numbers. To quantify the beauty of a sequence, Newton has created a unique method here’s how he does it:

The initial beauty of the sequence is set to 0.

For every possible contiguous segment of the sequence, he sorts the segment.

He then iterates over the elements of each sorted segment, comparing the current element with the next one, if it exists.

If the next element is greater than the current element by more than 1, he adds 1 to the beauty.

If the contiguous segment contains only 1 element, then it also increases the beauty by 1.

But computing it manually is time-consuming. Therefore, he asks you to write a program to help him in return for those delicious apples.

If the beauty value becomes very large, take the modulo with 109 + 7.

You need to write bruteforce solution only. There are bonus points for bruteforce solution (Don't panic some test cases will not pass for the brute force solution but you will be awarded points)

Input Format

First line of input is the integer n denoting the size of the sequence.

The next line contains n space separated integers denoting the elements of the sequence.

Output Format

Return an integer representing the beauty of the sequence modulo 109 + 7

Another question is same as this question, but it asks for the optimal approach and also the constraints are changed.

Constraints for the other question that asks for optimal approach -

  • 1 ≤ N ≤ 10^5
  • 1 ≤ sequence[i] ≤ N
    •

    1Example 1

    Input
    sequence = [2, 2, 2, 1, 5]
    Output
    9
    Explanation

    The contiguous segments-> [2,2,2,1,5], [2,2,1,5], [2,1,5], [1,5], [5], [2,2], [2,1], [1,5], [5], [2], [2], [1], [5] will become [1,2,2,2,5], [1,2,2,5], [1,2,5], [1,5], [5], [2], [2], [1], [5] respectively.

    The first 4 adds 1 each to the beauty because the difference between 2 and 5 is greater than 1. Rest any pair does not adds to the beauty from these 4 segments.

    The last 5 mentioned segments also adds 1 each to the beauty since they contain only 1 element.

    Rest any contiguous segment has 0 contribution to the beauty of the array.

    Constraints

    Limits and guarantees your solution can rely on.

    1 ≤ N ≤ 103
    1 ≤ sequence[i] ≤ N
    public int calculateSequenceBeauty(int[] sequence) {
  // write your code here
}
    Input

    sequence

    [2, 2, 2, 1, 5]

    Output

    9

    Sign in to submit your solution.