XOR Subsequence Complete Solution

This article is part of the Scaler Topics Fortnightly Contest - 16

Transform Your Career

Choose from our industry-leading programs designed for career success

NSDC Certified

Modern Software and AI Engineering Program

Master full-stack development with AI integration

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Modern Data Science and ML with specialisation in AI

Advanced data science techniques with AI specialization

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Advanced AIML with Specialisation in Agentic AI

Deep dive into AIML with focus on Agentic systems

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

DevOps, Cloud & AI Platform Engineering

Build and manage AI-powered cloud infrastructure

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

AI Engineering Advanced Certification by IIT-Roorkee

Premier AI engineering certification from IIT-Roorkee

3 MonthsDuration

AI-LedCurriculum

Career SupportSupport

Go to Program

Solution Approach

• We will use this property of xor if $x^y$ = z then x = $y^z$.
• We will divide the array in two parts let P1 and P2, then generate all the subsequences of each part.
• Now B if exist can be a subsequence of P1 or P2 or combination of some subsequence of both P1 and P2.
• First we will check if B exist in P1 or P2, if not then we will check for all subsequence P1 XOR B.
• If this xor value exists then we've found B as subsequence xor in A.

Time Complexity:- O$(2^{|A|/2})$ Space Complexity:- O$(2^{|A|/2})$

C++ Implementation

Java Implementation

Hiring Partners:

GoogleAmazonMicrosoftFlipkartAdobe1200+ more

Python Implementation