Проверьте, образуют ли элементы массива заданного диапазона перестановку

Опубликовано: 25 Февраля, 2023

Для заданного массива arr[] , состоящего из N различных целых чисел, и массива Q[][2], состоящего из M запросов вида [L, R] , задача для каждого запроса состоит в том, чтобы проверить, находятся ли элементы массива в диапазоне [L, R]. R] образует перестановку или нет.

Примечание. Перестановка — это последовательность длины N, содержащая каждое число от 1 до N ровно один раз. Например, (1), (4, 3, 5, 1, 2) являются перестановками, а (1, 1), (4, 3, 1) — нет.

Примеры:

Input: arr[] = {6, 4, 1, 2, 3, 5, 7}, Q[][] = {{2, 4}, {0, 4}, {1, 5}}
Output: 
YES
NO
YES
Explanation: Query 1: The elements of the array over the range [2, 4] are {1, 2, 3} which forms a permutation. Hence, print “YES”.
Query 2: The elements of the array over the range [0, 4] are {6, 4, 1, 2} which does not forms an permutation. Hence, print “NO”.
Query 3: The elements of the array over the range [1, 5] are {4, 1, 2, 3, 5}, which form an permutation. Hence, print “YES”.

Input: arr[] = {1, 2, 4, 3, 9}, Q[][] = {{0, 3}, {0, 4}}
Output: 
YES
NO

Наивный подход: основной способ решения проблемы заключается в следующем:

Traverse the given array over the range [L, R] for each query and check if every element is present or not from 1 to R – L + 1. This can be done by taking the sum of all elements from L to R if it is equal to the sum of 1 + 2 + 3 + 4 + . . . . + size of subarray [L, R], then print “YES”. Otherwise, print “NO”.

Временная сложность: O(N * M)
Вспомогательное пространство: O(1)

Эффективный подход. Описанный выше подход может быть оптимизирован на основе следующей идеи:

The idea is rather than calculating the sum of elements from L to R for each query precomputation can be done using the prefix sum. For Each query Q sum from L to R can be found in O(1) time using prefix sum.

The sum from 1 + 2 + 3 + 4 + . . . + size of subarray [L, R] can be found using the number theory formula for finding the sum of the first n natural numbers which is n * (n + 1) / 2. 

Выполните следующие шаги, чтобы решить проблему:

  • Инициализировать массив (например , prefix[] ) для хранения суммы префиксов массива
  • Чтобы заполнить массив суммы префикса, мы проходим по индексу от 1 до N и продолжаем добавлять текущий элемент с предыдущим значением в массив суммы префикса.
  • Пройдите заданный массив запросов Q[] и для каждого запроса {L, R} .
    • Инициируйте переменную размера и заполните R – L + 1 , что является размером подмассива [L, R] .
    • Инициируйте переменную total_From_1_To_Size , значение которой будет заполнено n * ( n + 1) / 2 .
    • Инициируйте переменную total_From_L_To_R , значение которой будет найдено с использованием предварительно вычисленного префикса массива[] .
    • Если total_From_L_To_R и total_From_1_To_Size равны, выведите « YES », иначе выведите « NO ».

Ниже приведена реализация вышеуказанного подхода:

C++




// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if the given range
// of queries form an Permutation or not
// in the given array arr[]
void findPermutation(int arr[], int N,
                     int Q[][2], int M)
{
    // Precomputation array
    // stores the sum of all ranges
    // for any L to R
    int prefix[N + 1] = { 0 };
 
    // Iterates over the range [1, N]
    for (int i = 1; i <= N; i++) {
 
        // Finding prefix sum of
        // given array
        prefix[i] = prefix[i - 1] + arr[i - 1];
    }
 
    // Traverse the given queries
    for (int i = 0; i < M; i++) {
 
        // Stores range L to R for
        // each query
        int L = Q[i][0], R = Q[i][1];
 
        // Size variable stores size of
        // [L, R] range
        int size = R - L + 1;
 
        // Stores total from 1 to size of
        // range [L, R]
        int total_From_1_To_Size
            = size * (size + 1) / 2;
 
        // Stores total sum from L to R
        // of Array
        int total_From_L_To_R
            = prefix[R] - prefix[L - 1];
 
        // If total from 1 to size is equal
        // to total from L to R then print
        // yes
        if (total_From_L_To_R == total_From_1_To_Size) {
            cout << "YES" << endl;
        }
        else {
            cout << "NO" << endl;
        }
    }
}
 
// Driver Code
int main()
{
    int arr[] = { 6, 4, 1, 2, 3, 5, 7 };
    int Q[][2] = { { 3, 5 }, { 1, 5 }, { 2, 6 } };
    int N = sizeof(arr) / sizeof(arr[0]);
    int M = sizeof(Q) / sizeof(Q[0]);
 
    // Function Call
    findPermutation(arr, N, Q, M);
 
    return 0;
}

Java



// Java code to implement the approach
import java.io.*;
 
class GFG {
    // Function to check if the given range
    // of queries form an Permutation or not
    // in the given array arr[]
    public static void findPermutation(int arr[], int N,
                                       int Q[][], int M)
    {
        // Precomputation array
        // stores the sum of all ranges
        // for any L to R
        int prefix[] = new int[N + 1];
 
        // Iterates over the range [1, N]
        for (int i = 1; i <= N; i++) {
 
            // Finding prefix sum of
            // given array
            prefix[i] = prefix[i - 1] + arr[i - 1];
        }
 
        // Traverse the given queries
        for (int i = 0; i < M; i++) {
 
            // Stores range L to R for
            // each query
            int L = Q[i][0], R = Q[i][1];
 
            // Size variable stores size of
            // [L, R] range
            int size = R - L + 1;
 
            // Stores total from 1 to size of
            // range [L, R]
            int total_From_1_To_Size
                = size * (size + 1) / 2;
 
            // Stores total sum from L to R
            // of Array
            int total_From_L_To_R
                = prefix[R] - prefix[L - 1];
 
            // If total from 1 to size is equal
            // to total from L to R then print
            // yes
            if (total_From_L_To_R == total_From_1_To_Size) {
                System.out.println("YES");
            }
            else {
                System.out.println("NO");
            }
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int arr[] = { 6, 4, 1, 2, 3, 5, 7 };
        int Q[][] = { { 3, 5 }, { 1, 5 }, { 2, 6 } };
        int N = arr.length;
        int M = Q.length;
 
        // Function Call
        findPermutation(arr, N, Q, M);
    }
}
 
// This code is contributed by Rohit Pradhan
Python3



# Python code to implement the approach
 
# Function to check if the given range
# of queries form an Permutation or not
# in the given array arr[]
def findPermutation(arr, N, Q, M) :
 
    # Precomputation array
    # stores the sum of all ranges
    # for any L to R
    prefix = [0] * (N + 1)
 
    # Iterates over the range [1, N]
    for i in range(1, N+1):
 
        # Finding prefix sum of
        # given array
        prefix[i] = prefix[i - 1] + arr[i - 1]
     
 
    # Traverse the given queries
    for i in range(0, M):
 
        # Stores range L to R for
        # each query
        L = Q[i][0]
        R = Q[i][1]
 
        # Size variable stores size of
        # [L, R] range
        size = R - L + 1
 
        # Stores total from 1 to size of
        # range [L, R]
        total_From_1_To_Size = size * (size + 1) // 2
 
        # Stores total sum from L to R
        # of Array
        total_From_L_To_R = prefix[R] - prefix[L - 1]
 
        # If total from 1 to size is equal
        # to total from L to R then print
        # yes
        if (total_From_L_To_R == total_From_1_To_Size) :
            print("YES")
         
        else :
            print("NO")
         
# Driver Code
if __name__ == "__main__":
 
    arr = [ 6, 4, 1, 2, 3, 5, 7 ]
    Q = [[ 3, 5 ], [ 1, 5 ], [ 2, 6]] 
    N = len(arr)
    M = len(Q)
 
    # Function Call
    findPermutation(arr, N, Q, M)
     
    # This code is contributed by sanjoy_62.
C#



// C# code to implement the approach
 
using System;
 
public class GFG {
 
    // Function to check if the given range
    // of queries form an Permutation or not
    // in the given array arr[]
    public static void findPermutation(int[] arr, int N,
                                       int[, ] Q, int M)
    {
        // Precomputation array
        // stores the sum of all ranges
        // for any L to R
        int[] prefix = new int[N + 1];
 
        // Iterates over the range [1, N]
        for (int i = 1; i <= N; i++) {
 
            // Finding prefix sum of
            // given array
            prefix[i] = prefix[i - 1] + arr[i - 1];
        }
 
        // Traverse the given queries
        for (int i = 0; i < M; i++) {
 
            // Stores range L to R for
            // each query
            int L = Q[i, 0], R = Q[i, 1];
 
            // Size variable stores size of
            // [L, R] range
            int size = R - L + 1;
 
            // Stores total from 1 to size of
            // range [L, R]
            int total_From_1_To_Size
                = size * (size + 1) / 2;
 
            // Stores total sum from L to R
            // of Array
            int total_From_L_To_R
                = prefix[R] - prefix[L - 1];
 
            // If total from 1 to size is equal
            // to total from L to R then print
            // yes
            if (total_From_L_To_R == total_From_1_To_Size) {
                Console.WriteLine("YES");
            }
            else {
                Console.WriteLine("NO");
            }
        }
    }
 
    static public void Main()
    {
 
        // Code
        int[] arr = { 6, 4, 1, 2, 3, 5, 7 };
        int[, ] Q = { { 3, 5 }, { 1, 5 }, { 2, 6 } };
        int N = arr.Length;
        int M = Q.GetLength(0);
 
        // Function Call
        findPermutation(arr, N, Q, M);
    }
}
 
// This code is contributed by lokeshmvs21.
Javascript



// JavaScript code to implement the approach
 
// Function to check if the given range
// of queries form an Permutation or not
// in the given array arr[]
const findPermutation = (arr, N, Q, M) => {
    // Precomputation array
    // stores the sum of all ranges
    // for any L to R
    let prefix = new Array(N + 1).fill(0);
 
    // Iterates over the range [1, N]
    for (let i = 1; i <= N; i++) {
 
        // Finding prefix sum of

            

                            

                    
                                    

                        

                
РЕКОМЕНДУЕМЫЕ СТАТЬИ