Given an integer N, the task is to find the number of pairs (say {a, b})from 1 to N (both inclusive) that satisfies the condition:
- a and b are distinct elements.
- The values of a | b and a ^ b are equal and
- a( a | b ) = b( a ^ b ) – ( a | b ) also holds true.
Examples:
Input: N=5
Output:1
Explanation: If we consider a=3 and b=4, then a | b = 7 and a ^ b=7. Thus it forms a valid pairInput: N=8
Output: 3
The possible pairs are {1, 2}, {3, 4} and {7, 8}
Intuition:
Let us consider two numbers a and b. As we know, the sum of these two values can be written as:
- a + b = ( a | b ) + ( a & b )
- a + b = ( a ^ b ) + 2*( a & b)
So equating 1 and 2 we get:
a | b + (a & b) = a^b + 2 * (a & b) or
a | b = a ^ b + (a & b) (equation 3)Since it is said that (a ^ b) = (a | b), from third condition, we can derive:
a * ( a | b ) = b * ( a ^ b ) – ( a | b ) or
a * (a | b) = b * (a | b) – (a | b) or
a = b – 1 i.e. b – a = 1Since (a ^ b) and (a | b) are same, so from the 3rd equation we can derive that (a & b) = 0.
So the question finally boils down to figure out the adjacent pair of elements whose bitwise AND is 0.
Naive Approach using Linear Iteration:
The basic idea to solve this problem is to store count of unique adjacent pairs by iterating over the array using a loop from 1 to N.
- Initialize a counter variable (say count) to store the count of unique pairs.
- Start traversing using from i = 1 to N-1:
- Find the bitwise AND of i and i+1 and if it is 0 increment the count.
- Return count as the required answer.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to count the number of// unique pairs that satisfy the conditionsint countPairs(int n){ // stores the count of unique pairs int count = 0; // Traverse from i = 1 to N-1 for (int i = 1; i < n; i++) { int ans = (i & (i + 1)); // If AND value is 0, // increase count by 1 if (ans == 0) count++; } return count;}// Driver codeint main(){ // First test case int N = 8; cout << "For N = 8: " << countPairs(N) << "\n"; // Second test case N = 1; cout << "For N = 1: " << countPairs(N) << "\n"; // Third test case N = 2; cout << "For N = 2: " << countPairs(N); return 0;} |
Java
// Java code to implement the approachimport java.io.*;class GFG { // Function to count the number of unique pairs that // satisfy the conditions static int countPairs(int n) { // stores the count of unique pairs int count = 0; // Traverse from i=1 to N-1 for (int i = 1; i < n; i++) { int ans = (i & (i + 1)); if (ans == 0) { // If AND value is 0, increase count by 1 count++; } } return count; } public static void main(String[] args) { // First test case int N = 8; System.out.println("For N = 8: " + countPairs(N)); // Second test case N = 1; System.out.println("For N = 1: " + countPairs(N)); // Third test case N = 2; System.out.println("For N = 2: " + countPairs(N)); }}// This code is contributed by lokesh. |
Python3
# python code to implement the approach# Function to count the number of# unique pairs that satisfy the conditionsdef countPairs(n): # stores the count of unique pairs count = 0 # Traverse from i = 1 to N-1 for i in range(1, n): ans = (i & (i + 1)) # If AND value is 0, # increase count by 1 if ans == 0: count = count+1 return count# Driver codeif __name__ == "__main__": # First test case N = 8 print("For N = 8: ", countPairs(N)) # Second test case N = 1 print("For N = 1: ", countPairs(N)) # Third test case N = 2 print("For N = 2: ", countPairs(N)) # This code is contributed by garg28harsh. |
C#
// C# code to implement the approachusing System;public class GFG { // Function to count the number of unique pairs that // satisfy the conditions static int countPairs(int n) { // stores the count of unique pairs int count = 0; // Traverse from i=1 to N-1 for (int i = 1; i < n; i++) { int ans = (i & (i + 1)); if (ans == 0) { // If AND value is 0, increase count by 1 count++; } } return count; } static public void Main() { // Code // First test case int N = 8; Console.WriteLine("For N = 8: " + countPairs(N)); // Second test case N = 1; Console.WriteLine("For N = 1: " + countPairs(N)); // Third test case N = 2; Console.WriteLine("For N = 2: " + countPairs(N)); }}// This code is contributed by lokeshmvs21. |
Javascript
// JavaScript code to implement the approach// Function to count the number of// unique pairs that satisfy the conditionsconst countPairs = (n) => { // stores the count of unique pairs let count = 0; // Traverse from i = 1 to N-1 for (let i = 1; i < n; i++) { let ans = (i & (i + 1)); // If AND value is 0, // increase count by 1 if (ans == 0) count++; } return count;}// Driver code// First test caselet N = 8;console.log(`For N = 8: ${countPairs(N)}<br/>`);// Second test caseN = 1;console.log(`For N = 1: ${countPairs(N)}<br/>`);// Third test caseN = 2;console.log(`For N = 2: ${countPairs(N)}`);// This code is contributed by rakeshsahni |
Output
For N = 8: 3 For N = 1: 0 For N = 2: 1
Time Complexity: O(N)
Auxiliary Space: O(N)
Efficient Approach:
Since we know that both the numbers differ by 1 hence by the property of the AND operation of any power of 2 with a number that is one less than that gives 0. Hence (2n) & (2n-1)==0, So we can directly count the number of pairs of form 2n and 2n-1.
Below is the implementation of the above idea.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to count the number of// unique pairs whoseint countPairs(int n){ // Get the maximum power of // 2 closest to n int max_power_of_2 = log2(n); return max_power_of_2;}// Driver codeint main(){ // First test case int N = 8; cout << "For N = 8: " << countPairs(N) << "\n"; // Second test case N = 1; cout << "For N = 1: " << countPairs(N) << "\n"; // Third test case N = 2; cout << "For N = 2: " << countPairs(N); return 0;} |
Java
// Java code to implement the approachimport java.util.*;class GFG {// Function to count the number of// unique pairs whosestatic int countPairs(int n){ // Get the maximum power of // 2 closest to n int max_power_of_2 = (int)(Math.log(n) / Math.log(2)); return max_power_of_2;}// Driver Codepublic static void main (String[] args) { // First test case int N = 8; System.out.println( "For N = 8: " + countPairs(N)); // Second test case N = 1; System.out.println( "For N = 1: " + countPairs(N)); // Third test case N = 2; System.out.println( "For N = 2: " + countPairs(N));}}// This code is contributed by sanjoy_62. |
Python3
# Python3 code to implement the approachimport math# Function to count the number of# unique pairs whosedef countPairs(n): # Get the maximum power of # 2 closest to n max_power_of_2 = int(math.log2(n)) return max_power_of_2# Driver code# First test caseN = 8print("For N = 8: ",countPairs(N))# Second test caseN = 1print("For N = 1: ",countPairs(N))# Third test caseN = 2print("For N = 2: ",countPairs(N))# This code is contributed by akashish__ |
C#
// C# code to implement the approachusing System;class GFG { // Function to count the number of // unique pairs whose static int countPairs(int n) { // Get the maximum power of // 2 closest to n int max_power_of_2 = (int)(Math.Log(n) / Math.Log(2)); return max_power_of_2; } // Driver Code public static void Main(string[] args) { // First test case int N = 8; Console.WriteLine("For N = 8: " + countPairs(N)); // Second test case N = 1; Console.WriteLine("For N = 1: " + countPairs(N)); // Third test case N = 2; Console.WriteLine("For N = 2: " + countPairs(N)); }}// This code is contributed by karandeep1234 |
Javascript
// Javascript code to implement the approach// Function to count the number of// unique pairs whosefunction countPairs(n){ // Get the maximum power of // 2 closest to n let max_power_of_2 = Math.round(Math.log2(n)); return max_power_of_2;}// Driver code // First test case let N = 8; console.log( "For N = 8: " +countPairs(N)); // Second test case N = 1; console.log( "For N = 1: " +countPairs(N)); // Third test case N = 2; console.log( "For N = 2: " +countPairs(N)); // This code is contributed by garg28harsh. |
Output
For N = 8: 3 For N = 1: 0 For N = 2: 1
Time Complexity: O(log N) since it calculates in log (N) time.
Space Complexity: O(1)
Related Articles:
Share your thoughts in the comments
