Проверьте, образуют ли элементы массива заданного диапазона перестановку
Для заданного массива 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 РЕКОМЕНДУЕМЫЕ СТАТЬИ |