Construya una array de elementos distintos con el tamaño, la suma y el límite superior del elemento dados

Posted on by Rudeus Greyrat

Dado el tamaño N de la array original, SUM suma total de todos los elementos presentes en la array y K tal que ningún elemento en la array es mayor que K, construya la array original donde todos los elementos de la array son únicos. Si no hay solución, imprima “No es posible”. 

Nota: Todos los elementos deben ser positivos.

Ejemplos: 

Input : N = 3, SUM = 15, K = 8  
Output: array[] = {1, 6, 8} 
The constructed array has size 3, sum
15 and all elements are smaller than
or equal to 8.

Input : N = 2,  SUM = 9, K = 10  
Output: array[]={1, 8} 

Input  : N = 3, SUM = 23, K = 8  
Output : Not Possible

Debemos elegir N elementos y todos los elementos deben ser positivos y ningún elemento debe ser mayor que K. Dado que los elementos son positivos y distintos, la suma más pequeña posible es igual a la suma de los primeros N números naturales, que es N * (N + 1)/2 . 

Dado que todos los elementos deben ser menores o iguales que K, la mayor suma posible es K + (K-1) + (K-2) + ….. + (K-N+1) = (N*K)- (N *(N-1))/2.
Entonces, si la suma dada está entre la suma más pequeña y la más grande posible, solo se puede formar la array, o de lo contrario tenemos que imprimir -1.

A continuación se muestra el algoritmo completo si es factible construir la array.

  1. Cree una array de tamaño N y llénela con los primeros N números. Entonces, la suma total de la array será la suma más pequeña posible. 
  2. Encuentre el elemento más grande de la array, pero a medida que la array está ordenada, la array [N] será la más grande. 
    • Si el elemento más grande es menor que K, lo reemplazamos con K y verificamos la nueva suma de la array. 
      • Si es menor que la SUMA dada, nos movemos a la posición N-1 en la array porque la array [N] no se puede incrementar más y para mantener la unicidad disminuimos K en 1.
      • Si es mayor que SUM dado, reemplazamos un elemento tal que sum se dará SUM y saldrá del bucle.
    • Si el elemento más grande es igual a K, nos movemos a la posición N-1 en la array porque la array [N] no se puede incrementar más y para mantener la unicidad disminuiremos K en 1.
  3. Imprime la array. 

Implementación:

C++

// CPP program to construct a distinct element
// array with given size, sum, element upper
// bound and all elements positive
#include <bits/stdc++.h>
using namespace std;
 
void printArray(int N, int SUM, int K)
{
    // smallest possible sum
    int minSum = (N * (N + 1)) / 2;
 
    // largest possible sum
    int maxSum = (N * K) - (N * (N - 1)) / 2;
 
    if (minSum > SUM || maxSum < SUM) {
        printf("Not Possible");
        return;
    }
 
    // Creating array with minimum possible
    // sum.
    int arr[N + 1];
    for (int i = 1; i <= N; i++)
        arr[i] = i;
    int sum = minSum;
 
    // running the loop from last because the
    // array is sorted and running from last
    // will give largest numbers
    for (int i = N; i >= 1; i--) {
 
        // replacing i with K, Note arr[i] = i
        int x = sum + (K - i);
        if (x < SUM) {
            sum = sum + (K - i);
            arr[i] = K; // can't be incremented further
            K--; // to maintain uniqueness
        }
 
        else {
 
            // directly replacing with a suitable
            // element to make sum as given sum
            arr[i] += (SUM - sum);
            sum = SUM;
            break;
        }
    }
 
    for (int i = 1; i <= N; i++)
        cout << arr[i] << " ";
}
 
// Driver code
int main()
{
    int N = 3, SUM = 15, K = 8;
    printArray(N, SUM, K);
    return 0;
}

Java

// Java program to construct a distinct element
// array with given size, sum, element upper
// bound and all elements positive
 
import java.io.*;
 
class GFG {
    static void printArray(int N, int SUM, int K)
    {
        // smallest possible sum
        int minSum = (N * (N + 1)) / 2;
 
        // largest possible sum
        int maxSum = (N * K) - (N * (N - 1)) / 2;
 
        if (minSum > SUM || maxSum < SUM) {
            System.out.println("Not Possible");
            return;
        }
 
        // Creating array with
        // minimum possible sum.
        int arr[] = new int[N + 1];
        for (int i = 1; i <= N; i++)
            arr[i] = i;
 
        int sum = minSum;
 
        // running the loop from last because the
        // array is sorted and running from last
        // will give largest numbers
        for (int i = N; i >= 1; i--) {
 
            // replacing i with K, Note arr[i] = i
            int x = sum + (K - i);
            if (x < SUM) {
                sum = sum + (K - i);
 
                // can't be incremented further
                arr[i] = K;
 
                // to maintain uniqueness
                K--;
            }
 
            else {
 
                // directly replacing with a suitable
                // element to make sum as given sum
                arr[i] += (SUM - sum);
                sum = SUM;
                break;
            }
        }
 
        for (int i = 1; i <= N; i++)
            System.out.print(arr[i] + " ");
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int N = 3, SUM = 15, K = 8;
        printArray(N, SUM, K);
    }
}
 
// This code is contributed by vt_m

Python3

# Python 3 program to construct a distinct
# element array with given size, sum,
# element upper bound and all elements
# positive
def printArray(N, SUM, K):
     
    # smallest possible sum
    minSum = (N * (N + 1)) / 2
 
    # largest possible sum
    maxSum = (N * K) - (N * (N - 1)) / 2
 
    if (minSum > SUM or maxSum < SUM):
        print("Not Possible")
        return
     
    # Creating array with minimum
    # possible sum.
    arr = [0 for i in range(N + 1)]
    for i in range(1, N + 1, 1):
        arr[i] = i
    sum = minSum
 
    # running the loop from last because
    # the array is sorted and running
    # from last will give largest numbers
    i = N
    while(i >= 1):
         
        # replacing i with K, Note arr[i] = i
        x = sum + (K - i)
        if (x < SUM):
            sum = sum + (K - i)
            arr[i] = K
             
            # can't be incremented further
            K -= 1
             
            # to maintain uniqueness
        else:
             
            # directly replacing with a suitable
            # element to make sum as given sum
            arr[i] += (SUM - sum)
            sum = SUM
            break
        i -= 1
 
    for i in range(1, N + 1, 1):
        print(int(arr[i]), end = " ")
 
# Driver code
if __name__ == '__main__':
    N = 3
    SUM = 15
    K = 8
    printArray(N, SUM, K)
 
# This code is contributed by
# Surendra_Gangwar

C#

// C# program to construct a distinct element
// array with given size, sum, element upper
// bound and all elements positive
using System;
 
class GFG {
     
    static void printArray(int N, int SUM, int K)
    {
         
        // smallest possible sum
        int minSum = (N * (N + 1)) / 2;
 
        // largest possible sum
        int maxSum = (N * K) - (N * (N - 1)) / 2;
 
        if (minSum > SUM || maxSum < SUM) {
            Console.WriteLine("Not Possible");
            return;
        }
 
        // Creating array with
        // minimum possible sum.
        int[] arr = new int[N + 1];
        for (int i = 1; i <= N; i++)
            arr[i] = i;
 
        int sum = minSum;
 
        // running the loop from last because the
        // array is sorted and running from last
        // will give largest numbers
        for (int i = N; i >= 1; i--) {
 
            // replacing i with K, Note arr[i] = i
            int x = sum + (K - i);
         
             
            if (x < SUM) {
                sum = sum + (K - i);
 
                // can't be incremented further
                arr[i] = K;
 
                // to maintain uniqueness
                K--;
            }
 
            else {
 
                // directly replacing with a suitable
                // element to make sum as given sum
                arr[i] += (SUM - sum);
                sum = SUM;
                break;
            }
        }
 
        for (int i = 1; i <= N; i++)
            Console.Write(arr[i] + " ");
    }
 
    // Driver code
    public static void Main()
    {
         
        int N = 3, SUM = 15, K = 8;
         
        printArray(N, SUM, K);
    }
}
 
// This code is contributed by vt_m.

PHP

<?php
// PHP program to construct a distinct element
// array with given size, sum, element upper
// bound and all elements positive
 
 
function printArray($N, $SUM, $K)
{
    // smallest possible sum
    $minSum = ($N * ($N + 1)) / 2;
 
    // largest possible sum
    $maxSum = ($N * $K) - ($N * ($N - 1)) / 2;
 
    if ($minSum > $SUM || $maxSum < $SUM) {
        echo"Not Possible";
        return;
    }
 
    // Creating array with minimum possible
    // sum.
     $arr = array();
    for ($i = 1; $i <= $N; $i++)
        $arr[$i] = $i;
      $sum = $minSum;
 
    // running the loop from last because the
    // array is sorted and running from last
    // will give largest numbers
    for ($i = $N; $i >= 1; $i--) {
 
        // replacing i with K, Note arr[i] = i
        $x = $sum + ($K - $i);
        if ($x <$SUM) {
            $sum = $sum + ($K - $i);
            $arr[$i] =$K; // can't be incremented further
            $K--; // to maintain uniqueness
        }
 
        else {
 
            // directly replacing with a suitable
            // element to make sum as given sum
            $arr[$i] += ($SUM - $sum);
            $sum = $SUM;
            break;
        }
    }
 
    for ($i = 1; $i <= $N; $i++)
        echo $arr[$i] , " ";
}
 
// Driver code
    $N = 3; $SUM = 15;$K = 8;
    printArray($N, $SUM, $K);
// This code is contributed by inder_verma..
 
?>

Javascript

<script>
// JavaScript program to construct a distinct element
// array with given size, sum, element upper
// bound and all elements positive
 
function printArray(N, SUM, K)
{
    // smallest possible sum
    let minSum = Math.floor((N * (N + 1)) / 2);
 
    // largest possible sum
    let maxSum = (N * K) - Math.floor((N * (N - 1)) / 2);
 
    if (minSum > SUM || maxSum < SUM) {
        document.write("Not Possible");
        return;
    }
 
    // Creating array with minimum possible
    // sum.
    let arr = new Array(N + 1);
    for (let i = 1; i <= N; i++)
        arr[i] = i;
    let sum = minSum;
 
    // running the loop from last because the
    // array is sorted and running from last
    // will give largest numbers
    for (let i = N; i >= 1; i--) {
 
        // replacing i with K, Note arr[i] = i
        let x = sum + (K - i);
        if (x < SUM) {
            sum = sum + (K - i);
            arr[i] = K; // can't be incremented further
            K--; // to maintain uniqueness
        }
 
        else {
 
            // directly replacing with a suitable
            // element to make sum as given sum
            arr[i] += (SUM - sum);
            sum = SUM;
            break;
        }
    }
 
    for (let i = 1; i <= N; i++)
        document.write(arr[i] + " ");
}
 
// Driver code
    let N = 3, SUM = 15, K = 8;
    printArray(N, SUM, K);
 
// This code is contributed by Surbhi Tyagi.
</script>

Producción: 

1 6 8

Complejidad de tiempo : O(N)

Publicación traducida automáticamente

Artículo escrito por Bibhu Pala 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 *