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 Ai with Ai + 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++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;// Define the function to find the maximum// length of subsequence with equal numbersint MaximizeEqualNumber(int n, int k, int a[]){ // Initialize the maximum count seen // so far to 1 int maxCount = 1; // Loop over all indices in the array for (int i = 1; i <= n; i++) { // Loop over all possible // values of x for (int x = -k; x <= k; x++) { // Compute the target value // based on the current // index and x int target = a[i] + x; // Initialize the count for // the current target value // to 1 int count = 1; // Loop over all remaining // indices in the array for (int j = i + 1; j <= n; j++) { // Check if the current // value can be transformed // to the target value using // the given operation if (abs(a[j] - target) <= k - x) { // Increment the count // for the current // target value count++; } } // Check if the count for the // current target value is // greater than the maximum // count seen so far if (count > maxCount) { // Update the maximum // count if necessary maxCount = count; } } } // Return the maximum count // seen for any target value return maxCount;}// Driver codeint main(){ int n = 4; int K = 1; int A[] = { 2, 5, 1, 2 }; // Call the function to find the // maximum length of subsequence // with equal numbers int result = MaximizeEqualNumber(n, K, A); // Print the result cout << "Maximum length of subsequence with equal " "numbers: " << result << endl; return 0;} |
Java
import java.util.*;public class Main { // Define the function to find the maximum // length of subsequence with equal numbers static int maximizeEqualNumber(int n, int k, int[] a) { // Initialize the maximum count seen // so far to 1 int maxCount = 1; // Loop over all indices in the array for (int i = 0; i < n; i++) { // Loop over all possible // values of x for (int x = -k; x <= k; x++) { // Compute the target value // based on the current // index and x int target = a[i] + x; // Initialize the count for // the current target value // to 1 int count = 1; // Loop over all remaining // indices in the array for (int j = i + 1; j < n; j++) { // Check if the current // value can be transformed // to the target value using // the given operation if (Math.abs(a[j] - target) <= k - Math.abs(x)) { // Increment the count // for the current // target value count++; } } // Check if the count for the // current target value is // greater than the maximum // count seen so far if (count > maxCount) { // Update the maximum // count if necessary maxCount = count; } } } // Return the maximum count // seen for any target value return maxCount; } // Driver code public static void main(String[] args) { int n = 4; int k = 1; int[] a = {2, 5, 1, 2}; // Call the function to find the // maximum length of subsequence // with equal numbers int result = maximizeEqualNumber(n, k, a); // Print the result System.out.println("Maximum length of subsequence with equal numbers: " + result); }}// This code is contributed by Prajwal Kandkekar |
Python3
# Define the function to find the maximum# length of subsequence with equal numbersdef MaximizeEqualNumber(n, k, a): # Initialize the maximum count seen # so far to 1 maxCount = 1 # Loop over all indices in the array for i in range(1, n+1): # Loop over all possible # values of x for x in range(-k, k+1): # Compute the target value # based on the current # index and x target = a[i] if i<n else 0 + x # Initialize the count for # the current target value # to 1 count = 1 # Loop over all remaining # indices in the array for j in range(i + 1, n+1): # Check if the current # value can be transformed # to the target value using # the given operation if abs(a[j] if j<n else 0 - target) <= k - x: # Increment the count # for the current # target value count += 1 # Check if the count for the # current target value is # greater than the maximum # count seen so far if count > maxCount: # Update the maximum # count if necessary maxCount = count # Return the maximum count # seen for any target value return maxCount# Driver codeif __name__ == "__main__": n = 4 K = 1 A = [2, 5, 1, 2] # Call the function to find the # maximum length of subsequence # with equal numbers result = MaximizeEqualNumber(n, K, A) # Print the result print("Maximum length of subsequence with equal numbers:", result) |
C#
// C# code for the above approach:using System;class GFG{// Define the function to find the maximum// length of subsequence with equal numbers static int MaximizeEqualNumber(int n, int k, int[] a) { // Initialize the maximum count seen // so far to 1 int maxCount = 1; // Loop over all indices in the array for (int i = 0; i < n; i++) { // Loop over all possible // values of x for (int x = -k; x <= k; x++) { // Compute the target value // based on the current // index and x int target = a[i] + x; // Initialize the count for // the current target value // to 1 int count = 1; // Loop over all remaining // indices in the array for (int j = i + 1; j < n; j++) { // Check if the current // value can be transformed // to the target value using // the given operation if (Math.Abs(a[j] - target) <= k - x) { // Increment the count // for the current // target value count++; } } // Check if the count for the // current target value is // greater than the maximum // count seen so far if (count > maxCount) { // Update the maximum // count if necessary maxCount = count; } } } // Return the maximum count // seen for any target value return maxCount; } // Driver code static void Main() { int n = 4; int k = 1; int[] a = { 2, 5, 1, 2 }; // Call the function to find the // maximum length of subsequence // with equal numbers int result = MaximizeEqualNumber(n, k, a); // Print the result Console.WriteLine("Maximum length of subsequence with equal numbers: " + result); }} |
Javascript
// JavaScript code for the above approach:// Define the function to find the maximum// length of subsequence with equal numbersfunction MaximizeEqualNumber(n, k, a) { // Initialize the maximum count seen // so far to 1 let maxCount = 1; // Loop over all indices in the array for (let i = 1; i <= n; i++) { // Loop over all possible // values of x for (let x = -k; x <= k; x++) { // Compute the target value // based on the current // index and x let target = a[i] + x; // Initialize the count for // the current target value // to 1 let count = 1; // Loop over all remaining // indices in the array for (let j = i + 1; j <= n; j++) { // Check if the current // value can be transformed // to the target value using // the given operation if (Math.abs(a[j] - target) <= k - x) { // Increment the count // for the current // target value count++; } } // Check if the count for the // current target value is // greater than the maximum // count seen so far if (count > maxCount) { // Update the maximum // count if necessary maxCount = count; } } } // Return the maximum count // seen for any target value return maxCount;}// Driver codefunction main() { let n = 4; let k = 1; let A = [2, 5, 1, 2]; // Call the function to find the // maximum length of subsequence // with equal numbers let result = MaximizeEqualNumber(n, k, A); // Print the result console.log("Maximum length of subsequence with equal numbers: " + result);}// Call the main functionmain(); |
Output
Maximum length of subsequence with equal numbers: 3
Time Complexity: O(N2 * 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(N2k).
Auxiliary Space: O(1)
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!
