Máxima suma y producto de las M cifras consecutivas de un número

Dado un número en forma de string. La tarea es encontrar la suma y el producto máximos de m dígitos consecutivos que se toman de la string de números.
Ejemplos: 
 

Entrada: N = 3675356291, m = 5 
Salida: 3150 
Hay 6 secuencias de 5 dígitos 36753, 67535, 75356, 53562, 35629, 56291 
6 x 7 x 5 x 3 x 5 da el producto máximo.
Entrada: N = 2709360626, m = 5 
Salida:
Dado que cada secuencia de 5 dígitos consecutivos contendrá un 0, por lo que cada vez que el producto sea cero, 
el producto máximo será cero.
 

Enfoque ingenuo: 
 

  1. Tome todas las secuencias consecutivas posibles de m caracteres de la string dada.
  2. Súmalos y multiplícalos cambiando los caracteres a números enteros.
  3. Compara el producto y la suma de cada secuencia y encuentra el producto y la suma máximos.

A continuación se muestra la implementación del enfoque anterior: 
 

C++

// Code is Improved by Surya Prakash Sharma
 
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum product
void maxProductSum(string str, int m)
{
    int n = str.length();
    int maxProd = INT_MIN, maxSum = INT_MIN;
    for (int i = 0; i <=n - m; i++) {
        int product = 1, sum = 0;
 
        for (int j = i; j < m + i; j++) {
            product = product * (str[j] - '0');
            sum = sum + (str[j] - '0');
        }
 
        maxProd = max(maxProd, product);
        maxSum = max(maxSum, sum);
    }
    cout << "Maximum Product = " << maxProd;
    cout << "\nMaximum Sum = " << maxSum;
}
 
// Driver code
int main()
{
    string str = "3605356297";
    int m = 3;
 
    maxProductSum(str, m);
}

Java

// Code is Improved by Surya Prakash Sharma
 
 // Java implementation of the above approach
 
import java.io.*;
 
class GFG {
  
 
// Function to find the maximum product
 static void maxProductSum(String str, int m)
{
    int n = str.length();
    int maxProd = Integer.MIN_VALUE, maxSum = Integer.MIN_VALUE;
    for (int i = 0; i <=n - m; i++) {
        int product = 1, sum = 0;
 
        for (int j = i; j < m + i; j++) {
            product = product * (str.charAt(j) - '0');
            sum = sum + (str.charAt(j) - '0');
        }
 
        maxProd = Math.max(maxProd, product);
        maxSum = Math.max(maxSum, sum);
    }
    System.out.println("Maximum Product = " + maxProd);
    System.out.print( "\nMaximum Sum = " + maxSum);
}
 
// Driver code
 
    public static void main (String[] args) {
        String str = "3605356297";
    int m = 3;
 
    maxProductSum(str, m);
    }
}
// This code is contributed by anuj_67..

Python 3

# Code is Improved by Surya Prakash Sharma
 
# Python implementation of
# above approach
import sys
 
# Function to find the maximum product
def maxProductSum(string, m) :
 
    n = len(string)
    maxProd , maxSum = (-(sys.maxsize) - 1,
                        -(sys.maxsize) - 1)
 
    for i in range(n - m+1) :
        product, sum = 1, 0
 
        for j in range(i, m + i) :
            product = product * (ord(string[j]) -
                                 ord('0'))
            sum = sum + (ord(string[j]) -
                         ord('0'))
 
        maxProd = max(maxProd, product)
        maxSum = max(maxSum, sum)
 
    print("Maximum Product =", maxProd)
    print("Maximum sum =", maxSum)
     
# Driver code
if __name__ == "__main__" :
 
    string = "3605356297"
    m = 3
    maxProductSum(string, m)
         
# This code is contributed by ANKITRAI1

C#

// Code is Improved by Surya Prakash Sharma
 
// C# implementation of the above approach
using System;
class GFG
{
     
// Function to find the maximum product
static void maxProductSum(string str, int m)
{
    int n = str.Length;
    int maxProd = int.MinValue,
        maxSum = int.MinValue;
    for (int i = 0; i <= n - m; i++)
    {
        int product = 1, sum = 0;
 
        for (int j = i; j < m + i; j++)
        {
            product = product * (str[j] - '0');
            sum = sum + (str[j] - '0');
        }
 
        maxProd = Math.Max(maxProd, product);
        maxSum = Math.Max(maxSum, sum);
    }
    Console.WriteLine("Maximum Product = " + maxProd);
    Console.Write( "\nMaximum Sum = " + maxSum);
}
 
// Driver code
public static void Main ()
{
    string str = "3605356297";
    int m = 3;
     
    maxProductSum(str, m);
}
}
 
// This code is contributed
// by Akanksha Rai

PHP

<?php
// Code is Improved by Surya Prakash Sharma
   
// PHP implementation of the above approach
 
// Function to find the maximum product
function maxProductSum($str, $m)
{
    $n = strlen($str);
    $maxProd = PHP_INT_MIN;
    $maxSum = PHP_INT_MIN;
    for ($i = 0; $i <= ($n - $m); $i++)
    {
        $product = 1;
        $sum = 0;
 
        for ($j = $i; $j < ($m + $i); $j++)
        {
            $product = $product *
                      ($str[$j] - '0');
            $sum = $sum + ($str[$j] - '0');
        }
 
        $maxProd = max($maxProd, $product);
        $maxSum = max($maxSum, $sum);
    }
    echo "Maximum Product = " ,$maxProd;
    echo "\nMaximum Sum = " , $maxSum;
}
 
// Driver code
$str = "3605356297";
$m = 3;
 
maxProductSum($str, $m);
 
// This code is contributed by @Tushil.
?>

Javascript

<script>
    // Code is Improved by Surya Prakash Sharma
     
    // Javascript implementation of the above approach
     
    // Function to find the maximum product
    function maxProductSum(str, m)
    {
        let n = str.length;
        let maxProd = Number.MIN_VALUE,
            maxSum = Number.MIN_VALUE;
        for (let i = 0; i <= n - m; i++)
        {
            let product = 1, sum = 0;
 
            for (let j = i; j < m + i; j++)
            {
                product = product * (str[j] - '0');
                sum = sum + (str[j] - '0');
            }
 
            maxProd = Math.max(maxProd, product);
            maxSum = Math.max(maxSum, sum);
        }
        document.write("Maximum Product = " + maxProd + "</br>");
        document.write( "Maximum Sum = " + maxSum);
    }
     
    let str = "3605356297";
    let m = 3;
       
    maxProductSum(str, m);
     
</script>
Producción

Maximum Product = 126
Maximum Sum = 18

Enfoque Eficiente: La idea es utilizar el concepto de Ventana Deslizante . Primero encuentre la suma y el producto de M dígitos consecutivos y actualice maxProd y maxSum. 
Luego comience a atravesar desde Mth index y agregue el dígito actual a la suma y reste str[iM] de la suma, es decir, considerando solo M elementos/dígitos. Del mismo modo para el producto. Y sigue actualizando maxSum y maxProd.
 

C++

// Code Improved By Surya Prakash Sharma
 
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum product and sum
void maxProductSum(string str, int m)
{
    int n = str.length();
    int product = 1, sum = 0, ZeroesInWindow=0;
 
    // find the sum and product of first K digits
    for (int i = 0; i < m; i++) {
        sum += (str[i] - '0');
       
        if(str[i]!='0')
        product *= (str[i] - '0');
        else
        ZeroesInWindow++;
    }
 
    // Update maxProd and maxSum
    int maxProd = 0;
    if(ZeroesInWindow==0)
      maxProd = product;
    int maxSum = sum;
 
    // Start traversing the next element
    for (int i = m; i < n; i++) {
 
         
       
       
        // Multiply with the current digit and divide by
        // the first digit of previous window
        if(str[i]!='0' && str[i-m]!='0')
        product = product * (str[i] - '0') / ((str[i - m]) - '0');
        else if(str[i]!='0' && str[i-m]=='0')
        { 
           product = product * (str[i] - '0');
           ZeroesInWindow--;
        }
        else if(str[i]=='0' && str[i-m]!='0')
        {
           product = product / (str[i-m] - '0');
           ZeroesInWindow++;
        }
       
        // Update maxProd
        if(ZeroesInWindow==0)
        maxProd = max(maxProd, product);
 
        // Add the current digit and subtract
        // the first digit of previous window
        sum = sum + (str[i] - '0') - ((str[i - m]) - '0');
 
        // Update maxSum
        maxSum = max(maxSum, sum);
    }
 
    cout << "Maximum Product = " << maxProd;
    cout << "\nMaximum Sum = " << maxSum;
}
 
// Driver code
int main()
{
    string str = "3601990545";
    int m = 3;
 
    maxProductSum(str, m);
}

Java

// Code Improved By Surya Prakash Sharma
 
// Java implementation of the above approach
import java.util.Arrays;
import java.io.*;
 
class GFG {
     
// Function to find the maximum product and sum
static void maxProductSum(String str, int m)
{
    int n = str.length();
    int product = 1, sum = 0, ZeroesInWindow=0;
 
    // find the sum and product of first K digits
    for (int i = 0; i < m; i++)
    {
        sum += (str.charAt(i) - '0');
       
        if(str.charAt(i)!='0')
        product *= (str.charAt(i) - '0');
        else
        ZeroesInWindow++;
         
    }
 
    // Update maxProd and maxSum
    int maxProd = 0;
    if(ZeroesInWindow==0)
      maxProd = product;
    int maxSum = sum;
 
    // Start traversing the next element
    for (int i = m; i < n; i++)
    {
 
        // Multiply with the current digit and divide by
        // the first digit of previous window
        if(str.charAt(i)!='0' && str.charAt(i-m)!='0')
        product = product * (str.charAt(i) - '0') / ((str.charAt(i-m)) - '0');
        else if(str.charAt(i)!='0' && str.charAt(i-m)=='0')
        { 
           product = product * (str.charAt(i) - '0');
           ZeroesInWindow--;
        }
        else if(str.charAt(i)=='0' && str.charAt(i-m)!='0')
        {
           product = product / (str.charAt(i-m) - '0');
           ZeroesInWindow++;
        }
       
        // Update maxProd
        if(ZeroesInWindow==0)
        maxProd = Math.max(maxProd, product);
 
        // Add the current digit and subtract
        // the first digit of previous window
        sum = sum + (str.charAt(i) - '0') - ((str.charAt(i-m)) - '0');
 
        // Update maxSum
        maxSum = Math.max(maxSum, sum);
    }
 
    System.out.println("Maximum Product = " + maxProd);
    System.out.println("\nMaximum Sum = " + maxSum);
}
 
// Driver code
    public static void main (String[] args) {
        String str = "3601990545";
        int m = 3;
        maxProductSum(str, m);
    }
}
 
// This code is contributed
// by ajit

Python 3

# Python 3 implementation of the above approach
 
# Function to find the maximum product and sum
def maxProductSum(str, m):
 
    n = len(str)
    product = 1
    sum = 0
 
    # find the sum and product of first K digits
    for i in range(m):
        sum += (ord(str[i]) - ord('0'))
        product *= (ord(str[i]) - ord('0'))
 
    # Update maxProd and maxSum
    maxProd = product
    maxSum = sum
 
    # Start traversing the next element
    for i in range(m, n) :
 
        # Multiply with the current digit and divide
        # by the first digit of previous window
        product = (product * (ord(str[i]) - ord('0')) //
                            ((ord(str[i - m])) - ord('0')))
 
        # Add the current digit and subtract
        # the first digit of previous window
        sum = (sum + (ord(str[i]) - ord('0')) -
                    ((ord(str[i - m])) - ord('0')))
 
        # Update maxProd and maxSum
        maxProd = max(maxProd, product)
        maxSum = max(maxSum, sum)
 
    print("Maximum Product =", maxProd)
    print("Maximum Sum =", maxSum)
 
# Driver code
if __name__ == "__main__":
     
    str = "3675356291"
    m = 5
 
    maxProductSum(str, m)
 
# This code is contributed by ita_c

C#

// C# implementation of the above approach
using System;
 
class GFG
{
// Function to find the maximum product and sum
static void maxProductSum(string str, int m)
{
    int n = str.Length;
    int product = 1, sum = 0;
 
    // find the sum and product of first K digits
    for (int i = 0; i < m; i++)
    {
        sum += (str[i] - '0');
        product *= (str[i] - '0');
    }
 
    // Update maxProd and maxSum
    int maxProd = product;
    int maxSum = sum;
 
    // Start traversing the next element
    for (int i = m; i < n; i++)
    {
 
        // Multiply with the current digit and divide by
        // the first digit of previous window
        product = product * (str[i] - '0') / ((str[i - m]) - '0');
 
        // Add the current digit and subtract
        // the first digit of previous window
        sum = sum + (str[i] - '0') - ((str[i - m]) - '0');
 
        // Update maxProd and maxSum
        maxProd = Math.Max(maxProd, product);
        maxSum = Math.Max(maxSum, sum);
    }
 
    Console.Write("Maximum Product = " + maxProd);
    Console.Write("\nMaximum Sum = " + maxSum);
}
 
// Driver code
public static void Main()
{
    string str = "3675356291";
    int m = 5;
 
    maxProductSum(str, m);
}
}
 
// This code is contributed
// by Akanksha Rai

PHP

<?php
// PHP implementation of the above approach
 
// Function to find the maximum
// product and sum
function maxProductSum($str, $m)
{
    $n = strlen($str);
    $product = 1;
    $sum = 0;
     
    // find the sum and product of
    // first K digits
    for ($i = 0; $i < $m; $i++)
    {
        $sum += ($str[$i] - '0');
        $product *= ($str[$i] - '0');
    }
 
    // Update maxProd and maxSum
    $maxProd = $product;
    $maxSum = $sum;
 
    // Start traversing the next element
    for ($i = $m; $i < $n; $i++)
    {
 
        // Multiply with the current digit and divide
        // by the first digit of previous window
        $product = $product * ($str[$i] - '0') /
                             (($str[$i - $m]) - '0');
 
        // Add the current digit and subtract
        // the first digit of previous window
        $sum = $sum + ($str[$i] - '0') -
                     (($str[$i - $m]) - '0');
 
        // Update maxProd and maxSum
        $maxProd = max($maxProd, $product);
        $maxSum = max($maxSum, $sum);
    }
 
    echo "Maximum Product = " , $maxProd;
    echo "\nMaximum Sum = " , $maxSum;
}
 
// Driver code
$str = "3675356291";
$m = 5;
maxProductSum($str, $m);
 
// This code is contributed by ajit
?>

Javascript

<script>   
    // Javascript implementation of the above approach
     
    // Function to find the maximum product and sum
    function maxProductSum(str, m)
    {
        let n = str.length;
        let product = 1, sum = 0;
 
        // find the sum and product of first K digits
        for (let i = 0; i < m; i++)
        {
            sum += (str[i].charCodeAt() - '0'.charCodeAt());
            product *= (str[i].charCodeAt() - '0'.charCodeAt());
        }
 
        // Update maxProd and maxSum
        let maxProd = product;
        let maxSum = sum;
 
        // Start traversing the next element
        for (let i = m; i < n; i++)
        {
 
            // Multiply with the current digit and divide by
            // the first digit of previous window
            product = product * (str[i].charCodeAt() - '0'.charCodeAt()) / ((str[i - m].charCodeAt()) - '0'.charCodeAt());
 
            // Add the current digit and subtract
            // the first digit of previous window
            sum = sum + (str[i].charCodeAt() - '0'.charCodeAt()) - ((str[i - m].charCodeAt()) - '0'.charCodeAt());
 
            // Update maxProd and maxSum
            maxProd = Math.max(maxProd, product);
            maxSum = Math.max(maxSum, sum);
        }
 
        document.write("Maximum Product = " + maxProd + "</br>");
        document.write("Maximum Sum = " + maxSum);
    }
     
    let str = "3675356291";
    let m = 5;
  
    maxProductSum(str, m);
 
</script>
Producción

Maximum Product = 100
Maximum Sum = 19

Publicación traducida automáticamente

Artículo escrito por SURENDRA_GANGWAR y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *