Dados dos enteros ‘X’ y ‘N’, la tarea es dividir el entero ‘X’ en exactamente ‘N’ partes tales que:
X1 + X2 + X3 + … + Xn = X y la diferencia entre el máximo y el mínimo número de la secuencia se minimiza.
Imprime la secuencia al final, si el número no se puede dividir exactamente en ‘N’ partes, imprime ‘-1’ en su lugar.
Ejemplos:
Entrada: X = 5, N = 3
Salida: 1 2 2
Dividir 5 en 3 partes de modo que la diferencia entre el número entero más grande y el más pequeño
sea la mínima posible. Entonces dividimos 5 como 1 + 2 + 2.Entrada: X = 25, N = 5
Salida: 5 5 5 5 5
Enfoque: siempre hay una forma de dividir el número si X >= N.
- Si el número se divide exactamente en ‘N’ partes, cada parte tendrá el valor X/N y la parte restante X%N se puede distribuir entre cualquier número X%N.
- Por lo tanto, si X % N == 0, la diferencia mínima siempre será ‘0’ y la secuencia contendrá todos los números iguales, es decir, x/n.
- De lo contrario, la diferencia será ‘1’ y la secuencia será X/N, X/N, …, (X/N)+1, (X/N)+1..
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP implementation of the approach
#include<bits/stdc++.h>
using namespace std;;
// Function that prints
// the required sequence
void split(int x, int n)
{
// If we cannot split the
// number into exactly 'N' parts
if(x < n)
cout<<"-1"<<" ";
// If x % n == 0 then the minimum
// difference is 0 and all
// numbers are x / n
else if (x % n == 0)
{
for(int i=0;i<n;i++)
cout<<(x/n)<<" ";
}
else
{
// upto n-(x % n) the values
// will be x / n
// after that the values
// will be x / n + 1
int zp = n - (x % n);
int pp = x/n;
for(int i=0;i<n;i++)
{
if(i>= zp)
cout<<(pp + 1)<<" ";
else
cout<<pp<<" ";
}
}
}
// Driver code
int main()
{
int x = 5;
int n = 3;
split(x, n);
}
//THis code is contributed
// Surendra_Gangwar
Java
// Java implementation of the approach
class GFG{
// Function that prints
// the required sequence
static void split(int x, int n)
{
// If we cannot split the
// number into exactly 'N' parts
if(x < n)
System.out.print("-1 ");
// If x % n == 0 then the minimum
// difference is 0 and all
// numbers are x / n
else if (x % n == 0)
{
for(int i=0;i<n;i++)
System.out.print((x/n)+" ");
}
else
{
// upto n-(x % n) the values
// will be x / n
// after that the values
// will be x / n + 1
int zp = n - (x % n);
int pp = x/n;
for(int i=0;i<n;i++)
{
if(i>= zp)
System.out.print((pp + 1)+" ");
else
System.out.print(pp+" ");
}
}
}
// Driver code
public static void main(String[] args)
{
int x = 5;
int n = 3;
split(x, n);
}
}
//This code is contributed by mits
Python3
# Python3 implementation of the approach # Function that prints # the required sequence def split(x, n): # If we cannot split the # number into exactly 'N' parts if(x < n): print(-1) # If x % n == 0 then the minimum # difference is 0 and all # numbers are x / n elif (x % n == 0): for i in range(n): print(x//n, end =" ") else: # upto n-(x % n) the values # will be x / n # after that the values # will be x / n + 1 zp = n - (x % n) pp = x//n for i in range(n): if(i>= zp): print(pp + 1, end =" ") else: print(pp, end =" ") # Driver code x = 5 n = 3 split(x, n)
C#
// C# implementation of the approach
using System;
public class GFG{
// Function that prints
// the required sequence
static void split(int x, int n)
{
// If we cannot split the
// number into exactly 'N' parts
if(x < n)
Console.WriteLine("-1 ");
// If x % n == 0 then the minimum
// difference is 0 and all
// numbers are x / n
else if (x % n == 0)
{
for(int i=0;i<n;i++)
Console.Write((x/n)+" ");
}
else
{
// upto n-(x % n) the values
// will be x / n
// after that the values
// will be x / n + 1
int zp = n - (x % n);
int pp = x/n;
for(int i=0;i<n;i++)
{
if(i>= zp)
Console.Write((pp + 1)+" ");
else
Console.Write(pp+" ");
}
}
}
// Driver code
static public void Main (){
int x = 5;
int n = 3;
split(x, n);
}
}
//This code is contributed by Sachin.
PHP
<?php
// PHP implementation of the approach
// Function that prints
// the required sequence
function split($x, $n)
{
// If we cannot split the
// number into exactly 'N' parts
if($x < $n)
echo (-1);
// If x % n == 0 then the minimum
// difference is 0 and all
// numbers are x / n
else if ($x % $n == 0)
{
for($i = 0; $i < $n; $i++)
{
echo ($x / $n);
echo (" ");
}
}
else
{
// upto n-(x % n) the values
// will be x / n
// after that the values
// will be x / n + 1
$zp = $n - ($x % $n);
$pp = $x / $n;
for ($i = 0; $i < $n; $i++)
{
if($i >= $zp)
{
echo (int)$pp + 1;
echo (" ");
}
else
{
echo (int)$pp;
echo (" ");
}
}
}
}
// Driver code
$x = 5;
$n = 3;
split( $x, $n);
// This code is contributed
// by Shivi_Aggarwal
?>
Javascript
<script>
// JavaScript implementation of the above approach
// Function that prints
// the required sequence
function split(x, n)
{
// If we cannot split the
// number into exactly 'N' parts
if(x < n)
document.write("-1 ");
// If x % n == 0 then the minimum
// difference is 0 and all
// numbers are x / n
else if (x % n == 0)
{
for(let i=0;i<n;i++)
document.write((x/n)+" ");
}
else
{
// upto n-(x % n) the values
// will be x / n
// after that the values
// will be x / n + 1
let zp = n - (x % n);
let pp = Math.floor(x/n);
for(let i=0;i<n;i++)
{
if(i>= zp)
document.write((pp + 1)+" ");
else
document.write(pp+" ");
}
}
}
// driver code
let x = 5;
let n = 3;
split(x, n);
</script>
Producción:
1 2 2
Complejidad temporal: O(n)
Espacio auxiliar: O(1)