Haz que todos los elementos de la array sean divisibles por un número K

Dada una array arr[] y un número K , la tarea es hacer que todos los elementos de la array sean divisibles por K. Para hacer que los elementos sean divisibles por K, se puede realizar la siguiente operación: 
 

• Elija cualquier índice C en la array.
• Puede restar cualquier valor de cualquiera de los números hasta el índice C y puede agregar cualquier valor a cualquiera de los elementos presentes después del índice C.
• La única condición requerida para la operación anterior es que la suma total de los valores restados hasta el índice C se puede agregar a los elementos después del índice C.

Imprima el valor del índice C y la diferencia de los números restados a los números agregados después del índice C.
Ejemplos:
 

Entrada: arr[] = {1, 14, 4, 41, 1}, K = 7 
Salida: C = 3, diferencia = 5 
Explicación: 
consulte la explicación a continuación.
Entrada: arr[] = {1, 10, 19}, K=9 
Salida: C = 2, diferencia = 2 
 

Explicación: 
 

Acercarse: 
 

• Cree dos arrays auxiliares arr1[] y arr2[].
• La primera array arr1[] almacena el valor del elemento que se puede restar de cada elemento para hacerlo divisible por K en arr[].
• La segunda array arr2[] almacena el valor del elemento que se puede agregar para hacer que el elemento sea divisible por K.
• Luego itere sobre los valores posibles para C y encuentre el índice en el que la suma de los valores restados desde arr1[] hasta ese índice es mayor o igual que la suma de los valores agregados al índice después de C en arr2[].

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

// C++ implementation to make
// the array elements divisible by K
#include <bits/stdc++.h>
using namespace std;
 
// Function to make array divisible
pair<int,int> makeDivisble(int arr[], int n, int k)
{
     
    vector<int>b1;
    vector<int>b2;
    int c, suml, sumr, index, rem;
     
    // For each element of array
    // how much number to be subtracted
    // to make it divisible by k
    for (int i = 0; i < n; i++)
        b1.push_back(arr[i] % k);
     
    // For each element of array
    // how much number to be added
    // to make it divisible by K
    for (int j = 0; j < n; j++)
        if ((arr[j] % k) != 0)
            b2.push_back(k - (arr[j] % k));
        else
            b2.push_back(0);
             
    c = 0;
    float mini = INT_MAX;
    suml = 0;
    sumr = 0;
    index = -1;
     
    // Calculate minimum difference
    for (int c = 0; c < n; c++)
    {
        suml = accumulate(b1.begin(),b1.begin() + c + 1, 0);
        sumr = accumulate(b2.begin() + c + 1 , b2.end(), 0);
        if (suml >= sumr)
        {
            rem = suml - sumr;
            if (rem < mini)
            {
                mini = rem;
                index = c;
            }
        }
    }
     
    return make_pair(index, mini);
 
}
 
// Driver Code
int main() {
    int arr[] = {1, 14, 4, 41, 1};
    int k = 7;
    int n=sizeof(arr)/sizeof(arr[0]);
     
    pair<int ,int>ans;
    ans = makeDivisble(arr, n, k);
    cout << ans.first << " " << ans.second;
     
    return 0;
}
 
// This code is contributed by Atul_kumar_Shrivastava

# Python implementation to make
# the array elements divisible by K
 
# Function to make array divisible
def makeDivisble(arr, k):
    n = len(arr)
    b1 =[]
    b2 =[]
     
    # For each element of array
    # how much number to be subtracted
    # to make it divisible by k
    for i in range (n):
        b1.append(arr[i]% k)
     
    # For each element of array
    # how much number to be added
    # to make it divisible by K
    for j in range(n):
        if ((arr[j]% k)!= 0):
            b2.append(k-(arr[j]% k))
        else:
            b2.append(0)
    c = 0
    mini = float('inf')
    suml = 0
    sumr = 0
    index = -1
     
    # Calculate minimum difference
    for c in range(0, n+1, 1):
        suml = sum(b1[ : c + 1])
        sumr = sum(b2)
        if suml>= sumr:
            rem = suml-sumr
            if rem<mini:
                mini = rem
                index = c
    return index, mini
 
# Driver Code
if __name__ == "__main__":
    arr = [1, 14, 4, 41, 1]
    k = 7
    index, diff = makeDivisble(arr, k)
    print(index, diff)

3 5

Complejidad de tiempo: O(N^2)
Espacio auxiliar : O(N)