Comprobar si una Secuencia es una concatenación de dos permutaciones

Dada una array arr que contiene enteros positivos, la tarea es verificar si la array arr dada es una concatenación de dos permutaciones o no. Una secuencia de M enteros se llama permutación si contiene todos los enteros del 1 al M exactamente una vez. 
Ejemplos: 
 

Entrada: arr[] = {1, 2, 5, 3, 4, 1, 1} 
Salida: No 
Explicación: 
La array dada contiene 1 tres veces. Los primeros 5 elementos forman una permutación de longitud 5, pero los 2 elementos restantes no forman una permutación.
Entrada: arr[] = {1, 2, 5, 3, 4, 1, 2} 
Salida: Sí 
Explicación: 
array dada arr[] = {1, 2, 5, 3, 4} + {1, 2} 
El Los primeros 5 elementos forman una permutación de longitud 5 y los 2 elementos restantes forman una permutación de longitud 2. 
 

Acercarse: 
 

1. Recorra la array dada y calcule la suma de todos los elementos .
2. Forme una array de prefijos que contenga el prefijo sum .
3. Ahora, para cada índice en el rango [1, N) 
   • Verifique si los elementos, desde el inicio hasta el índice actual, forman una permutación, usando la siguiente condición:

Sum of K elements = Sum of K natural numbers

where K is the current index

• Luego verifique que los elementos restantes formen una permutación.
• En caso afirmativo, imprimimos/devolvemos Sí.

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ program to check if a given sequence
// is a concatenation of two permutations or not
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to Check if a given sequence
// is a concatenation of two permutations or not
bool checkPermutation(int arr[], int n)
{
    // Computing the sum of all the
    // elements in the array
    long long sum = 0;
    for (int i = 0; i < n; i++)
        sum += arr[i];
 
    // Computing the prefix sum
    // for all the elements in the array
    long long prefix[n + 1] = { 0 };
    prefix[0] = arr[0];
    for (int i = 1; i < n; i++)
        prefix[i] = prefix[i - 1] + arr[i];
 
    // Iterating through the i
    // from lengths 1 to n-1
    for (int i = 0; i < n - 1; i++) {
 
        // Sum of first i+1 elements
        long long lsum = prefix[i];
 
        // Sum of remaining n-i-1 elements
        long long rsum = sum - prefix[i];
 
        // Lengths of the 2 permutations
        long long l_len = i + 1,
                  r_len = n - i - 1;
 
        // Checking if the sums
        // satisfy the formula or not
        if (((2 * lsum)
             == (l_len * (l_len + 1)))
            && ((2 * rsum)
                == (r_len * (r_len + 1))))
            return true;
    }
 
    return false;
}
 
// Driver code
int main()
{
    int arr[] = { 1, 2, 5, 3, 4, 1, 2 };
    int n = sizeof(arr) / sizeof(int);
 
    if (checkPermutation(arr, n))
        cout << "Yes\n";
    else
        cout << "No\n";
 
    return 0;
}

// Java program to check if a given sequence
// is a concatenation of two permutations or not
import java.util.*;
 
class GFG{
 
// Function to Check if a given sequence
// is a concatenation of two permutations or not
static boolean checkPermutation(int []arr, int n)
{
    // Computing the sum of all the
    // elements in the array
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += arr[i];
 
    // Computing the prefix sum
    // for all the elements in the array
    int []prefix = new int[n + 1];
    Arrays.fill(prefix,0);
    prefix[0] = arr[0];
    for (int i = 1; i < n; i++)
        prefix[i] = prefix[i - 1] + arr[i];
 
    // Iterating through the i
    // from lengths 1 to n-1
    for (int i = 0; i < n - 1; i++) {
 
        // Sum of first i+1 elements
        int lsum = prefix[i];
 
        // Sum of remaining n-i-1 elements
        int rsum = sum - prefix[i];
 
        // Lengths of the 2 permutations
        int l_len = i + 1,
                r_len = n - i - 1;
 
        // Checking if the sums
        // satisfy the formula or not
        if (((2 * lsum)
            == (l_len * (l_len + 1)))
            && ((2 * rsum)
                == (r_len * (r_len + 1))))
            return true;
    }
 
    return false;
}
 
// Driver code
public static void main(String args[])
{
    int []arr = { 1, 2, 5, 3, 4, 1, 2 };
    int n = arr.length;
 
    if (checkPermutation(arr, n))
        System.out.println("Yes");
    else
        System.out.println("No");
 
}
}
 
// This code is contributed by Surendra_Gangwar

# Python program to check if a given sequence
# is a concatenation of two permutations or not
 
# Function to Check if a given sequence
# is a concatenation of two permutations or not
def checkPermutation(arr, n):
     
    # Computing the sum of all the
    # elements in the array
    sum = 0;
    for i in range(n):
        sum += arr[i];
 
    # Computing the prefix sum
    # for all the elements in the array
    prefix = [0]*(n + 1);
    prefix[0] = arr[0];
    for i in range(n):
        prefix[i] = prefix[i - 1] + arr[i];
 
    # Iterating through the i
    # from lengths 1 to n-1
    for i in range(n - 1):
 
        # Sum of first i+1 elements
        lsum = prefix[i];
 
        # Sum of remaining n-i-1 elements
        rsum = sum - prefix[i];
 
        # Lengths of the 2 permutations
        l_len = i + 1
        r_len = n - i - 1;
 
        # Checking if the sums
        # satisfy the formula or not
        if (((2 * lsum)== (l_len * (l_len + 1))) and
            ((2 * rsum)== (r_len * (r_len + 1)))):
            return True;
     
    return False;
 
# Driver code
if __name__=='__main__':
 
    arr = [ 1, 2, 5, 3, 4, 1, 2 ]
    n = len(arr)
 
    if (checkPermutation(arr, n)):
        print("Yes");
    else:
        print("No");
 
# This code is contributed by Princi Singh

// C# program to check if a given sequence
// is a concatenation of two permutations or not
using System;
 
class GFG{
  
// Function to Check if a given sequence
// is a concatenation of two permutations or not
static bool checkPermutation(int []arr, int n)
{
    // Computing the sum of all the
    // elements in the array
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum += arr[i];
  
    // Computing the prefix sum
    // for all the elements in the array
    int []prefix = new int[n + 1];
    prefix[0] = arr[0];
    for (int i = 1; i < n; i++)
        prefix[i] = prefix[i - 1] + arr[i];
  
    // Iterating through the i
    // from lengths 1 to n-1
    for (int i = 0; i < n - 1; i++) {
  
        // Sum of first i+1 elements
        int lsum = prefix[i];
  
        // Sum of remaining n-i-1 elements
        int rsum = sum - prefix[i];
  
        // Lengths of the 2 permutations
        int l_len = i + 1,
                r_len = n - i - 1;
  
        // Checking if the sums
        // satisfy the formula or not
        if (((2 * lsum)
            == (l_len * (l_len + 1)))
            && ((2 * rsum)
                == (r_len * (r_len + 1))))
            return true;
    }
  
    return false;
}
  
// Driver code
public static void Main(String []args)
{
    int []arr = { 1, 2, 5, 3, 4, 1, 2 };
    int n = arr.Length;
  
    if (checkPermutation(arr, n))
        Console.WriteLine("Yes");
    else
        Console.WriteLine("No");
  
}
}
 
// This code is contributed by Rajput-Ji

<script>
 
// JavaScript program to check if a given sequence
// is a concatenation of two permutations or not
 
// Function to Check if a given sequence
// is a concatenation of two permutations or not
function checkPermutation(arr, n)
{
    // Computing the sum of all the
    // elements in the array
    let sum = 0;
    for (let i = 0; i < n; i++)
        sum += arr[i];
   
    // Computing the prefix sum
    // for all the elements in the array
    let prefix = Array.from({length: n+1}, (_, i) => 0);
    prefix[0] = arr[0];
    for (let i = 1; i < n; i++)
        prefix[i] = prefix[i - 1] + arr[i];
   
    // Iterating through the i
    // from lengths 1 to n-1
    for (let i = 0; i < n - 1; i++) {
   
        // Sum of first i+1 elements
        let lsum = prefix[i];
   
        // Sum of remaining n-i-1 elements
        let rsum = sum - prefix[i];
   
        // Lengths of the 2 permutations
        let l_len = i + 1,
                r_len = n - i - 1;
   
        // Checking if the sums
        // satisfy the formula or not
        if (((2 * lsum)
            == (l_len * (l_len + 1)))
            && ((2 * rsum)
                == (r_len * (r_len + 1))))
            return true;
    }
   
    return false;
}
  
 
// Driver Code
     
        let arr = [ 1, 2, 5, 3, 4, 1, 2 ];
    let n = arr.length;
   
    if (checkPermutation(arr, n))
        document.write("Yes");
    else
        document.write("No");
                   
</script>

Yes

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(n)