Suma mínima después de restar múltiplos de k de los elementos de la array

Dado un entero  y una array de enteros, la tarea es encontrar la suma mínima posible de todos los elementos de la array después de que se reducen al restar un múltiplo de  de cada elemento (el resultado debe ser positivo y cada elemento de la array debe ser iguales después de esta reducción). Si la array no se puede reducir, imprima 

Tenga en cuenta que un elemento puede reducirse o no en el estado final de la array.

Ejemplos: 

Input: arr[] = {2, 3, 4, 5}, K = 1 
Output: 4 
Subtract 1 form 2, arr[] = {1, 3, 4, 5} 
Subtract 2 from 3, arr[] = {1, 1, 4, 5} 
Subtract 3 from 4, arr[] = {1, 1, 1, 5} 
Subtract 4 from 5 to make arr[] = {1, 1, 1, 1}, thus giving minimum possible sum as 4.

Input: arr[] = {5, 6, 7}, K = 2 
Output: -1 

Enfoque: Primero, la array debe ordenarse ya que el problema se puede resolver utilizando el enfoque codicioso . 

• Ordene la array, si arr[0] < 0 , imprima -1 ya que cada elemento debe ser ≥ 0.
• Si K == 0 , ningún elemento puede reducirse más. Entonces, para tener una respuesta, todos los elementos de la array deben ser iguales. Entonces la suma de los elementos es n * arr[0] else print -1 .
• Ahora, para el resto de los elementos, ejecute un ciclo de 1 an y compruebe si ((arr[i] – arr[0]) % K) == 0 , es decir , arr[i] se puede reducir a arr[0] .
• Si la condición anterior falla para algún elemento, imprima -1 .
• De lo contrario, si k == 1 , la respuesta es n , es decir, todos los elementos se reducirán a 1 .
• De lo contrario, la respuesta es n * (a[0] % k) .

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

// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// function to calculate minimum sum after transformation
int min_sum(int n, int k, int a[])
{
 
    sort(a, a + n);
 
    if (a[0] < 0)
        return -1;
     
 
    // no element can be reduced further
    if (k == 0) {
 
        // if all the elements of the array
        // are identical
        if (a[0] == a[n - 1])
            return (n * a[0]);
        else
            return -1;
    }
    else {
        int f = 0;
        for (int i = 1; i < n; i++) {
 
            int p = a[i] - a[0];
 
            // check if a[i] can be reduced to a[0]
            if (p % k == 0)
                continue;
            else {
                f = 1;
                break;
            }
        }
 
        // one of the elements cannot be reduced
        // to be equal to the other elements
        if (f)
            return -1;
        else {
 
            // if k = 1 then all elements can be reduced to 1
            if (k == 1)
                return n;
            else
                return (n * (a[0] % k));
        }
    }
}
 
// Driver code
int main()
{
    int arr[] = { 2, 3, 4, 5 };
    int K = 1;
    int N = sizeof(arr) / sizeof(arr[0]);
    cout << min_sum(N, K, arr);
 
    return 0;
}

// Java program of the above approach
 
import java.io.*;
import java.util.*;
class GFG {
     
// function to calculate minimum sum after transformation
static int min_sum(int n, int k, int a[])
{
 
    Arrays.sort(a);
 
    if (a[0] < 0)
        return -1;
     
 
    // no element can be reduced further
    if (k == 0) {
 
        // if all the elements of the array
        // are identical
        if (a[0] == a[n - 1])
            return (n * a[0]);
        else
            return -1;
    }
    else {
        int f = 0;
        for (int i = 1; i < n; i++) {
 
            int p = a[i] - a[0];
 
            // check if a[i] can be reduced to a[0]
            if (p % k == 0)
                continue;
            else {
                f = 1;
                break;
            }
        }
 
        // one of the elements cannot be reduced
        // to be equal to the other elements
        if (f>0)
            return -1;
        else {
 
            // if k = 1 then all elements can be reduced to 1
            if (k == 1)
                return n;
            else
                return (n * (a[0] % k));
        }
    }
}
 
// Driver code
 
 
    public static void main (String[] args) {
            int arr[] = { 2, 3, 4, 5 };
    int K = 1;
    int N = arr.length;
    System.out.println(min_sum(N, K, arr));
    }
}
// This code is contributed by shs..

# Python 3 program of the above approach
 
# function to calculate minimum sum
# after transformation
def min_sum(n, k, a):
    a.sort(reverse = False)
 
    if (a[0] < 0):
        return -1
     
    # no element can be reduced further
    if (k == 0):
         
        # if all the elements of the
        # array are identical
        if (a[0] == a[n - 1]):
            return (n * a[0])
        else:
            return -1
     
    else:
        f = 0
        for i in range(1, n, 1):
            p = a[i] - a[0]
 
            # check if a[i] can be
            # reduced to a[0]
            if (p % k == 0):
                continue
            else:
                f = 1
                break
         
        # one of the elements cannot be reduced
        # to be equal to the other elements
        if (f):
            return -1
        else:
             
            # if k = 1 then all elements
            # can be reduced to 1
            if (k == 1):
                return n
            else:
                return (n * (a[0] % k))
     
# Driver code
if __name__ == '__main__':
    arr = [2, 3, 4, 5]
    K = 1
    N = len(arr)
    print(min_sum(N, K, arr))
 
# This code is contributed by
# Surendra_Gangwar

// C# program of the above approach
using System;
 
class GFG
{
     
// function to calculate minimum
// sum after transformation
static int min_sum(int n, int k, int[] a)
{
 
    Array.Sort(a);
 
    if (a[0] < 0)
        return -1;
 
    // no element can be reduced further
    if (k == 0)
    {
 
        // if all the elements of the array
        // are identical
        if (a[0] == a[n - 1])
            return (n * a[0]);
        else
            return -1;
    }
    else
    {
        int f = 0;
        for (int i = 1; i < n; i++)
        {
            int p = a[i] - a[0];
 
            // check if a[i] can be
            // reduced to a[0]
            if (p % k == 0)
                continue;
            else
            {
                f = 1;
                break;
            }
        }
 
        // one of the elements cannot be reduced
        // to be equal to the other elements
        if (f > 0)
            return -1;
        else
        {
 
            // if k = 1 then all elements can
            // be reduced to 1
            if (k == 1)
                return n;
            else
                return (n * (a[0] % k));
        }
    }
}
 
// Driver code
public static void Main ()
{
    int[] arr = new int[] { 2, 3, 4, 5 };
    int K = 1;
    int N = arr.Length;
    Console.WriteLine(min_sum(N, K, arr));
}
}
 
// This code is contributed by mits

<?php
// PHP program of the above approach
 
// function to calculate minimum
// sum after transformation
function min_sum($n, $k, $a)
{
 
    sort($a);
 
    if ($a[0] < 0)
        return -1;
     
 
    // no element can be reduced further
    if ($k == 0)
    {
 
        // if all the elements of the array
        // are identical
        if ($a[0] == $a[$n - 1])
            return ($n * $a[0]);
        else
            return -1;
    }
    else
    {
        $f = 0;
        for ($i = 1; $i <$n; $i++)
        {
 
            $p = $a[$i] - $a[0];
 
            // check if a[i] can be reduced to a[0]
            if ($p % $k == 0)
                continue;
            else
            {
                $f = 1;
                break;
            }
        }
 
        // one of the elements cannot be reduced
        // to be equal to the other elements
        if ($f)
            return -1;
        else
        {
 
            // if k = 1 then all elements can
            // be reduced to 1
            if ($k == 1)
                return $n;
            else
                return ($n * ($a[0] % $k));
        }
    }
}
 
// Driver code
$arr = array(2, 3, 4, 5 );
$K = 1;
$N = count($arr);
echo min_sum($N, $K, $arr);
 
// This code is contributed by inder_verma
?>

<script>
 
// Javascript program of the above approach
 
// function to calculate minimum sum after transformation
function min_sum(n, k, a)
{
 
    a.sort();
 
    if (a[0] < 0)
        return -1;
     
 
    // no element can be reduced further
    if (k == 0) {
 
        // if all the elements of the array
        // are identical
        if (a[0] == a[n - 1])
            return (n * a[0]);
        else
            return -1;
    }
    else {
        let f = 0;
        for (let i = 1; i < n; i++) {
 
            let p = a[i] - a[0];
 
            // check if a[i] can be reduced to a[0]
            if (p % k == 0)
                continue;
            else {
                f = 1;
                break;
            }
        }
 
        // one of the elements cannot be reduced
        // to be equal to the other elements
        if (f>0)
            return -1;
        else {
 
            // if k = 1 then all elements can be reduced to 1
            if (k == 1)
                return n;
            else
                return (n * (a[0] % k));
        }
    }
}
 
// Driver code
 
    let arr = [ 2, 3, 4, 5 ];
    let K = 1;
    let N = arr.length;
    document.write(min_sum(N, K, arr));
 
</script>

4

Complejidad de tiempo: O (nlogn)

 Espacio Auxiliar: O(1)

Más optimizaciones: 

En lugar de ordenar la array, podemos encontrar el elemento mínimo en tiempo O(n). Podemos comprobar si todos los elementos son iguales o no también en tiempo O(n).

Los pasos involucrados en este enfoque son los siguientes:

1.  Encuentre el elemento mínimo en la array y guárdelo en el nombre de la variable val.
2.  Ahora, si val < 0, imprima -1 ya que cada elemento debe ser ≥ 0 y si el elemento mínimo es mayor o igual a 0, entonces todos los elementos serán mayores que 0.
3.  Si K == 0, ningún elemento puede reducirse más. Entonces, para tener una respuesta, todos los elementos de la array deben ser iguales. Entonces verificamos esto iterando un ciclo y si todos son iguales, la respuesta será n * val else print -1.
4.  Ahora, para el resto de los elementos, itere un bucle y compruebe si ((arr[i] – val) % K) == 0, es decir, arr[i] se puede reducir a val.
5.  Si la condición anterior falla para algún elemento, imprima -1.
6.  De lo contrario, si k == 1, la respuesta es n, es decir, todos los elementos se reducirán a 1.
7.  De lo contrario, la respuesta es n * (val % k).

A continuación se muestra el código para el enfoque anterior:

// C++ program of the above approach
 
#include <bits/stdc++.h>
 
using namespace std;
 
// function to calculate minimum sum after transformation
int min_sum(int n, int k, int a[])
{
    // Finding minimum element in the array
    int val=INT_MAX;
    for(int i=0;i<n;i++)
    {
        val=min(a[i],val);
    }
 
    if (val < 0)
        return -1;
 
    // no element can be reduced further
    if (k == 0) {
 
        // check if all the elements of the array
        // are identical or not
        for(int i=0;i<n;i++)
        {
            if(val!=a[i])
            return -1;
        }
            return (n * val);
    }
    else {
        int f = 0;
        for (int i = 0; i < n; i++) {
 
            int p = a[i] - val;
 
            // check if a[i] can be reduced to val
            if (p % k == 0)
                continue;
            else {
                f = 1;
                break;
            }
        }
 
        // one of the elements cannot be reduced
        // to be equal to the other elements
        if (f)
            return -1;
        else {
 
            // if k = 1 then all elements can be reduced to 1
            if (k == 1)
                return n;
            else
                return (n * (val % k));
        }
    }
}
 
// Driver code
int main()
{
    int arr[] = { 2, 3, 4, 5 };
    int K = 1;
    int N = sizeof(arr) / sizeof(arr[0]);
    cout << min_sum(N, K, arr);
 
    return 0;
}
 
// This code is contributed by Pushpesh raj

// Java program of above approach
import java.io.*;
import java.util.*;
 
class GFG{
      
static int min_sum(int n,int k,int[] a)
{
    // Finding minimum element in the array
    int val=Integer.MAX_VALUE;
    for(int i=0;i<n;i++)
    {
        val=Math.min(a[i],val);
    }
 
    if (val < 0)
        return -1;
 
    // no element can be reduced further
    if (k == 0) {
 
        // check if all the elements of the array
        // are identical or not
        for(int i=0;i<n;i++)
        {
            if(val!=a[i])
            return -1;
        }
            return (n * val);
    }
    else {
        int f = 0;
        for (int i = 0; i < n; i++) {
 
            int p = a[i] - val;
 
            // check if a[i] can be reduced to val
            if (p % k == 0)
                continue;
            else {
                f = 1;
                break;
            }
        }
 
        // one of the elements cannot be reduced
        // to be equal to the other elements
        if (f!=0)
            return -1;
        else {
 
            // if k = 1 then all elements can be reduced to 1
            if (k == 1)
                return n;
            else
                return (n * (val % k));
        }
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int[] arr = { 2, 3, 4, 5 };
    int K = 1;
    int N = arr.length;
 
    System.out.println(min_sum(N, K, arr));
}
}
  
// This code is contributed by aditya942003patil

4

Complejidad de tiempo: O(n)

 Espacio Auxiliar: O(1)