Dada una array A[] de N enteros. Compruebe si existen 2 subsecuencias distintas X e Y de la array dada, de modo que la suma de los elementos de X sea mayor que la suma de los elementos de Y , pero el número de elementos en X sea menor que el número de elementos en Y .
Ejemplos:
Entrada: N = 5, A[] = {2, 3, 8, 1, 6}
Salida: SI
Explicación: Considere las secuencias: X = {6}, Y = {2, 3}.
Se puede ver fácilmente que el tamaño de X (es decir, 1) < tamaño de Y (es decir, 2), mientras que la suma de los elementos de X (es decir, 6) > la suma de los elementos de Y (es decir, 5).Entrada: N = 6, A[] = {1, 1, 1, 1, 1, 1}
Salida: NO
Enfoque: el problema se puede resolver utilizando un enfoque de dos punteros basado en la siguiente idea:
En una array ordenada, si la suma de los primeros K (donde K > N/2) elementos más pequeños es menor que la suma de los elementos restantes, entonces puede haber tales subsecuencias; de lo contrario, no.
Siga los pasos que se mencionan a continuación para resolver el problema:
- Ordenar la array dada.
- Declare dos variables beg y end para almacenar la suma de elementos desde el principio y el final de la array ordenada.
- Inicialice beg con arr[0] y termine con 0 porque debe haber al menos 1 elemento más en la subsecuencia con menos suma.
- Use dos punteros de i = 1 y j = N-1:
- Agrega arr[i] con beg y arr[j] con end.
- Si mendigar es menor que finalizar, entonces rompa la iteración. Porque es posible encontrar subsecuencias como que todos los demás elementos en el lado superior son más grandes que la primera mitad y los lados inferiores ya tienen un elemento más.
- Si después de la iteración total no se encuentra tal secuencia, no es posible devolverla.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Code for above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if the given
// array have 2 distinct subsequences
// such that number of elements in one
// having greater sum is less
bool haveSubsequences(int N, int A[])
{
// Sorting the given sequence Array
sort(A, A + N);
// Variable "beg" stores the sum of
// elements from beginning variable
// "end" stores the sum of elements
// from end
int beg = A[0], end = 0;
// Flag variable to check for wrong
// answer
int flag = 0;
// Initializing 2 pointers
int i = 1, j = N - 1;
// Iterating array from both sides
// via 2 pointers and checking if
// sum of starting say k+1 elements is
// less than sum of k elements from the
// end
while (i < j) {
beg += A[i];
end += A[j];
// If sum of starting i elements is
// less than the sum of j elements,
// we make flag 1 and break the loop
if (beg < end) {
flag = 1;
break;
}
// Else we simply increment i and
// decrement j
i++;
j--;
}
// Returning true or false in accordance
// with the flag
if (flag == 1) {
return true;
}
else {
return false;
}
}
// Driver Code
int main()
{
int N = 5;
int A[] = { 2, 3, 8, 1, 6 };
bool answer = haveSubsequences(N, A);
if (answer == true) {
cout << "YES";
}
else {
cout << "NO";
}
}
Java
/*package whatever //do not write package name here */
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG
{
// Function to check if the given
// array have 2 distinct subsequences
// such that number of elements in one
// having greater sum is less
public static boolean haveSubsequences(int N, int A[])
{
// Sorting the given sequence Array
Arrays.sort(A);
// Variable "beg" stores the sum of
// elements from beginning variable
// "end" stores the sum of elements
// from end
int beg = A[0], end = 0;
// Flag variable to check for wrong
// answer
int flag = 0;
// Initializing 2 pointers
int i = 1, j = N - 1;
// Iterating array from both sides
// via 2 pointers and checking if
// sum of starting say k+1 elements is
// less than sum of k elements from the
// end
while (i < j) {
beg += A[i];
end += A[j];
// If sum of starting i elements is
// less than the sum of j elements,
// we make flag 1 and break the loop
if (beg < end) {
flag = 1;
break;
}
// Else we simply increment i and
// decrement j
i++;
j--;
}
// Returning true or false in accordance
// with the flag
if (flag == 1) {
return true;
}
else {
return false;
}
}
// Driver Code
public static void main(String[] args)
{
int N = 5;
int A[] = { 2, 3, 8, 1, 6 };
boolean answer = haveSubsequences(N, A);
if (answer == true) {
System.out.println("YES");
}
else {
System.out.println("NO");
}
}
}
// This code is contributed by amnindersingh1414.
Python3
# Python Code for above approach
# Function to check if the given
# array have 2 distinct subsequences
# such that number of elements in one
# having greater sum is less
def haveSubsequences(N, A):
# Sorting the given sequence Array
A.sort()
# Variable "beg" stores the sum of
# elements from beginning variable
# "end" stores the sum of elements
# from end
beg = A[0]
end = 0
# Flag variable to check for wrong
# answer
flag = 0
# Initializing 2 pointers
i = 1
j = N - 1
# Iterating array from both sides
# via 2 pointers and checking if
# sum of starting say k+1 elements is
# less than sum of k elements from the
# end
while i < j:
beg += A[i]
end += A[j]
# If sum of starting i elements is
# less than the sum of j elements,
# we make flag 1 and break the loop
if (beg < end):
flag = 1
break
# Else we simply increment i and
# decrement j
i += 1
j -= 1
# Returning true or false in accordance
# with the flag
if (flag == 1):
return True
else:
return False
# Driver Code
if __name__ == '__main__':
N = 5
A = [2, 3, 8, 1, 6]
answer = haveSubsequences(N, A)
if (answer == True):
print("YES")
else:
print("NO")
# This code is contributed by amnindersingh1414.
C#
// C# program for the above approach
using System;
class GFG
{
// Function to check if the given
// array have 2 distinct subsequences
// such that number of elements in one
// having greater sum is less
static bool haveSubsequences(int N, int []A)
{
// Sorting the given sequence Array
Array.Sort(A);
// Variable "beg" stores the sum of
// elements from beginning variable
// "end" stores the sum of elements
// from end
int beg = A[0], end = 0;
// Flag variable to check for wrong
// answer
int flag = 0;
// Initializing 2 pointers
int i = 1, j = N - 1;
// Iterating array from both sides
// via 2 pointers and checking if
// sum of starting say k+1 elements is
// less than sum of k elements from the
// end
while (i < j) {
beg += A[i];
end += A[j];
// If sum of starting i elements is
// less than the sum of j elements,
// we make flag 1 and break the loop
if (beg < end) {
flag = 1;
break;
}
// Else we simply increment i and
// decrement j
i++;
j--;
}
// Returning true or false in accordance
// with the flag
if (flag == 1) {
return true;
}
else {
return false;
}
}
// Driver Code
public static void Main()
{
int N = 5;
int []A = { 2, 3, 8, 1, 6 };
bool answer = haveSubsequences(N, A);
if (answer == true) {
Console.WriteLine("YES");
}
else {
Console.WriteLine("NO");
}
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// JavaScript Code for above approach
// Function to check if the given
// array have 2 distinct subsequences
// such that number of elements in one
// having greater sum is less
const haveSubsequences = (N, A) => {
// Sorting the given sequence Array
A.sort();
// Variable "beg" stores the sum of
// elements from beginning variable
// "end" stores the sum of elements
// from end
let beg = A[0], end = 0;
// Flag variable to check for wrong
// answer
let flag = 0;
// Initializing 2 pointers
let i = 1, j = N - 1;
// Iterating array from both sides
// via 2 pointers and checking if
// sum of starting say k+1 elements is
// less than sum of k elements from the
// end
while (i < j) {
beg += A[i];
end += A[j];
// If sum of starting i elements is
// less than the sum of j elements,
// we make flag 1 and break the loop
if (beg < end) {
flag = 1;
break;
}
// Else we simply increment i and
// decrement j
i++;
j--;
}
// Returning true or false in accordance
// with the flag
if (flag == 1) {
return true;
}
else {
return false;
}
}
// Driver Code
let N = 5;
let A = [2, 3, 8, 1, 6];
let answer = haveSubsequences(N, A);
if (answer == true) {
document.write("YES");
}
else {
document.write("NO");
}
// This code is contributed by rakeshsahni
</script>
Producción
YES
Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kamabokogonpachiro y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA