Partición de N en M partes de modo que la diferencia entre la parte Max y Min sea la más pequeña

Dados dos números enteros N y M , dividir N en M números enteros de manera que la diferencia entre el número entero máximo y mínimo obtenido por la partición sea lo más pequeña posible. 

Imprime los números M A1, A2….Am , tal que: 

• suma(A) = N.
• max(A)-min(A) se minimiza.

Ejemplos :  

Input : N = 11, M = 3
Output : A[] = {4, 4, 3}

Input : N = 8, M = 4
Output : A[] = {2, 2, 2, 2}

Para minimizar la diferencia entre los términos, debemos tenerlos lo más cerca posible entre sí. Digamos que podríamos imprimir cualquier valor flotante en lugar de números enteros, la respuesta en ese caso sería 0 (imprimir N/MM veces). Pero como necesitamos imprimir números enteros, podemos dividirlo en 2 partes, piso (N/M) y piso (N/M) + 1, lo que nos daría la respuesta como máximo 1. 
¿Cuántos términos necesitamos imprimir de ¿cada tipo? 
Digamos que imprimimos floor(N/M) M veces, la suma sería igual a N – (N%M) . Entonces, debemos elegir N%M términos y aumentarlos en 1.

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

// C++ program to partition N into M parts
// such that difference Max and Min
// part is smallest
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to partition N into M parts such
// that difference Max and Min part
// is smallest
void printPartition(int n, int m)
{
    int k = n / m; // Minimum value
 
    int ct = n % m; // Number of (K+1) terms
 
    int i;
 
    for (i = 1; i <= ct; i++)
        cout << k + 1 << " ";
 
    for (; i <= m; i++)
        cout << k << " ";
}
 
// Driver Code
int main()
{
    int n = 5, m = 2;
 
    printPartition(n, m);
 
    return 0;
}

// Java program to partition N into M parts
// such that difference Max and Min
// part is smallest
 
import java.io.*;
 
class GFG {
 
 
// Function to partition N into M parts such
// that difference Max and Min part
// is smallest
static void printPartition(int n, int m)
{
    int k = n / m; // Minimum value
 
    int ct = n % m; // Number of (K+1) terms
 
    int i;
 
    for (i = 1; i <= ct; i++)
        System.out.print( k + 1 + " ");
 
    for (; i <= m; i++)
        System.out.print( k + " ");
}
 
// Driver Code
 
    public static void main (String[] args) {
    int n = 5, m = 2;
 
    printPartition(n, m);
    }
}
// This code is contributed by anuj_67..

# Python 3 program to partition N into M parts
# such that difference Max and Min
# part is the smallest
 
# Function to partition N into M parts such
# that difference Max and Min part
# is smallest
def printPartition(n, m):
    k = int(n / m)
    # Minimum value
 
    ct = n % m
    # Number of (K+1) terms
 
    for i in range(1,ct+1,1):
        print(k + 1,end= " ")
    count = i
    for i in range(count,m,1):
        print(k,end=" ")
 
# Driver Code
if __name__ == '__main__':
    n = 5
    m = 2
    printPartition(n, m)
 
# This code is contributed by
# Surendra_Gangwar

// C# program to partition N into M parts
// such that difference Max and Min
// part is smallest
using System;
 
class GFG
{
static void printPartition(int n, int m)
{
    int k = n / m; // Minimum value
 
    int ct = n % m; // Number of (K+1) terms
 
    int i;
 
    for (i = 1; i <= ct; i++)
        Console.Write( k + 1 + " ");
 
    for (; i <= m; i++)
        Console.Write( k + " ");
}
 
// Driver Code
static public void Main ()
{
    int n = 5, m = 2;
 
    printPartition(n, m);
}
}
 
// This code is contributed by Sachin

<?php
// PHP program to partition N into
// M parts such that difference
// Max and Min part is smallest
 
// Function to partition N into M
// parts such that difference Max
// and Min part is smallest
function printPartition($n, $m)
{
    $k = (int)($n / $m); // Minimum value
 
    $ct = $n % $m; // Number of (K+1) terms
 
    for ($i = 1; $i <= $ct; $i++)
        echo $k + 1 . " ";
 
    for (; $i <= $m; $i++)
        echo $k . " ";
}
 
// Driver Code
$n = 5; $m = 2;
 
printPartition($n, $m);
 
// This code is contributed
// by Akanksha Rai
?>

<script>
 
// Javascript program to partition N into M parts
// such that difference Max and Min
// part is smallest
 
// Function to partition N into M parts such
// that difference Max and Min part
// is smallest
function prletPartition(n, m)
{
    let k = Math.floor(n / m); // Minimum value
 
    let ct = n % m; // Number of (K+1) terms
 
    let i;
 
    for (i = 1; i <= ct; i++)
        document.write( k + 1 + " ");
 
    for (; i <= m; i++)
        document.write( k + " ");
}
 
 
// driver program
     
    let n = 5, m = 2;
 
    prletPartition(n, m);
    
</script>

3 2

Complejidad temporal: O(n + m), donde n y m son los valores de los números enteros dados.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.