All Tracks Basic Programming Bit Manipulation Basics of Bit Manipulation Problem

AISH AND XOR
Tag(s):

Easy-Medium

Problem
Editorial
Analytics

“…I always wanted to become an architect, but I’m not very good at math.”

Aishwarya was saying this to her friend Puper. Puper motivated her for screwing up the things related to math and said he will also help her if needed.

Being motivated, she started up practicing hard problems of maths and she got stuck in a problem and asked for help from Puper. She is playing with XOR, given an array (containing only 0 and 1) as element of N length.

Given L and R, she wants to know the value of XOR of all elements from L to R (both inclusive) and number of unset bits (0's) in the given range of the array.
Being new she finds it tough so she ask for help from Puper. Puper also finds it tough and confusing. So he ask for your help.
INPUT:-
The first line contains the number N and the next line contains N numbers containing 0 and 1 only. Next line contain number of query q, and next q lines contains L and R.
OUTPUT:-
For each query print the xor value and number of unset bits in that range.
CONSTRAINT:-
1<=N<=100000 (1-based indexing of elements)
1<=Q<=N
1<=L<=R<=100000
0<=R-L<=100000

SAMPLE INPUT
5
1 0 0 0 1
3
2 4
1 5
3 5
SAMPLE OUTPUT
0 3
0 3
1 2
Explanation

In the given case the bit sequence is of length 5 and the sequence is 1 0 0 0 1. For query 1 the range is 2 4, and the answer is (array[2] xor array[3] xor array[4]) = 0, and number of zeroes are 3, so output is 0 3. Similarly for other queries.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

National Institute of Technology Patna

Challenge Name

Valentine Breakup!

Notifications
View All Notifications