Longest Harmonious Subsequence

Hard
0/120
Average time to solve is 15m
profile
Contributed by
13 upvotes
Asked in companies
AppleeBayLTI - Larsen & Toubro Infotech

Problem statement

You are given an array ‘ARR’ of 'N' integers. Your task is to find the longest harmonious subsequence of this array.

A sequence is Harmonious if the difference between the maximum and the minimum of all the elements is exactly 1.

For example 
[3, 4, 3, 3, 3, 3, 4] is a harmonic array as the maximum of all the elements is 4 and minimum of all the elements is 3. So, the difference between the maximum and the minimum = 4 - 3 = 1.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer ‘T’, denoting the number of test cases. The test cases follow.

The first line of each test case contains an integer N, which denotes the number of integers in the array ‘ARR’.

The second line of each test case contains 'N' integers of the array ‘ARR’, separated by space.
Output Format: 
For each test case, return the size of the longest harmonious subsequence.
Note: 
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints: 
1<= T <= 100
1 <= N <= 10^4
1 <= ARR[i] <= 10^8

Time Limit: 1 sec
Sample Input 1:
2
4
1 2 2 1
4
1 2 3 4
Sample Output 1:
4
2
Explanation for Sample Input 1:
In the first test case, the given array is [1, 2, 2, 1]. If we take the complete array, then the maximum of all the elements is 2 and the minimum of all the elements is 1. So, the difference between the maximum and the minimum = 2 - 1 = 1. Hence, the longest Harmonic subsequence is [1, 2, 2, 1] and its length is 4.

In the second test case, the given array is [1, 2, 3, 4]. If we take the complete array, then the maximum of all the elements is 4 and the minimum of all the elements is 1. 
So, the difference between the maximum and the minimum = 4 - 1 = 3. So, it is not a Harmonic subsequence. If we take subsequence as [1, 2], then the maximum of all the elements is 2 and the minimum of all the elements is 1. 
So, the difference between the maximum and the minimum = 2 - 1 = 1. So, it is a harmonic subsequence and this is the longest harmonic subsequence. If we take subsequence as [2, 3] or [3, 4], then we will get the same answer.
Sample Input 2:
2
2
1 2
10
1 2 2 3 4 5 1 1 1 1
Sample Output 2:
2
7
Hint

Generate all the possible subsequences and check if it possible to make it harma onious subsequence or not?

Approaches (3)
Brute Force

The idea is to generate all the possible subsequences using the bit masking technique. For each subsequence, check if it is a Harmonious subsequence or not. Take the maximum length of all the possible subsequences.

 

The steps are as follows:

  • Initialize 'ANSWER' to 0, which denotes the longest length of the Harmonic subsequence.
  • Iterate from ‘i’ = 0 to ‘2^N - 1’, where ‘N’ is the length of the given Array, ‘ARR’.
    • Initialize three integers ‘MIN_VALUE’, ‘MAX_VALUE’, and ‘COUNT_LENGTH’ with INT_MAX, INT_MIN, and 0 respectively which stores the minimum, maximum values of the current subsequence and length of the current subsequence respectively.
    • Iterate from ‘j’ = 0 to ‘N-1’:
      • If a jth bit of i is set and ‘MIN_VALUE’ is less than ARR[j], then update ‘MIN_VALUE’ to ARR[j].
      • If a jth bit of i is set and ‘MAX_VALUE’ is greater than ARR[j], then update ‘MAX_VALUE’ to ARR[j].
      • Increment the count as we are including the current element in the subsequence.
    • If the difference between the ‘MAX_VALUE’ and ‘MIN_VALUE’ is 1. It means it is a valid subsequence. Update 'ANSWER' to a maximum of 'ANSWER' and ‘COUNT_LENGTH’. Also, take care of the integer overflow.
  • Return 'ANSWER’ as the final answer.
Time Complexity

O(N*2^N), where ‘N’ is the length of the given array ‘arr’. 

 

We are generating the binary values from 0 to 2^N - 1 and then iterating through the array. Hence the overall time complexity is O(N*2^N).

Space Complexity

O(1).

 

As we are using constant space.

Code Solution
(100% EXP penalty)
Longest Harmonious Subsequence
Full screen
Console