Make sum of all subarrays of length K equal by only inserting elements

0 0 5 minutes read

Given an array arr[] of length N such that (1 <= arr[i] <= N), the task is to modify the array, by only inserting elements within the range [1, N], such that the sum of all subarrays of length K become equal. Print the modified array, if possible. Else print “Not possible”.
Examples:

Input: arr[] = {1, 2, 2, 1}, K = 2
Output: 1 2 1 2 1
Explanation:
Insert 1 between second and third element.
Now all subarray of length K has an equal sum of 3.
Input: arr[] = {1, 2, 3, 4}, K = 3
Output: Not possible

Approach:

Since the removal of elements is not allowed, therefore the only case when such a modified array can be achieved, is when there are at most K distinct elements in the array.
Therefore, Firstly check if there are more than K distinct elements in the given array. If yes, then print “Not possible”.
Else, store all the distinct elements of the given array in a vector.
If the number of distinct elements is less than K, then add/repeat some elements in the vector and make the size of the vector equal to K.
The vector has now K elements. Now repeat the elements of the vector in the same order to show the modified array. This repetition is done to show all the subarrays of length K have the same sum.

Below is the implementation of the above approach

C++

// 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

// 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

# 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#

// 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

Javascript

<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>

Output:

2 1 2 1

Time Complexity: O(N), where N is the size of the given array.
Auxiliary Space: O(N), in order to store elements in HashMap.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!