Dada una array de N enteros, usando ‘+’ y ‘-‘ entre los elementos, verifique si hay una forma de formar una secuencia de números que evalúe a un número divisible por M
Ejemplos:
Entrada: arr = {1, 2, 3, 4, 6}
M = 4
Salida: Verdadero
Explicación:
Hay una secuencia válida, es decir, (1 – 2
+ 3 + 4 + 6), que da como resultado 12 que
es divisible por 4Entrada: arr = {1, 3, 9}
M = 2
Salida: Falso
Explicación:
No hay secuencia que se evalúe como
un número divisible por M.
Una solución simple es considerar recursivamente todos los escenarios posibles, es decir, usar un operador ;+’ o ‘-‘ entre los elementos y mantener una suma variable que almacene el resultado. Si este resultado es divisible por M, devuelva verdadero; de lo contrario, devuelva falso.
La implementación recursiva es la siguiente:
C++
bool isPossible(int index, int sum)
{
// Base case
if (index == n) {
// check if sum is divisible by M
if ((sum % M) == 0)
return true;
return false;
}
// recursively call by considering '+'
// or '-' between index and index+1
// 1.Try placing '+'
bool placeAdd = isPossible(index + 1,
sum + arr[index]);
// 2. Try placing '-'
bool placeMinus = isPossible(index + 1,
sum - arr[index]);
if (placeAdd || placeMinus)
return true;
return false;
}
Java
static boolean isPossible(int index, int sum)
{
// Base case
if (index == n)
{
// Check if sum is divisible by M
if ((sum % M) == 0)
return true;
return false;
}
// Recursively call by considering '+'
// or '-' between index and index+1
// 1.Try placing '+'
boolean placeAdd = isPossible(index + 1,
sum + arr[index]);
// 2. Try placing '-'
boolean placeMinus = isPossible(index + 1,
sum - arr[index]);
if (placeAdd || placeMinus)
return true;
return false;
}
// This code is contributed by rutvik_56.
Python3
def isPossible(index, sum): # Base case if (index == n): # check if sum is divisible by M if ((sum % M) == 0): return True; return False; # recursively call by considering '+' # or '-' between index and index+1 # 1.Try placing '+' placeAdd = isPossible(index + 1, sum + arr[index]); # 2. Try placing '-' placeMinus = isPossible(index + 1, sum - arr[index]); if (placeAdd or placeMinus): return True; return False; # This code is contributed by pratham76.
C#
static bool isPossible(int index, int sum)
{
// Base case
if (index == n)
{
// Check if sum is divisible by M
if ((sum % M) == 0)
return true;
return false;
}
// Recursively call by considering '+'
// or '-' between index and index+1
// 1.Try placing '+'
bool placeAdd = isPossible(index + 1,
sum + arr[index]);
// 2. Try placing '-'
bool placeMinus = isPossible(index + 1,
sum - arr[index]);
if (placeAdd || placeMinus)
return true;
return false;
}
// This code is contributed by divyesh072019
Javascript
<script>
function isPossible(index , sum)
{
// Base case
if (index == n)
{
// Check if sum is divisible by M
if ((sum % M) == 0)
return true;
return false;
}
// Recursively call by considering '+'
// or '-' between index and index+1
// 1.Try placing '+'
let placeAdd = isPossible(index + 1,
sum + arr[index]);
// 2. Try placing '-'
let placeMinus = isPossible(index + 1,
sum - arr[index]);
if (placeAdd || placeMinus)
return true;
return false;
}
// This code is contributed by Amit Katiyar
</script>
Hay subproblemas superpuestos como se muestra en la imagen a continuación (Nota: la imagen representa el árbol de recursión hasta el índice = 3)
Mejor enfoque: para optimizar el enfoque anterior, utilice la programación dinámica.
Método 1: Aplicamos programación dinámica con dos estados: –
(i) índice,
(ii) suma
Entonces DP [índice] [suma] almacena el índice actual en el que estamos y la suma almacena el resultado de la evaluación de la secuencia formada hasta ese índice .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to check if any
// valid sequence is divisible by M
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000;
bool isPossible(int n, int index, int sum,
int M, int arr[], int dp[][MAX])
{
// Base case
if (index == n) {
// check if sum is divisible by M
if ((sum % M) == 0)
return true;
return false;
}
// check if the current state
// is already computed
if (dp[index][sum] != -1)
return dp[index][sum];
// 1.Try placing '+'
bool placeAdd = isPossible(n, index + 1,
sum + arr[index], M, arr, dp);
// 2. Try placing '-'
bool placeMinus = isPossible(n, index + 1,
sum - arr[index], M, arr, dp);
// calculate value of res for recursive case
bool res = (placeAdd || placeMinus);
// store the value for res for current
// states and return for parent call
dp[index][sum] = res;
return res;
}
int main()
{
int arr[] = { 1, 2, 3, 4, 6 };
int n = sizeof(arr)/sizeof(arr[0]);
int M = 4;
int dp[n + 1][MAX];
memset(dp, -1, sizeof(dp));
bool res;
res = isPossible(n, 0, 0, M, arr, dp);
cout << (res ? "True" : "False") << endl;
return 0;
}
Java
// Java program to check if any
// valid sequence is divisible by M
import java.util.*;
class GFG
{
static final int MAX = 1000;
static boolean isPossible(int n, int index, int sum,
int M, int arr[], int dp[][])
{
// Base case
if (index == n)
{
// check if sum is divisible by M
if ((sum % M) == 0)
return true;
return false;
}
else if(sum < 0 || sum >= MAX)
return false;
// check if the current state
// is already computed
if (dp[index][sum] != -1)
{
if(dp[index][sum] == 0)
return false;
return true;
}
// 1.Try placing '+'
boolean placeAdd = isPossible(n, index + 1,
sum + arr[index], M, arr, dp);
// 2. Try placing '-'
boolean placeMinus = isPossible(n, index + 1,
sum - arr[index], M, arr, dp);
// calculate value of res for recursive case
boolean res = (placeAdd || placeMinus);
// store the value for res for current
// states and return for parent call
dp[index][sum] = (res) ? 1 : 0;
return res;
}
// Driver code
public static void main(String args[])
{
int arr[] = { 1, 2, 3, 4, 6 };
int n = arr.length;
int M = 4;
int dp[][] = new int[n + 1][MAX];
for(int i = 0; i < n + 1; i++)
Arrays.fill(dp[i], -1);
boolean res;
res = isPossible(n, 0, 0, M, arr, dp);
System.out.println((res ? "True" : "False"));
}
}
// This code is contributed by ghanshyampandey
Python3
# Python3 program to check if any # valid sequence is divisible by M def isPossible(n, index, Sum, M, arr, dp): global MAX # Base case if index == n: # check if sum is divisible by M if (Sum % M) == 0: return True return False # check if the current state # is already computed if dp[index][Sum] != -1: return dp[index][Sum] # 1.Try placing '+' placeAdd = isPossible(n, index + 1, Sum + arr[index], M, arr, dp) # 2. Try placing '-' placeMinus = isPossible(n, index + 1, Sum - arr[index], M, arr, dp) # calculate value of res for recursive case res = placeAdd or placeMinus # store the value for res for current # states and return for parent call dp[index][Sum] = res return res MAX = 1000 arr = [1, 2, 3, 4, 6] n = len(arr) M = 4 dp = [[-1]*MAX for i in range(n+1)] res = isPossible(n, 0, 0, M, arr, dp) if res: print(True) else: print(False) # this code is contributed by PranchalK
C#
// C# program to check if any
// valid sequence is divisible by M
using System;
class GFG
{
static int MAX = 1000;
static Boolean isPossible(int n, int index, int sum,
int M, int []arr, int [,]dp)
{
// Base case
if (index == n)
{
// check if sum is divisible by M
if ((sum % M) == 0)
return true;
return false;
}
else if(sum < 0 || sum >= MAX)
return false;
// check if the current state
// is already computed
if (dp[index,sum] != -1)
{
if(dp[index,sum] == 0)
return false;
return true;
}
// 1.Try placing '+'
Boolean placeAdd = isPossible(n, index + 1,
sum + arr[index],
M, arr, dp);
// 2. Try placing '-'
Boolean placeMinus = isPossible(n, index + 1,
sum - arr[index],
M, arr, dp);
// calculate value of res for recursive case
Boolean res = (placeAdd || placeMinus);
// store the value for res for current
// states and return for parent call
dp[index,sum] = (res) ? 1 : 0;
return res;
}
// Driver code
public static void Main(String []args)
{
int []arr = { 1, 2, 3, 4, 6 };
int n = arr.Length;
int M = 4;
int [,]dp = new int[n + 1, MAX];
for(int i = 0; i < n + 1; i++)
for(int j = 0; j < MAX; j++)
dp[i, j] = -1;
Boolean res;
res = isPossible(n, 0, 0, M, arr, dp);
Console.WriteLine((res ? "True" : "False"));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// javascript program to check if any
// valid sequence is divisible by M
var MAX = 1000;
function isPossible(n , index , sum,M , arr , dp)
{
// Base case
if (index == n)
{
// check if sum is divisible by M
if ((sum % M) == 0)
return true;
return false;
}
else if(sum < 0 || sum >= MAX)
return false;
// check if the current state
// is already computed
if (dp[index][sum] != -1)
{
if(dp[index][sum] == 0)
return false;
return true;
}
// 1.Try placing '+'
var placeAdd = isPossible(n, index + 1,
sum + arr[index], M, arr, dp);
// 2. Try placing '-'
var placeMinus = isPossible(n, index + 1,
sum - arr[index], M, arr, dp);
// calculate value of res for recursive case
var res = (placeAdd || placeMinus);
// store the value for res for current
// states and return for parent call
dp[index][sum] = (res) ? 1 : 0;
return res;
}
// Driver code
var arr = [ 1, 2, 3, 4, 6 ];
var n = arr.length;
var M = 4;
var dp = Array(n+1).fill(-1).map(x => Array(MAX).fill(-1));
res = isPossible(n, 0, 0, M, arr, dp);
document.write((res ? "True" : "False"));
// This code contributed by shikhasingrajput
</script>
Producción:
True
Complejidad de tiempo: O(N*suma) donde la suma es la suma máxima posible para la secuencia de enteros y N es el número de elementos en la array.
Método 2 (eficiente): Esto es más eficiente que el Método 1. Aquí también, aplicamos Programación Dinámica pero con dos estados diferentes:
(i) índice,
(ii) módulo
Entonces DP[índice][módulo] almacena el módulo del resultado de la evaluación de la secuencia formada hasta ese índice, con M.
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100;
int isPossible(int n, int index, int modulo,
int M, int arr[], int dp[][MAX])
{
// Calculate modulo for this call
modulo = ((modulo % M) + M) % M;
// Base case
if (index == n) {
// check if sum is divisible by M
if (modulo == 0)
return 1;
return 0;
}
// check if the current state is
// already computed
if (dp[index][modulo] != -1)
return dp[index][modulo];
// 1.Try placing '+'
int placeAdd = isPossible(n, index + 1,
modulo + arr[index], M, arr, dp);
// 2. Try placing '-'
int placeMinus = isPossible(n, index + 1,
modulo - arr[index], M, arr, dp);
// calculate value of res for recursive
// case
bool res = (placeAdd || placeMinus);
// store the value for res for current
// states and return for parent call
dp[index][modulo] = res;
return res;
}
int main()
{
int arr[] = { 1, 2, 3, 4, 6 };
int n = sizeof(arr)/sizeof(arr[0]);
int M = 4;
// MAX is the Maximum value M can take
int dp[n + 1][MAX];
memset(dp, -1, sizeof(dp));
bool res;
res = isPossible(n, 1, arr[0], M, arr, dp);
cout << (res ? "True" : "False") << endl;
return 0;
}
Java
// Java implementation of above approach
class GFG
{
static int MAX = 100;
static int isPossible(int n, int index, int modulo,
int M, int arr[], int dp[][])
{
// Calculate modulo for this call
modulo = ((modulo % M) + M) % M;
// Base case
if (index == n)
{
// check if sum is divisible by M
if (modulo == 0)
{
return 1;
}
return 0;
}
// check if the current state is
// already computed
if (dp[index][modulo] != -1)
{
return dp[index][modulo];
}
// 1.Try placing '+'
int placeAdd = isPossible(n, index + 1,
modulo + arr[index], M, arr, dp);
// 2. Try placing '-'
int placeMinus = isPossible(n, index + 1,
modulo - arr[index], M, arr, dp);
// calculate value of res for
// recursive case
int res = placeAdd;
// store the value for res for current
// states and return for parent call
dp[index][modulo] = res;
return res;
}
// Driver code
public static void main(String[] args)
{
int arr[] = {1, 2, 3, 4, 6};
int n = arr.length;
int M = 4;
// MAX is the Maximum value M can take
int dp[][] = new int[n + 1][MAX];
for (int i = 0; i < n + 1; i++)
{
for (int j = 0; j < MAX; j++)
{
dp[i][j] = -1;
}
}
boolean res;
if (isPossible(n, 1, arr[0], M, arr, dp) == 1)
{
res = true;
}
else
{
res = false;
}
System.out.println(res ? "True" : "False");
}
}
// This code is contributed by
// PrinciRaj1992
Python3
# Python3 Program to Check if any
# valid sequence is divisible by M
MAX = 100
def isPossible(n, index, modulo,
M, arr, dp):
# Calculate modulo for this call
modulo = ((modulo % M) + M) % M
# Base case
if (index == n):
# check if sum is divisible by M
if (modulo == 0):
return 1
return 0
# check if the current state is
# already computed
if (dp[index][modulo] != -1):
return dp[index][modulo]
# 1.Try placing '+'
placeAdd = isPossible(n, index + 1, modulo +
arr[index], M, arr, dp)
# 2. Try placing '-'
placeMinus = isPossible(n, index + 1, modulo -
arr[index], M, arr, dp)
# calculate value of res
# for recursive case
res = bool(placeAdd or placeMinus)
# store the value for res for current
# states and return for parent call
dp[index][modulo] = res
return res
# Driver code
arr = [ 1, 2, 3, 4, 6 ]
n = len(arr)
M = 4
# MAX is the Maximum value
# M can take
dp = [[-1] * (n + 1)] * MAX
res = isPossible(n, 1, arr[0],
M, arr, dp)
if(res == True):
print("True")
else:
print("False")
# This code is contributed by ash264
C#
// C# implementation of above approach
using System;
class GFG
{
static int MAX = 100;
static int isPossible(int n, int index, int modulo,
int M, int []arr, int [,]dp)
{
// Calculate modulo for this call
modulo = ((modulo % M) + M) % M;
// Base case
if (index == n)
{
// check if sum is divisible by M
if (modulo == 0)
{
return 1;
}
return 0;
}
// check if the current state is
// already computed
if (dp[index, modulo] != -1)
{
return dp[index, modulo];
}
// 1.Try placing '+'
int placeAdd = isPossible(n, index + 1,
modulo + arr[index], M, arr, dp);
// 2. Try placing '-'
int placeMinus = isPossible(n, index + 1,
modulo - arr[index], M, arr, dp);
// calculate value of res for
// recursive case
int res = placeAdd;
// store the value for res for current
// states and return for parent call
dp[index, modulo] = res;
return res;
}
// Driver code
public static void Main()
{
int []arr = {1, 2, 3, 4, 6};
int n = arr.Length;
int M = 4;
// MAX is the Maximum value M can take
int [,]dp = new int[n + 1,MAX];
for (int i = 0; i < n + 1; i++)
{
for (int j = 0; j < MAX; j++)
{
dp[i, j] = -1;
}
}
bool res;
if (isPossible(n, 1, arr[0], M, arr, dp) == 1)
{
res = true;
}
else
{
res = false;
}
Console.WriteLine(res ? "True" : "False");
}
}
//This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of above approach
const MAX = 100;
function isPossible(n, index, modulo, M, arr, dp)
{
// Calculate modulo for this call
modulo = ((modulo % M) + M) % M;
// Base case
if (index == n)
{
// Check if sum is divisible by M
if (modulo == 0)
{
return 1;
}
return 0;
}
// check if the current state is
// already computed
if (dp[index][modulo] != -1)
{
return dp[index][modulo];
}
// 1.Try placing '+'
var placeAdd = isPossible(n, index + 1,
modulo + arr[index],
M, arr, dp);
// 2. Try placing '-'
var placeMinus = isPossible(n, index + 1,
modulo - arr[index],
M, arr, dp);
// Calculate value of res for
// recursive case
var res = placeAdd;
// Store the value for res for current
// states and return for parent call
dp[index][modulo] = res;
return res;
}
// Driver code
var arr = [ 1, 2, 3, 4, 6 ];
var n = arr.length;
var M = 4;
// MAX is the Maximum value M can take
var dp = Array(n + 1);
for(i = 0; i < n + 1; i++)
{
dp[i] = Array(MAX).fill(-1);
}
var res;
if (isPossible(n, 1, arr[0], M, arr, dp) == 1)
{
res = true;
}
else
{
res = false;
}
document.write(res ? "True" : "False");
// This code is contributed by gauravrajput1
</script>
Producción
True
Complejidad temporal: O(N*M).
Enfoque eficiente: siga los pasos a continuación para resolver el problema:
- Evalúe Modulo de todos los elementos de la array con respecto al número dado y guárdelo en la nueva array, digamos ModArray[].
- Evalúe la suma de ModArray y guárdela en la suma y verifique si la suma% M == 0, entonces la salida es «verdadera» y regrese.
- Si la suma es impar, no habrá ningún caso en el que el siguiente pueda evaluarse como el número que es divisible por M. Imprime «Falso» y regresa.
- Verifique si la suma es par y luego divídala por 2, esto se debe a que los hemos sumado previamente y ahora la tarea es eliminarlo, por lo que es necesario eliminarlo dos veces, por lo tanto, el número debe ser par.
- Elimine el primer elemento del ModArray ya que no es posible colocar menos en el primer elemento.
- Ahora la solución se convierte en el problema donde queremos evaluar si existe una solución para que la suma de los elementos de un ModArray sea igual a la suma o no.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if any valid
// sequence is divisible by M
void func(int n, int m, int A[])
{
// DEclare mod array
vector<int> ModArray(n);
int sum = 0;
// Calculate the mod array
for (int i = 0; i < n; i++) {
ModArray[i] = A[i] % m;
sum += ModArray[i];
}
sum = sum % m;
// Check if sum is divisible by M
if (sum % m == 0) {
cout << "True";
return;
}
// Check if sum is not divisible by 2
if (sum % 2 != 0) {
cout << "False";
}
else {
// Remove the first element from
// the ModArray since it is not
// possible to place minus
// on the first element
ModArray.erase(ModArray.begin());
int i = 0;
// Decrease the size of array
int j = ModArray.size() - 1;
// Sort the array
sort(ModArray.begin(), ModArray.end());
sum = sum / 2;
int i1, i2;
// Loop until the pointer
// cross each other
while (i <= j) {
int s = ModArray[i] + ModArray[j];
// Check if sum becomes equal
if (s == sum) {
i1 = i;
i2 = j;
cout << "True";
break;
}
// Increase and decrease
// the pointer accordingly
else if (s > sum)
j--;
else
i++;
}
}
}
// Driver code
int main()
{
int m = 2;
int a[] = { 1, 3, 9 };
int n = sizeof a / sizeof a[0];
// Function call
func(n, m, a);
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to check if any valid
// sequence is divisible by M
static void func(int n, int m, int []A)
{
// Declare mod array
Vector<Integer> ModArray = new Vector<>();
for(int i = 0; i < n; i++)
ModArray.add(0);
int sum = 0;
// Calculate the mod array
for(int i = 0; i < n; i++)
{
ModArray.set(i, A[i] % m);
sum += ((int)ModArray.get(i));
}
sum = sum % m;
// Check if sum is divisible by M
if (sum % m == 0)
{
System.out.println("True");
return;
}
// Check if sum is not divisible by 2
if (sum % 2 != 0)
{
System.out.println("False");
}
else
{
// Remove the first element from
// the ModArray since it is not
// possible to place minus
// on the first element
ModArray.remove(0);
int i = 0;
// Decrease the size of array
int j = ModArray.size() - 1;
// Sort the array
Collections.sort(ModArray);
sum = sum / 2;
int i1, i2;
// Loop until the pointer
// cross each other
while (i <= j)
{
int s = (int)ModArray.get(i) +
(int)ModArray.get(j);
// Check if sum becomes equal
if (s == sum)
{
i1 = i;
i2 = j;
System.out.println("True");
break;
}
// Increase and decrease
// the pointer accordingly
else if (s > sum)
j--;
else
i++;
}
}
}
// Driver code
public static void main(String args[])
{
int m = 2;
int []a = { 1, 3, 9 };
int n = a.length;
// Function call
func(n, m, a);
}
}
// This code is contributed by Stream_Cipher
Python3
# Python3 program for the above approach
# Function to check if any valid
# sequence is divisible by M
def func(n, m, A):
# DEclare mod array
ModArray = [0]*n
Sum = 0
# Calculate the mod array
for i in range(n):
ModArray[i] = A[i] % m
Sum += ModArray[i]
Sum = Sum % m
# Check if sum is divisible by M
if (Sum % m == 0) :
print("True")
return
# Check if sum is not divisible by 2
if (Sum % 2 != 0) :
print("False")
else :
# Remove the first element from
# the ModArray since it is not
# possible to place minus
# on the first element
ModArray.pop(0)
i = 0
# Decrease the size of array
j = len(ModArray) - 1
# Sort the array
ModArray.sort()
Sum = Sum // 2
# Loop until the pointer
# cross each other
while (i <= j) :
s = ModArray[i] + ModArray[j]
# Check if sum becomes equal
if (s == Sum) :
i1 = i
i2 = j
print("True")
break
# Increase and decrease
# the pointer accordingly
elif (s > Sum):
j -= 1
else:
i += 1
# Driver code
m = 2
a = [ 1, 3, 9 ]
n = len(a)
# Function call
func(n, m, a)
# This code is contributed by divyeshrabadiya07
C#
// C# program for the above approach
using System.Collections.Generic;
using System;
class GFG{
// Function to check if any valid
// sequence is divisible by M
static void func(int n, int m, int []A)
{
// Declare mod array
List<int> ModArray = new List<int>();
for(int i = 0; i < n; i++)
ModArray.Add(0);
int sum = 0;
// Calculate the mod array
for(int i = 0; i < n; i++)
{
ModArray[i] = (A[i] % m);
sum += ((int)ModArray[i]);
}
sum = sum % m;
// Check if sum is divisible by M
if (sum % m == 0)
{
Console.WriteLine("True");
return;
}
// Check if sum is not divisible by 2
if (sum % 2 != 0)
{
Console.WriteLine("False");
}
else
{
// Remove the first element from
// the ModArray since it is not
// possible to place minus
// on the first element
ModArray.Remove(0);
int i = 0;
// Decrease the size of array
int j = ModArray.Count - 1;
// Sort the array
ModArray.Sort();
sum = sum / 2;
int i1, i2;
// Loop until the pointer
// cross each other
while (i <= j)
{
int s = (int)ModArray[i] +
(int)ModArray[j];
// Check if sum becomes equal
if (s == sum)
{
i1 = i;
i2 = j;
Console.WriteLine("True");
break;
}
// Increase and decrease
// the pointer accordingly
else if (s > sum)
j--;
else
i++;
}
}
}
// Driver code
public static void Main()
{
int m = 2;
int []a = { 1, 3, 9 };
int n = a.Length;
// Function call
func(n, m, a);
}
}
// This code is contributed by Stream_Cipher
Javascript
<script>
// Javascript program for the above approach
// Function to check if any valid
// sequence is divisible by M
function func(n, m, A)
{
// Declare mod array
let ModArray = [];
for(let i = 0; i < n; i++)
ModArray.push(0);
let sum = 0;
// Calculate the mod array
for(let i = 0; i < n; i++)
{
ModArray[i] = A[i] % m;
sum += ModArray[i];
}
sum = sum % m;
// Check if sum is divisible by M
if (sum % m == 0)
{
document.write("True");
return;
}
// Check if sum is not divisible by 2
if (sum % 2 != 0)
{
document.write("False");
}
else
{
// Remove the first element from
// the ModArray since it is not
// possible to place minus
// on the first element
ModArray.shift();
let i = 0;
// Decrease the size of array
let j = ModArray.length - 1;
// Sort the array
ModArray.sort(function(a, b){return a - b});
sum = parseInt(sum / 2, 10);
let i1, i2;
// Loop until the pointer
// cross each other
while (i <= j)
{
let s = ModArray[i] + ModArray[j];
// Check if sum becomes equal
if (s == sum)
{
i1 = i;
i2 = j;
document.write("True");
break;
}
// Increase and decrease
// the pointer accordingly
else if (s > sum)
j--;
else
i++;
}
}
}
let m = 2;
let a = [ 1, 3, 9 ];
let n = a.length;
// Function call
func(n, m, a);
</script>
Producción
False
Complejidad de tiempo: O(n * log n)