Haga que la suma de todos los subarreglos de longitud K sea igual simplemente insertando elementos

Dada una array arr[] de longitud N tal que (1 <= arr[i] <= N), la tarea es modificar la array, solo insertando elementos dentro del rango [1, N] , tal que la suma de todos los subarreglos de longitud K se vuelven iguales. Imprima la array modificada, si es posible. De lo contrario, escriba «No es posible».
Ejemplos: 
 

Entrada: arr[] = {1, 2, 2, 1}, K = 2 
Salida: 1 2 1 2 1 
Explicación: 
Inserte 1 entre el segundo y el tercer elemento. 
Ahora todo subarreglo de longitud K tiene una suma igual a 3.
Entrada: arr[] = {1, 2, 3, 4}, K = 3 
Salida: No es posible

Acercarse:

• Dado que no se permite la eliminación de elementos, el único caso en el que se puede lograr dicha array modificada es cuando hay como máximo K elementos distintos en la array.
• Por lo tanto, primero verifique si hay más de K elementos distintos en la array dada. En caso afirmativo, escriba «No es posible».
• De lo contrario, almacene todos los elementos distintos de la array dada en un vector .
• Si el número de elementos distintos es menor que K, agregue/repita algunos elementos en el vector y haga que el tamaño del vector sea igual a K.
• El vector tiene ahora K elementos. Ahora repita los elementos del vector en el mismo orden para mostrar la array modificada. Esta repetición se realiza para mostrar que todos los subarreglos de longitud K tienen la misma suma.

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

// C++ implementation of above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function that prints another array
// whose all subarray of length k
// have an equal sum
void MakeArray(int a[], int n, int k)
{
    unordered_map<int, int> mp;
 
    // Store all distinct elements in
    // the unordered map
    for (int i = 0; i < n; i++) {
        if (mp.find(a[i]) == mp.end())
            mp[a[i]] = 1;
    }
 
    // Condition if the number of
    // distinct elements is greater
    // than k
    if (mp.size() > k) {
        cout << "Not possible\n";
        return;
    }
 
    vector<int> ans;
 
    // Push all distinct elements
    // in a vector
    for (auto i : mp) {
        ans.push_back(i.first);
    }
 
    // Push 1 while the size of
    // vector not equal to k
    while (ans.size() < k) {
        ans.push_back(1);
    }
 
    // Print the vector 2 times
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < k; j++)
            cout << ans[j] << " ";
    }
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 2, 1 };
    int K = 2;
    int size = sizeof(arr) / sizeof(arr[0]);
 
    MakeArray(arr, size, K);
 
    return 0;
}

// Java implementation of above approach
import java.util.*;
class GFG{
   
// Function that prints another array
// whose all subarray of length k
// have an equal sum
static void MakeArray(int a[], int n, int k)
{
    HashMap<Integer,
              Integer> mp = new HashMap<Integer,
                                        Integer>();
   
    // Store all distinct elements in
    // the unordered map
    for (int i = 0; i < n; i++)
    {
        if (!mp.containsKey(a[i]))
            mp.put(a[i], 1);
    }
   
    // Condition if the number of
    // distinct elements is greater
    // than k
    if (mp.size() > k)
    {
        System.out.print("Not possible\n");
        return;
    }
   
    Vector<Integer> ans = new Vector<Integer>();
   
    // Push all distinct elements
    // in a vector
    for (Map.Entry<Integer,Integer> i : mp.entrySet())
    {
        ans.add(i.getKey());
    }
   
    // Push 1 while the size of
    // vector not equal to k
    while (ans.size() < k)
    {
        ans.add(1);
    }
   
    // Print the vector 2 times
    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < k; j++)
            System.out.print(ans.get(j) + " ");
    }
}
   
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 1, 2, 2, 1 };
    int K = 2;
    int size = arr.length;
   
    MakeArray(arr, size, K);
}
}
  
// This code is contributed by Rohit_ranjan

# Python3 implementation of above approach
 
# Function that prints another array
# whose all subarray of length k
# have an equal sum
def MakeArray(a, n, k):
    mp = dict()
 
    # Store all distinct elements in
    # the unordered map
    for i in a:
        if i not in mp:
            mp[a[i]] = 1
 
    # Condition if the number of
    # distinct elements is greater
    # than k
    if(len(mp) > k):
       print("Not possible")
       return
 
    ans = []
 
    # Push all distinct elements
    # in a vector
    for i in mp:
        ans.append(i)
 
    # Push 1 while the size of
    # vector not equal to k
    while(len(ans) < k):
          ans.append(1)
 
    # Print the vector 2 times
    for i in range(2):
        for j in range(k):
            print(ans[j], end = " ")
 
# Driver Code
if __name__ == '__main__':
     
    arr = [ 1, 2, 2, 1 ]
    K = 2
    size = len(arr)
     
    MakeArray(arr, size, K)
     
# This code is contributed by mohit kumar 29

// C# implementation of above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function that prints another array
// whose all subarray of length k
// have an equal sum
static void MakeArray(int []a, int n, int k)
{
    Dictionary<int,
               int> mp = new Dictionary<int,
                                        int>();
 
    // Store all distinct elements in
    // the unordered map
    for(int i = 0; i < n; i++)
    {
        if (!mp.ContainsKey(a[i]))
             mp.Add(a[i], 1);
    }
 
    // Condition if the number of
    // distinct elements is greater
    // than k
    if (mp.Count > k)
    {
        Console.Write("Not possible\n");
        return;
    }
 
    List<int> ans = new List<int>();
 
    // Push all distinct elements
    // in a vector
    foreach(KeyValuePair<int, int> i in mp)
    {
        ans.Add(i.Key);
    }
 
    // Push 1 while the size of
    // vector not equal to k
    while (ans.Count < k)
    {
        ans.Add(1);
    }
 
    // Print the vector 2 times
    for(int i = 0; i < 2; i++)
    {
        for(int j = 0; j < k; j++)
            Console.Write(ans[j] + " ");
    }
}
 
// Driver Code
public static void Main(String[] args)
{
    int []arr = { 1, 2, 2, 1 };
    int K = 2;
    int size = arr.Length;
 
    MakeArray(arr, size, K);
}
}
 
// This code is contributed by amal kumar choubey

<script>
 
// Javascript implementation of above approach
 
// Function that prints another array
// whose all subarray of length k
// have an equal sum
function MakeArray(a, n, k)
{
    var mp = new Map();
 
    // Store all distinct elements in
    // the unordered map
    for (var i = 0; i < n; i++) {
        if (!mp.has(a[i]))
            mp.set(a[i], 1);
    }
 
    // Condition if the number of
    // distinct elements is greater
    // than k
    if (mp.count > k) {
        document.write( "Not possible<br>");
        return;
    }
 
    var ans = [];
 
    // Push all distinct elements
    // in a vector
    mp.forEach((value, key) => {
        ans.push(key);
    });
      
 
    // Push 1 while the size of
    // vector not equal to k
    while (ans.length < k) {
        ans.push(1);
    }
 
    // Print the vector 2 times
    for (var i = 0; i < 2; i++) {
        for (var j = 0; j < k; j++)
            document.write( ans[j] + " ");
    }
}
 
// Driver Code
var arr = [1, 2, 2, 1];
var K = 2;
var size = arr.length;
MakeArray(arr, size, K);
 
// This code is contributed by rutvik_56.
</script>

2 1 2 1