Solution 2 for Scaler Topics Fortnightly Contest - 20
FREE
Maximum Xor Sum Value Complete Solution
This article is part of the Scaler Topics Fortnightly Contest - 20
Transform Your Career
Choose from our industry-leading programs designed for career success
Modern Software and AI Engineering Program
Master full-stack development with AI integration
+1000 moreModern Data Science and ML with specialisation in AI
Advanced data science techniques with AI specialization
+1000 moreAdvanced AIML with Specialisation in Agentic AI
Deep dive into AIML with focus on Agentic systems
+1000 moreDevOps, Cloud & AI Platform Engineering
Build and manage AI-powered cloud infrastructure
+1000 moreAI Engineering Advanced Certification by IIT-Roorkee
Premier AI engineering certification from IIT-Roorkee
Solution Approach
We will calculate two arrays start[] and end[] for every bit. The value of start[j] will give the position where the j-th bit is first set. The value of end[j] will give the position where for all positions k (k >= j), the j-th bit is set in X[k].
- Case 1 : start[j] = end[j] For all position k (k >= end[j]), the j-th bit is set in X
- Case 2 : end[j] - start[j] = 2 For all position k (k >= end[j] or k = start[j]), the j-th bit is set in X The (start[j] + 1)th postion of X must have the j-th bit unset.
- Case 3 : end[j] - start[j] > 2 We can choose whether to set or unset the j-th bit in the (end[j] - 2)th postion of X. So this bit will always contribute to the xor sum of X
Time Complexity : O(NlogT) Space Complexity : O(N) where T = 2^30
C++ Implementation
Java Implementation
Scaler Placement Report and Statistics
Scaler learners achieved 2.5x salary growth with average post-Scaler CTC reaching ₹23L.
Google
Amazon
Microsoft
Flipkart
Adobe1200+ more
