Dada una array de dígitos de longitud n> 1, los dígitos se encuentran dentro del rango de 0 a 9. Realizamos una secuencia de las siguientes tres operaciones hasta que terminamos con todos los dígitos.
- Seleccione dos dígitos iniciales y agregue (+)
- Luego, el siguiente dígito se resta (-) del resultado del paso anterior.
- El resultado del paso anterior se multiplica (X) con el siguiente dígito.
Realizamos la secuencia anterior de operaciones linealmente con los dígitos restantes.
La tarea es encontrar cuántas permutaciones de una array dada producen un resultado positivo después de las operaciones anteriores.
Por ejemplo, considere el número de entrada [] = {1, 2, 3, 4, 5}. Consideremos una permutación 21345 para demostrar la secuencia de operaciones.
- Suma los dos primeros dígitos, resultado = 2+1 = 3
- Resta el dígito siguiente, resultado = resultado-3 = 3-3 = 0
- Multiplica el dígito siguiente, resultado=resultado*4= 0*4 = 0
- Agregar el siguiente dígito, resultado = resultado+5 = 0+5 = 5
- resultado = 5, que es positivo, así que incremente el conteo en uno
Ejemplos:
Input : number[]="123" Output: 4 // here we have all permutations // 123 --> 1+2 -> 3-3 -> 0 // 132 --> 1+3 -> 4-2 -> 2 ( positive ) // 213 --> 2+1 -> 3-3 -> 0 // 231 --> 2+3 -> 5-1 -> 4 ( positive ) // 312 --> 3+1 -> 4-2 -> 2 ( positive ) // 321 --> 3+2 -> 5-1 -> 4 ( positive ) // total 4 permutations are giving positive result Input : number[]="112" Output: 2 // here we have all permutations possible // 112 --> 1+1 -> 2-2 -> 0 // 121 --> 1+2 -> 3-1 -> 2 ( positive ) // 211 --> 2+1 -> 3-1 -> 2 ( positive )
Preguntado en: Morgan Stanley
Primero generamos todas las permutaciones posibles de una array de dígitos dada y realizamos una secuencia dada de operaciones secuencialmente en cada permutación y verificamos qué resultado de permutación es positivo. El siguiente código describe la solución del problema fácilmente.
Nota: Podemos generar todas las permutaciones posibles usando el método iterativo, consulte este artículo o podemos usar la función STL next_permutation() para generarla.
C++
// C++ program to find count of permutations that produce
// positive result.
#include<bits/stdc++.h>
using namespace std;
// function to find all permutation after executing given
// sequence of operations and whose result value is positive
// result > 0 ) number[] is array of digits of length of n
int countPositivePermutations(int number[], int n)
{
// First sort the array so that we get all permutations
// one by one using next_permutation.
sort(number, number+n);
// Initialize result (count of permutations with positive
// result)
int count = 0;
// Iterate for all permutation possible and do operation
// sequentially in each permutation
do
{
// Stores result for current permutation. First we
// have to select first two digits and add them
int curr_result = number[0] + number[1];
// flag that tells what operation we are going to
// perform
// operation = 0 ---> addition operation ( + )
// operation = 1 ---> subtraction operation ( - )
// operation = 0 ---> multiplication operation ( X )
// first sort the array of digits to generate all
// permutation in sorted manner
int operation = 1;
// traverse all digits
for (int i=2; i<n; i++)
{
// sequentially perform + , - , X operation
switch (operation)
{
case 0:
curr_result += number[i];
break;
case 1:
curr_result -= number[i];
break;
case 2:
curr_result *= number[i];
break;
}
// next operation (decides case of switch)
operation = (operation + 1) % 3;
}
// result is positive then increment count by one
if (curr_result > 0)
count++;
// generate next greater permutation until it is
// possible
} while(next_permutation(number, number+n));
return count;
}
// Driver program to test the case
int main()
{
int number[] = {1, 2, 3};
int n = sizeof(number)/sizeof(number[0]);
cout << countPositivePermutations(number, n);
return 0;
}
Java
// Java program to find count of permutations
// that produce positive result.
import java.util.*;
class GFG
{
// function to find all permutation after
// executing given sequence of operations
// and whose result value is positive result > 0 )
// number[] is array of digits of length of n
static int countPositivePermutations(int number[],
int n)
{
// First sort the array so that we get
// all permutations one by one using
// next_permutation.
Arrays.sort(number);
// Initialize result (count of permutations
// with positive result)
int count = 0;
// Iterate for all permutation possible and
// do operation sequentially in each permutation
do
{
// Stores result for current permutation.
// First we have to select first two digits
// and add them
int curr_result = number[0] + number[1];
// flag that tells what operation we are going to
// perform
// operation = 0 ---> addition operation ( + )
// operation = 1 ---> subtraction operation ( - )
// operation = 0 ---> multiplication operation ( X )
// first sort the array of digits to generate all
// permutation in sorted manner
int operation = 1;
// traverse all digits
for (int i = 2; i < n; i++)
{
// sequentially perform + , - , X operation
switch (operation)
{
case 0:
curr_result += number[i];
break;
case 1:
curr_result -= number[i];
break;
case 2:
curr_result *= number[i];
break;
}
// next operation (decides case of switch)
operation = (operation + 1) % 3;
}
// result is positive then increment count by one
if (curr_result > 0)
count++;
// generate next greater permutation until
// it is possible
} while(next_permutation(number));
return count;
}
static boolean next_permutation(int[] p)
{
for (int a = p.length - 2; a >= 0; --a)
if (p[a] < p[a + 1])
for (int b = p.length - 1;; --b)
if (p[b] > p[a])
{
int t = p[a];
p[a] = p[b];
p[b] = t;
for (++a, b = p.length - 1; a < b; ++a, --b)
{
t = p[a];
p[a] = p[b];
p[b] = t;
}
return true;
}
return false;
}
// Driver Code
public static void main(String[] args)
{
int number[] = {1, 2, 3};
int n = number.length;
System.out.println(countPositivePermutations(number, n));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 program to find count of permutations # that produce positive result. # function to find all permutation after # executing given sequence of operations # and whose result value is positive result > 0 ) # number[] is array of digits of length of n def countPositivePermutations(number, n): # First sort the array so that we get # all permutations one by one using # next_permutation. number.sort() # Initialize result (count of permutations # with positive result) count = 0; # Iterate for all permutation possible and # do operation sequentially in each permutation while True: # Stores result for current permutation. # First we have to select first two digits # and add them curr_result = number[0] + number[1]; # flag that tells what operation we are going to # perform # operation = 0 ---> addition operation ( + ) # operation = 1 ---> subtraction operation ( - ) # operation = 0 ---> multiplication operation ( X ) # first sort the array of digits to generate all # permutation in sorted manner operation = 1; # traverse all digits for i in range(2, n): # sequentially perform + , - , X operation if operation == 0: curr_result += number[i]; else if operation == 1: curr_result -= number[i]; else if operation == 2: curr_result *= number[i]; # next operation (decides case of switch) operation = (operation + 1) % 3; # result is positive then increment count by one if (curr_result > 0): count += 1 # generate next greater permutation until # it is possible if(not next_permutation(number)): break return count; def next_permutation(p): for a in range(len(p)-2, -1, -1): if (p[a] < p[a + 1]): for b in range(len(p)-1, -1000000000, -1): if (p[b] > p[a]): t = p[a]; p[a] = p[b]; p[b] = t; a += 1 b = len(p) - 1 while(a < b): t = p[a]; p[a] = p[b]; p[b] = t; a += 1 b -= 1 return True; return False; # Driver Code if __name__ =='__main__': number = [1, 2, 3] n = len(number) print(countPositivePermutations(number, n)); # This code is contributed by rutvik_56.
C#
// C# program to find count of permutations
// that produce positive result.
using System;
class GFG
{
// function to find all permutation after
// executing given sequence of operations
// and whose result value is positive result > 0 )
// number[] is array of digits of length of n
static int countPositivePermutations(int []number,
int n)
{
// First sort the array so that we get
// all permutations one by one using
// next_permutation.
Array.Sort(number);
// Initialize result (count of permutations
// with positive result)
int count = 0;
// Iterate for all permutation possible and
// do operation sequentially in each permutation
do
{
// Stores result for current permutation.
// First we have to select first two digits
// and add them
int curr_result = number[0] + number[1];
// flag that tells what operation we are going to
// perform
// operation = 0 ---> addition operation ( + )
// operation = 1 ---> subtraction operation ( - )
// operation = 0 ---> multiplication operation ( X )
// first sort the array of digits to generate all
// permutation in sorted manner
int operation = 1;
// traverse all digits
for (int i = 2; i < n; i++)
{
// sequentially perform + , - , X operation
switch (operation)
{
case 0:
curr_result += number[i];
break;
case 1:
curr_result -= number[i];
break;
case 2:
curr_result *= number[i];
break;
}
// next operation (decides case of switch)
operation = (operation + 1) % 3;
}
// result is positive then increment count by one
if (curr_result > 0)
count++;
// generate next greater permutation until
// it is possible
} while(next_permutation(number));
return count;
}
static bool next_permutation(int[] p)
{
for (int a = p.Length - 2; a >= 0; --a)
if (p[a] < p[a + 1])
for (int b = p.Length - 1;; --b)
if (p[b] > p[a])
{
int t = p[a];
p[a] = p[b];
p[b] = t;
for (++a, b = p.Length - 1;
a < b; ++a, --b)
{
t = p[a];
p[a] = p[b];
p[b] = t;
}
return true;
}
return false;
}
// Driver Code
static public void Main ()
{
int []number = {1, 2, 3};
int n = number.Length;
Console.Write(countPositivePermutations(number, n));
}
}
// This code is contributed by ajit..
Javascript
<script>
// Javascript program to find count of permutations
// that produce positive result.
// function to find all permutation after
// executing given sequence of operations
// and whose result value is positive result > 0 )
// number[] is array of digits of length of n
function countPositivePermutations(number, n)
{
// First sort the array so that we get
// all permutations one by one using
// next_permutation.
number.sort(function(a, b){return a - b});
// Initialize result (count of permutations
// with positive result)
let count = 0;
// Iterate for all permutation possible and
// do operation sequentially in each permutation
do
{
// Stores result for current permutation.
// First we have to select first two digits
// and add them
let curr_result = number[0] + number[1];
// flag that tells what operation we are going to
// perform
// operation = 0 ---> addition operation ( + )
// operation = 1 ---> subtraction operation ( - )
// operation = 0 ---> multiplication operation ( X )
// first sort the array of digits to generate all
// permutation in sorted manner
let operation = 1;
// traverse all digits
for (let i = 2; i < n; i++)
{
// sequentially perform + , - , X operation
switch (operation)
{
case 0:
curr_result += number[i];
break;
case 1:
curr_result -= number[i];
break;
case 2:
curr_result *= number[i];
break;
}
// next operation (decides case of switch)
operation = (operation + 1) % 3;
}
// result is positive then increment count by one
if (curr_result > 0)
count++;
// generate next greater permutation until
// it is possible
} while(next_permutation(number));
return count;
}
function next_permutation(p)
{
for (let a = p.length - 2; a >= 0; --a)
if (p[a] < p[a + 1])
for (let b = p.length - 1;; --b)
if (p[b] > p[a])
{
let t = p[a];
p[a] = p[b];
p[b] = t;
for (++a, b = p.length - 1;
a < b; ++a, --b)
{
t = p[a];
p[a] = p[b];
p[b] = t;
}
return true;
}
return false;
}
let number = [1, 2, 3];
let n = number.length;
document.write(countPositivePermutations(number, n));
</script>
Producción:
4
Si tiene una solución mejor y optimizada para este problema, compártala en los comentarios.
Este artículo es una contribución de Shashank Mishra (Gullu) y revisado por el equipo geeksforgeeks. Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA