Dada una array arr[] de tamaño n . La tarea es contar el número de posibles subarreglos de modo que sus elementos se puedan reorganizar para formar un palíndromo.
Ejemplos:
Entrada: arr[] = {1, 2, 1, 2}
Salida: 7
{1}, {2}, {1}, {2}, {1, 2, 1}, {2, 1, 2} y {1, 2, 1, 2} son los subconjuntos válidos.
Entrada: arr[] = {1, 2, 3, 1, 2, 3, 4}
Salida: 11
Enfoque: Hay algunas observaciones:
- Para crear un palíndromo de longitud uniforme, todos los números distintos deben tener ocurrencias pares.
- Para crear un palíndromo de longitud impar, solo tiene que haber un número de ocurrencias impares.
Ahora, la parte complicada es determinar si una sección particular de la array se puede convertir en un palíndromo en complejidad O(1). Podemos usar XOR para lograr esto:
- Para cada número m, podemos usarlo en el cálculo de xor como 2^n para que contenga un solo bit establecido.
- Si el xor de todos los elementos de una sección es 0 , significa que las ocurrencias de todos los números distintos de esta sección son pares.
- Si el xor de todos los elementos de una sección es mayor que 0 significa que:
- O hay más de un número distinto con ocurrencias impares, en cuyo caso la sección no se puede reorganizar para formar un palíndromo
- O exactamente un número con ocurrencia impar (la representación binaria del número tendrá solo 1 bit establecido).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;
// Function that returns true if n is a
// power of 2 i.e. n has only 1 set bit
bool is_power_of_two(ll n)
{
return !(n & (n - 1LL));
}
// Function to return the count
// of all valid sub-arrays
int countSubArrays(int arr[], int n)
{
// To store the count of valid sub-arrays
int cnt = 0;
for (int j = 0; j < n; j++) {
ll xorval = 0LL;
for (int k = j; k < n; k++) {
// num = 2 ^ arr[k]
ll num = 1LL << arr[k];
xorval ^= num;
// If frequency of all the elements of the
// sub-array is even or there is only a
// single element with odd frequency
if (xorval == 0LL || is_power_of_two(xorval))
cnt++;
}
}
// Return the required count
return cnt;
}
// Driver code
int main()
{
int arr[] = { 1, 2, 3, 1, 2, 3, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << countSubArrays(arr, n);
return 0;
}
Java
// Java implementation of the approach
class GfG
{
static long ll;
// Function that returns true if n is a
// power of 2 i.e. n has only 1 set bit
static boolean is_power_of_two(long n)
{
return n!=0 && (n & (n - 1))==0;
}
// Function to return the count
// of all valid sub-arrays
static int countSubArrays(int arr[], int n)
{
// To store the count of valid sub-arrays
int cnt = 0;
for (int j = 0; j < n; j++)
{
long xorval = 0;
for (int k = j; k < n; k++)
{
// num = 2 ^ arr[k]
long num = 1 << arr[k];
xorval ^= num;
// If frequency of all the elements of the
// sub-array is even or there is only a
// single element with odd frequency
if (xorval == 0 || is_power_of_two(xorval))
cnt++;
}
}
// Return the required count
return cnt;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 2, 3, 1, 2, 3, 4 };
int n = arr.length;
System.out.println(countSubArrays(arr, n));
}
}
// This code is contributed by Prerna Saini
Python3
# Python3 implementation of the approach # Function that returns true if n is a # power of 2 i.e. n has only 1 set bit def is_power_of_two(n): return 0 if(n & (n - 1)) else 1; # Function to return the count # of all valid sub-arrays def countSubArrays(arr, n): # To store the count of valid sub-arrays cnt = 0; for j in range(n): xorval = 0; for k in range(j, n): # num = 2 ^ arr[k] num = 1 << arr[k]; xorval ^= num; # If frequency of all the elements of the # sub-array is even or there is only a # single element with odd frequency if (xorval == 0 or is_power_of_two(xorval)): cnt += 1; # Return the required count return cnt; # Driver code arr = [ 1, 2, 3, 1, 2, 3, 4 ]; n = len(arr); print(countSubArrays(arr, n)); # This code is contributed by mits
C#
// C# implementation of the approach
using System;
class GfG
{
static long ll;
// Function that returns true if n is a
// power of 2 i.e. n has only 1 set bit
static bool is_power_of_two(long n)
{
//return !(n & (n - 1));
return false;
}
// Function to return the count
// of all valid sub-arrays
static int countSubArrays(int []arr, int n)
{
// To store the count of valid sub-arrays
int cnt = 0;
for (int j = 0; j < n; j++)
{
long xorval = 0;
for (int k = j; k < n; k++)
{
// num = 2 ^ arr[k]
long num = 1 << arr[k];
xorval ^= num;
// If frequency of all the elements of the
// sub-array is even or there is only a
// single element with odd frequency
if (xorval == 0 || is_power_of_two(xorval))
cnt++;
}
}
// Return the required count
return cnt;
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 1, 2, 3, 1, 2, 3, 4 };
int n = arr.Length;
Console.WriteLine(countSubArrays(arr, n) + "1");
}
}
// This code contributed by Rajput-Ji
PHP
<?php
// PHP implementation of the approach
// Function that returns true if n is a
// power of 2 i.e. n has only 1 set bit
function is_power_of_two($n)
{
return !($n & ($n - 1));
}
// Function to return the count
// of all valid sub-arrays
function countSubArrays($arr, $n)
{
// To store the count of valid sub-arrays
$cnt = 0;
for ($j = 0; $j < $n; $j++) {
$xorval = 0;
for ($k = $j; $k < $n; $k++) {
// num = 2 ^ arr[k]
$num = 1 << $arr[$k];
$xorval ^= $num;
// If frequency of all the elements of the
// sub-array is even or there is only a
// single element with odd frequency
if ($xorval == 0 || is_power_of_two($xorval))
$cnt++;
}
}
// Return the required count
return $cnt;
}
// Driver code
$arr = array( 1, 2, 3, 1, 2, 3, 4 );
$n = count($arr);
echo countSubArrays($arr, $n);
// This code is contributed by mits
?>
Javascript
<script>
// Javascript implementation of the approach
// Function that returns true if n is a
// power of 2 i.e. n has only 1 set bit
function is_power_of_two(n)
{
return !(n & (n - 1));
}
// Function to return the count
// of all valid sub-arrays
function countSubArrays(arr, n)
{
// To store the count of valid sub-arrays
let cnt = 0;
for (let j = 0; j < n; j++) {
let xorval = 0;
for (let k = j; k < n; k++) {
// num = 2 ^ arr[k]
let num = 1 << arr[k];
xorval ^= num;
// If frequency of all the elements of the
// sub-array is even or there is only a
// single element with odd frequency
if (xorval == 0 || is_power_of_two(xorval))
cnt++;
}
}
// Return the required count
return cnt;
}
// Driver code
let arr = [ 1, 2, 3, 1, 2, 3, 4 ];
let n = arr.length;
document.write(countSubArrays(arr, n));
</script>
Producción:
11
Publicación traducida automáticamente
Artículo escrito por quirky1234 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA