Horje
Maximum Sum of Array with given MEX

Given 3 integers N, K, and X, the task is to construct an array arr[] with the below conditions:

  • Size of the array = N
  • MEX of the array = K
  • All array elements should be at most X

Among all the array that follows the above condition print the one having the maximum sum of its elements or print -1 if no such array exists.

Constraints:

  • 1<= N <= 100000
  • 1<= K <= 100000
  • 1<= X <= 100000

Examples:

Input: N=5, K=3, X=3
Output: [0, 1, 2, 2, 2]
Explanation: The MEX of the above array is 3, and sum of its element is 7, it is guaranteed that we cannot create an array having sum greater than 7

Input: N=4, K=7, X=5
Output: -1
Explanation: No valid array exists

Approach: The problem can be solved using the following approach:

Case 1: If min(N, X+1) < K, then answer does not exists i.e. answer = -1.
Reason:

  • If N < K, then the maximum value of MEX that can be created using N numbers is equal to N. For example, if N=4, then arr[] = [0, 1, 2, 3] gives MEX = 4. Therefore, if N<K we cannot achieve MEX = K
  • If X+1 < K, then also it would be impossible to achieve MEX = K due to the fact that for MEX = K, K – 1 should be present in the array, but X is the maximum number present in the array.

Case 2: If answer exists, and we want to maximize it.

Since we have to form MEX=K therefore it is necessary for all the elements from 0 to K-1 to appear at least once in the array. Now since our task is to maximize the sum, all the elements form 0 to K-1 should occur exactly once all the remaining elements will depend upon the value of X i.e.

  • If X = K, then all the remaining values should be K-1 so that MEX = K is preserved
  • If X ≠ K, then all the remaining values should be X.

Steps to solve the problem:

  • If N < K or X + 1 < K, then the answer does not exist, so print -1.
  • Else, since we want the MEX to be equal to K so push all the numbers from 0 to K-1 into our answer.
  • After pushing number from 0 to K-1, check if we can push X as all the remaining elements.
    • If yes, then push all the remaining elements as X.
    • Else, push all the remaining elements as X – 1.
  • Finally, print the answer array.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>
#define ll long long
using namespace std;
void resultArray(ll N, ll K, ll X)
{
    // case when answer does not exist
    if (N < K || X + 1 < K) {
        cout << -1 << endl;
        return;
    }
 
    // vector to store the answer
    vector<ll> ans;
    // Push all the numbers less than K into
    // the answer, to get MEX = K
    for (ll i = 0; i < K; i++) {
        ans.push_back(i);
    }
 
    // If MEX is equal to maximum element allowed, then fill
    // the remaining positions with second maximum element
    if (X == K) {
        for (int i = K; i < N; i++) {
            ans.push_back(K - 1);
        }
    }
    // Else fill the remaining positions with the maximum
    // element allowed
    else {
        for (int i = K; i < N; i++) {
            ans.push_back(X);
        }
    }
    for (int i = 0; i < N; i++)
        cout << ans[i] << " ";
    cout << "\n";
}
int main()
{
    // taking input
    ll N = 5, K = 3, X = 3;
 
    resultArray(N, K, X);
}

Java

import java.util.*;
 
class GFG {
    // Function to generate the result array
    static void resultArray(long N, long K, long X) {
        // Case when the answer does not exist
        if (N < K || X + 1 < K) {
            System.out.println("-1");
            return;
        }
        // List to store the answer
        List<Long> ans = new ArrayList<>();
        // Push all the numbers less than K into
        // the answer to get MEX = K
        for (long i = 0; i < K; i++) {
            ans.add(i);
        }
        if (X == K) {
            for (long i = K; i < N; i++) {
                ans.add(K - 1);
            }
        }
        // Else fill the remaining positions with
        // the maximum element allowed
        else {
            for (long i = K; i < N; i++) {
                ans.add(X);
            }
        }
        // Print the result array
        for (Long num : ans) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
 
    public static void main(String[] args) {
        // Example input values
        long N = 5, K = 3, X = 3;
        resultArray(N, K, X);
    }
}

Python3

def GFG(N, K, X):
    # Case when the answer does not exist
    if N < K or X + 1 < K:
        print("-1")
        return
     
    # Array to store the result
    ans = []
     
    # Push all the numbers less than K into answer to get MEX = K
    for i in range(K):
        ans.append(i)
     
    if X == K:
        for i in range(K, N):
            ans.append(K - 1)
    else:
        # Else fill the remaining positions with the maximum element allowed
        for i in range(K, N):
            ans.append(X)
     
    # Print the result array
    print(' '.join(map(str, ans)))
 
# input values
N, K, X = 5, 3, 3
GFG(N, K, X)

C#

using System;
using System.Collections.Generic;
 
class GFG
{
    // Function to generate the result array
    static void ResultArray(long N, long K, long X)
    {
        // Case when the answer does not exist
        if (N < K || X + 1 < K)
        {
            Console.WriteLine("-1");
            return;
        }
        // List to store the answer
        List<long> ans = new List<long>();
        // Push all the numbers less than K into
      // the answer to get MEX = K
        for (long i = 0; i < K; i++)
        {
            ans.Add(i);
        }
        if (X == K)
        {
            for (long i = K; i < N; i++)
            {
                ans.Add(K - 1);
            }
        }
        // Else fill the remaining positions with
       // the maximum element allowed
        else
        {
            for (long i = K; i < N; i++)
            {
                ans.Add(X);
            }
        }
        // Print the result array
        foreach (var num in ans)
        {
            Console.Write(num + " ");
        }
        Console.WriteLine();
    }
    static void Main()
    {
        // Example input values
        long N = 5, K = 3, X = 3;
        ResultArray(N, K, X);
    }
}

Javascript

function GFG(N, K, X) {
    // Case when the answer does not exist
    if (N < K || X + 1 < K) {
        console.log("-1");
        return;
    }
    // Array to store the result
    const ans = [];
    // Push all the numbers less than K into answer to get MEX = K
    for (let i = 0; i < K; i++) {
        ans.push(i);
    }
    if (X === K) {
        for (let i = K; i < N; i++) {
            ans.push(K - 1);
        }
    }
    // Else fill the remaining positions with maximum element allowed
    else {
        for (let i = K; i < N; i++) {
            ans.push(X);
        }
    }
    // Print the result array
    console.log(ans.join(' '));
}
// input values
const N = 5, K = 3, X = 3;
GFG(N, K, X);

Output

0 1 2 2 2

Time Complexity: O(N)
Auxiliary Space: O(N), where N is the size of array. 




Reffered: https://www.geeksforgeeks.org

Arrays

Related
Minimum cost to buy all items at least once Minimum cost to buy all items at least once
Optimal Placement of People in Circular Locations Optimal Placement of People in Circular Locations
Minimum Operations to Sort Array with Custom Shuffling Minimum Operations to Sort Array with Custom Shuffling
Maximizing Toy Purchases with Budget Constraints and Broken Toys Maximizing Toy Purchases with Budget Constraints and Broken Toys
Generate Lexicographically Largest Array through Even Swaps Generate Lexicographically Largest Array through Even Swaps

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 13



 

Horje