Length of Longest Subsequence Whose XOR Value is Odd in Java
In this tutorial, we are going to learn about length of longest subsequence whose XOR value is odd in Java. To compute the length of the longest subsequence such that the bitwise XOR of all the integers in the subsequence is odd, given an array arr[] of N positive integers in array form.
Examples:
Example 1:
Input: N = 5, arr[] = {4, 8, 6, 1, 2}
Output: 15
Explanation: {4, 8, 6, 1, 2} is the longest length subsequence, and the XOR of all elements equals 15. There are more subsequences.
Example 2:
Input: N = 6, arr[] = {3, 5, 2, 7, 6, 4}
Output: 7
Explanation: There are other subsequences as well. The subsequence with the longest length is {3, 5, 7}, where the XOR of all elements is 7.
Naïve approach:
ALGORITHM:
Step 1: Determine how many even and odd components there are in arr[].
Step 2: There are two scenarios that could occur if the number of odd values is equal to the array size, or N:
Step 2.1: In the event that the array's size is odd, the maximum length will equal N.
Step 2.2: If not, the maximum length will be N – 1.
Step 3: If the number of even values matches the array size, the maximum length should be set to 0.
Step 4: Include all the even items in the maximum length, if both kinds of elements are found in the provided array, then, and for odd elements, all of them will be included if the count of odd values is odd; else, odd – 1 elements will be included.
Step 5: Print the longest subsequence's maximum length once the previous stages are completed.
Filename: LongestSubsequence.java
import java.io.*; public class LongestSubsequence { // Function to determine the maximum XOR subsequence with an odd value static int lengthOfLongestXORSubsequence(int[] elements, int number) { // Set the odd and even counts to zero. int m, odd = 0, even = 0; // Determine how many odd and even numbers are in the provided array. for (m = 0; m < number; m++) { if ((elements[m] & 1) != 0) odd++; else even++; } int maximumLength; if (odd == number) { // If every value in the provided array is odd if (odd % 2 == 0) maximumLength = number - 1; else maximumLength = number; } else if (even == number) { // If every value in the provided array is even maximumLength = 0; } else { // If every value in the provided array is both even and odd if (odd % 2 == 0) maximumLength = even + odd - 1; else maximumLength = even + odd; } return maximumLength; } public static void main(String[] args) { // Given a sample array arr[] int[] elements = { 8, 9, 10, 11, 12 }; int number = elements.length; System.out.print(lengthOfLongestXORSubsequence(elements, number)); } }
Output:
4
Complexity analysis:
Time complexity: The time complexity of the program is O(N).
Space complexity: The space complexity of the program is O(1).
Approach: Using odd – count XOR subsequence
ALGORITHM:
Step 1: Determine how many odd components are there in an array[].
Step 2: Calculate the XOR subsequence's maximum length by counting the odd values.
Filename: CountSubsequence.java
import java.io.*; public class CountSubsequence { // Function to determine the maximum XOR subsequence with an odd value static int longestXORSubsequence(int[] elements, int length) { // Set the odd to zero. int odd = 0; for (int a = 0; a < length; a++) { if ((elements[a] & 1) != 0) odd++; } // Length of maximum variable int maximumLength; if (odd == length) { // If every value in the provided array is odd maximumLength = (odd % 2 == 0) ? length - 1 : length; } else { // If every value in the provided array is both odd and even maximumLength = Math.min(odd + 1, length); } return maximumLength; } public static void main(String[] args) { // Given an sample array arr[] int[] elements = { 12, 13, 14, 15, 16 }; int length = elements.length; System.out.print(longestXORSubsequence(elements, length)); } }
Output:
3
Complexity analysis:
Time complexity: The time complexity of the program is O(n).
Space complexity: The space complexity of the program is O(1).