Maximize the equal numbers in the Array

Given an array A[] consisting of n elements and integer K. The task is to find the maximum length of the subsequence of array A[], such that all numbers in that subsequence are equal after applying the given operation. For each (1 ≤ i ≤ n), perform the following operation exactly one time:

Replace A_i with A_i + x, where x ∈ [-K, K] which denotes x should lie in the range of -K and K, both inclusive.
Assume 1-based indexing.

Examples:

Input: n = 4, k = 1, A[] = {2, 5, 1, 2}
Output: 3
Explanation: Applying one operation on indices 1, 2, and 4 to get array A as (2, 5, 1, 2). Applying one operation on index 3, with x = 1 to get array A as (2, 5, 2, 2). Therefore, the maximum length of the subsequence with equal numbers is 3.

Input: n = 4, k = 2, A[] = {3, 5, 1, 3}
Output: 4
Explanation: Applying one operation on indices 2 and 3 to get array A as (3, 3, 3, 3). Therefore, the maximum length of the subsequence with equal numbers is 4.

Approach: To solve the problem follow the below idea:

The idea is to try all possible values of x from -k to k, for each element of the input array A. For each value of x, it computes the target value (A[i] + x) and then checks how many elements in the subsequence starting from i + 1 can be changed to the target value using at most k-x operations. If the number of elements that can be changed to the target value is greater than the current maximum count, then it updates the maximum count. At the end, it returns the maximum count of a subsequence with equal numbers that can be obtained by applying the given operation.

Below are the steps for the above approach:

Initialize a variable maxCount = 1 to keep track of the maximum length of the subsequence with equal numbers.
Iterate over each element of the array using a loop variable i from 1 to n.
For each element, iterate over all possible values of x from -k to k using another loop variable x.
Initialize a variable say target and calculate the target value by adding the current element A[i] and x.
Initialize a variable count = 1 to keep track of the length of the current subsequence with equal numbers, starting with the current element A[ i ].
Iterate over the remaining elements of the array a using a loop variable j from i+1 to n.
Check if the absolute difference between the current element A[ j ] and the target value is less than or equal to k-x, and increment the count variable.
Update the maxCount variable if the current count value is greater than the current maxCount.
Return the maxCount value.

Below is the code for the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

int MaximizeEqualNumber(int n, int k, int a[])

{

int maxCount = 1;

for (int i = 1; i <= n; i++) {

for (int x = -k; x <= k; x++) {

int target = a[i] + x;

int count = 1;

for (int j = i + 1; j <= n; j++) {

if (abs(a[j] - target) <= k - x) {

count++;

}

if (count > maxCount) {

maxCount = count;

}

return maxCount;

}

int main()

{

int n = 4;

int K = 1;

int A[] = { 2, 5, 1, 2 };

int result = MaximizeEqualNumber(n, K, A);

cout << "Maximum length of subsequence with equal "

"numbers: "

<< result << endl;

return 0;

}

Output

Maximum length of subsequence with equal numbers: 3

Time Complexity: O(N²* K), because of the three nested loops. The outer loop iterates n times, the middle loop iterates 2k+1 times, and the inner loop iterates n times at worst. Therefore, the total number of iterations is n(2k+1)n, which simplifies to O(N²k).
Auxiliary Space: O(1)

Replace A_i with A_i + x, where x ∈ [-K, K] which denotes x should lie in the range of -K and K, both inclusive.
Assume 1-based indexing.