Dada una array arr[] que consta de N enteros positivos y un entero positivo X , la tarea es verificar si la suma de la array dada puede hacerse igual a X eliminando el primer o el último dígito de cada elemento de la array. Si es posible hacer que la suma de los elementos de la array sea igual a X , imprima «Sí» . De lo contrario, escriba “No” .
Ejemplos:
Entrada: arr[] = {545, 433, 654, 23}, X = 134
Salida: Sí
Explicación:
La siguiente eliminación de dígitos hace que la suma de la array sea igual a X :
- Eliminar el primer dígito de arr[0] modifica arr[0] a 45.
- Eliminando el primer dígito de arr[1] se modifica a 33.
- Eliminar el primer dígito de arr[2] modifica arr[2] a 54.
- Eliminar el último dígito de arr[3] modifica arr[3] a 2.
La array modificada es {45, 33, 54, 2}. Por lo tanto, suma de la array modificada = 45 + 33 + 54 + 2 = 134(= X).
Entrada: arr[] = {54, 22, 76, 432}, X = 48
Salida: No
Enfoque: el problema dado se puede resolver usando la recursividad generando todas las formas posibles de eliminar el primer o el último dígito de cada elemento de la array. Siga los pasos a continuación para resolver el problema dado.
- Defina una función recursiva , digamos makeSumX(arr, S, i, X) que tome la array arr[] , la suma actual S , el índice actual i y la suma X requerida como parámetros y realice las siguientes operaciones:
- Si el índice actual es igual a la longitud de la array y la suma S actual es igual a la suma X requerida , entonces devuelve true . De lo contrario, devuelve falso .
- Convierte el entero arr[i] en una string .
- Elimine el último dígito del entero arr[i] y guárdelo en una variable, digamos L .
- Elimine el primer dígito del entero arr[i] y guárdelo en una variable, digamos R .
- Devuelve el valor de la función como Bitwise OR de makeSumX(arr, S + L, i + 1, X) y makeSumX(arr, S + R, i + 1, X) .
- Si el valor devuelto por la función makeSumX(arr, 0, 0, X) es verdadero, imprima «Sí» . De lo contrario, escriba “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;
// Utility Function to check if the sum
// of the array elements can be made
// equal to X by removing either the first
// or last digits of every array element
bool makeSumX(int arr[], int X, int S,
int i, int N)
{
// Base Case
if (i == N)
{
return S == X;
}
// Convert arr[i] to string
string a = to_string(arr[i]);
// Remove last digit
int l = stoi(a.substr(0, a.length() - 1));
// Remove first digit
int r = stoi(a.substr(1));
// Recursive function call
bool x = makeSumX(arr, X, S + l, i + 1, N);
bool y = makeSumX(arr, X, S + r, i + 1, N);
return (x || y);
}
// Function to check if sum of given
// array can be made equal to X or not
void Check(int arr[], int X, int N)
{
if (makeSumX(arr, X, 0, 0, N))
{
cout << "Yes";
}
else
{
cout << "No";
}
}
// Driver code
int main()
{
int arr[] = { 545, 433, 654, 23 };
int N = sizeof(arr) / sizeof(arr[0]);
int X = 134;
// Function Call
Check(arr, X, N);
return 0;
}
// This code is contributed by Kingash
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
// Utility Function to check if the sum
// of the array elements can be made
// equal to X by removing either the first
// or last digits of every array element
static boolean makeSumX(int arr[], int X,
int S, int i)
{
// Base Case
if (i == arr.length)
{
return S == X;
}
// Convert arr[i] to string
String a = Integer.toString(arr[i]);
// Remove last digit
int l = Integer.parseInt(
a.substring(0, a.length() - 1));
// Remove first digit
int r = Integer.parseInt(a.substring(1));
// Recursive function call
boolean x = makeSumX(arr, X, S + l, i + 1);
boolean y = makeSumX(arr, X, S + r, i + 1);
return (x || y);
}
// Function to check if sum of given
// array can be made equal to X or not
static void Check(int arr[], int X)
{
if (makeSumX(arr, X, 0, 0))
{
System.out.println("Yes");
}
else
{
System.out.println("No");
}
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 545, 433, 654, 23 };
int X = 134;
// Function Call
Check(arr, X);
}
}
// This code is contributed by Kingash
Python3
# Python3 program for the above approach
# Utility Function to check if the sum
# of the array elements can be made
# equal to X by removing either the first
# or last digits of every array element
def makeSumX(arr, X, S, i):
# Base Case
if i == len(arr):
return S == X
# Convert arr[i] to string
a = str(arr[i])
# Remove last digit
l = int(a[:-1])
# Remove first digit
r = int(a[1:])
# Recursive function call
x = makeSumX(arr, X, S + l, i + 1)
y = makeSumX(arr, X, S + r, i + 1)
return x | y
# Function to check if sum of given
# array can be made equal to X or not
def Check(arr, X):
if (makeSumX(arr, X, 0, 0)):
print("Yes")
else:
print("No")
# Driver Code
arr = [545, 433, 654, 23]
X = 134
Check(arr, X)
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Utility Function to check if the sum
// of the array elements can be made
// equal to X by removing either the first
// or last digits of every array element
static bool makeSumX(int[] arr, int X,
int S, int i)
{
// Base Case
if (i == arr.Length)
{
return S == X;
}
// Convert arr[i] to string
string a = Convert.ToString(arr[i]);
// Remove last digit
int l = Int32.Parse(
a.Substring(0, a.Length - 1));
// Remove first digit
int r = Int32.Parse(a.Substring(1));
// Recursive function call
bool x = makeSumX(arr, X, S + l, i + 1);
bool y = makeSumX(arr, X, S + r, i + 1);
return (x || y);
}
// Function to check if sum of given
// array can be made equal to X or not
static void Check(int[] arr, int X)
{
if (makeSumX(arr, X, 0, 0))
{
Console.Write("Yes");
}
else
{
Console.Write("No");
}
}
// Driver Code
public static void Main()
{
int[] arr = { 545, 433, 654, 23 };
int X = 134;
// Function Call
Check(arr, X);
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// Javascript program for the above approach
// Utility Function to check if the sum
// of the array elements can be made
// equal to X by removing either the first
// or last digits of every array element
function makeSumX(arr, X, S,
i, N) {
// Base Case
if (i === N) {
return S === X
}
// Convert arr[i] to string
let a = (arr[i]).toString()
// Remove last digit
let l = parseInt((a.substr(0, a.length - 1)))
// Remove first digit
let r = parseInt((a.substr(1)))
// Recursive function call
let x = makeSumX(arr, X, S + l, i + 1, N);
let y = makeSumX(arr, X, S + r, i + 1, N);
return (x || y);
}
// Function to check if sum of given
// array can be made equal to X or not
function Check(arr, X, N) {
if (makeSumX(arr, X, 0, 0, N)) {
document.write("Yes")
}
else {
document.write("No")
}
}
// Driver code
let arr = [545, 433, 654, 23];
let N = arr.length;
let X = 134;
// Function Call
Check(arr, X, N);
// This code is contributed by Hritik
</script>
Producción:
Yes
Complejidad temporal: O(2 N )
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por rohitsingh07052 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA