Solution 3 for Scaler Topics Fortnightly Contest - 14

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

Build an AI-First Career, Master the Complete Skillset

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

NSDC Certified

AI Forward Deployed Engineer Program

Full-stack engineering, production AI and client-facing consulting

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

Solution Approach

• If popcount(x)%2 = 0 and popcount(y)%2 = 0, then popcount(x⊕y)%2 is 0.
• If popcount(x)%2 = 1 and popcount(y)%2 = 1, then popcount(x⊕y)%2 is 0.
• If popcount(x)%2 = 0 and popcount(y)%2 = 1, then popcount(x⊕y)%2 is 1.
• Thus, we can say for an array to be superior, the count of elements x such that popcount(x)%2 = 1 should be even.
• Thus we maintain a Sorted List odd_popcount of indices of the A with elements having odd popcount at those indices.
• For each query, if the parity of popcount changes, we add or remove the corresponding index based on the scenario.
• If the size of odd_popcount is even after performing a query, then ans for that query is |A| since the whole array is superior. else, the longest superior subarray is either of the below:
• subarray starting after the first index in odd_popcount till the end.
• subarray starting from index 1 till before the last index in odd_popcount.
• We can use std::set (C++) data structure for the same.

Time Complexity - $O((N + Q) * (log(K) + log(N)))$

where N is length of A and $K = 1e5 (log(K)$ comes from counting popcount of elements).

C++ Implementation

Java Implementation

Hiring Partners:

GoogleAmazonMicrosoftFlipkartAdobe1200+ more

Python Implementation