CODEWITHSUNDEEP
javascriptxor
Antonio Salazar
Antonio Salazar

Reputation: 41

XOR of all integers

I’m a jr web dev trying to improve my logic/algorithm skills, while studying I have found coding challenges like the one below, for this kind of problems can you point me in the right direction, I mean what should I study, check, review? And for the below challenge can you give me an idea on how to solve it, maybe some pseudo code?

CHALLENGE:

You are given Q queries. Each of the query contains two integers L and R. For each query print out the XOR of all integers in the given range which have only one bit in their binary representation.

Input format:

  • The first line contains Q queries.
  • Next Q lines contain two integers L and R

Output format:

Print one integer for each query denoting the answer

Constraints:

1 ≤ Q ≤ 105
1 ≤ L ≤ R ≤ 1018

Sample input

1
60 - 130

Sample Output

192

What I have tried so far:

const sumQuery = (q, n) => {
  let bitCount = [];
  //travers the bits
  for(let i = 0; i < 32; i++) {
    for(let j = 0; j < n; j++) {
     // check whether the current bit is
     let temp = Math.sqrt(arr[j]) * 2 );
     if(temp % 2 !== 0 ) {
      console.log(temp)
     }
    }
  }
}

Upvotes: 4

Views: 600

Answers (1)

Artem K
Artem K

Reputation: 169

There are 2 parts to your question, I will try to answer them both separately.

1) What should you study to improve your logic / algorithmic skills? First, you should determine your purpose for doing that (trying to get a better job / building fundamentals in cs / learning how specific systems or frameworks function and etc). Once you figure out what your exact reason for trying to improve, it will be much easier to determine what kind of knowledge / skills you will need to gather. Here are some recommendations for the paths that I mentioned:

a) Trying to get a better job. If that is the case - my only recommendation is practise your coding interview questions. Depth of your knowledge doesn’t often matter as much as your ability to solve these during an interview (based on my personal experience). Here are a few places where you can start:

b) Building fundamentals in CS. There are a few ways to do this (including going to school). If you are looking for a program, my recommendations are as follows:

c) Better understanding of certain systems. For that - I would highly recommend reading through the system implementation or doing a deeper tutorial on it. Recommendations:

2) How to solve your specific coding challenge. Here is a great breakdown of 80% of the challenge that you are presenting described by someone else (https://www.codechef.com/PRJRF14/problems/XORSN). I would recommend getting a solid understanding of binary data and the concept of XOR between integers.

Possible solution steps (I will not write it out for you in js, since you want to solve it yourself):

  • Like mentioned by Maaz Syed Adeeb - you only need to account for powers of 2 when searching for the XOR between the given integers range (since they are the only ones that have one bit binary representations).
  • Make note of all powers of 2 in the given constraint valid = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512]
  • Determine which of these lie within given range
  • Convert each valid integer to binary
  • Find XOR between each valid integer using this logic
Rule 1 : If both bits are 1 then XOR’ed bit will be 0.
Rule 2 : If both bits are 0 then XOR’ed bit will be 0.
Rule 3 : If one bit is 0 and one bit is 1 XOR’ed bit will be 1.
  • Convert binary code from your last XOR comparison into an integer

Good luck!

Upvotes: 2

Related Questions