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 sumvoid 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 Codeint 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 approachimport java.util.*;class GFG{ // Function that prints another array// whose all subarray of length k// have an equal sumstatic 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 Codepublic 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 sumdef 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 Codeif __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 approachusing System;using System.Collections.Generic;class GFG{// Function that prints another array// whose all subarray of length k// have an equal sumstatic 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 Codepublic 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 sumfunction 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 Codevar 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
