Count of integers K in range [0, N] such that (K XOR K+1) equals (K+2 XOR K+3)

Count of integers K in range [0, N] such that (K XOR K+1) equals (K+2 XOR K+3)

Given an integer N, the task is to print the count of all the non-negative integers K less than or equal to N, such that bitwise XOR of K and K+1 equals bitwise XOR of K+2 and K+3.

Examples:

Input: N = 3
Output: 2
Explanation: 
The numbers satisfying the conditions are:

1. K = 0, the bitwise XOR of 0 and 1 is equal to 1 and the bitwise xor of 2 and 3 is also equal to 1.
2. K = 2, the bitwise XOR of 2 and 3 is equal to 1 and the bitwise xor of 4 and 5 is also equal to 1.

Therefore, there are 2 numbers satisfying the condition.

Input: 4
Output: 3

Naive Approach: The simplest approach is to iterate over the range [0, N] and check if the current number satisfies the condition or not. If it satisfies, increment the count by 1. After checking all the numbers, print the value of the count.

Time Complexity: O(N)
Auxiliary Space: O(1)

Efficient Approach: The above approach can be optimized by the observation that all the even numbers in the range [0, N] satisfy the given condition.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h> using namespace std;    int countXor(int N) {                  int cnt = N / 2 + 1;             return cnt; }    int main() {          int N = 4;             cout << countXor(N);        return 0; }

Time Complexity: O(1)
Auxiliary Space: O(1)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.  To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.

In case you wish to attend live classes with experts, please refer DSA Live Classes for Working Professionals and Competitive Programming Live for Students.

Adblock test (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets