Skip to main content

Find pair of integers such that their sum is twice their Bitwise XOR

Given a positive integer N, the task is to find all pairs of integers (i, j) from the range [1, N] in increasing order of i such that:

  • 1 ? i, j ? N
  • i + j = N
  • i + j = 2*(i ^ j)
  • If there are no such pairs, return a pair -1, -1.

Note: Here ‘^’ denotes the bitwise XOR operation.

Examples:

Input: N = 4
Output: 1, 3, 3, 1
Explanation: A total of 3 pairs satisfy the first condition: (1, 3), (2, 2), (3, 1).
There are only two valid pairs out of them: (1, 3) and (3, 1) as 1 + 3 = 4 = 2 * (1 ^ 3).

Input: 7
Output: -1, -1

Input: 144
Output: 36, 108,  44, 100, 100, 44,  108, 36

Approach: 

The problem can be viewed as a bitwise manipulation problem satisfying pre-conditions. 

If the pairs add upto N then it is obvious that the second element j of the pair can be generated using the first element i as j = N – i. Then we just have to check for the remaining condition  i + j = 2 * (i ^ j).

Follow the steps mentioned below to solve the problem:

  • Traverse from 1 to N for first element i and second element as j = N – i.
  • Check for N = i + j and N = 2 * (i ^ j) and push the first elements i and j into the 2-D vector ans and increment count.
  • Return -1,  -1 if count = 0 or ans, if count > 0.

Below is the implementation of the above approach.

C++14




// C++ code to solve using above approach
 
#include
using namespace std;
 
// Function to find the pair
vectorint> > solve(int& N)
    vector<int> x, y;
    int count = 0;
    vectorint> > ans;
 
    // For each element from 1 to N
    // check whether i + j = 2 * (i^j)
    // where j = N - i
    for (int i = 1; i <= N; i++)
        int j = N - i;
 
        if (N == 2 * (i ^ j))
 
            // Insert the pair into answer
            ans.push_back( i, j );
 
            // Increase count accordingly
            count++;
        
    
 
    if (count == 0)
        return -1, -1 ;
 
    return ans;
 
// Function to print the pairs
void printPairs(int& N)
    vectorint> > ans = solve(N);
    for (auto& x : ans)
        for (auto& y : x)
            cout << y << " ";
        cout << endl;
    
 
// Driver code
int main()
    int N = 144;
 
    // Function call
    printPairs(N);
    return 0;
 















Java

















 






 




 



























import java.util.*;


 


class Solve 


  public static void main(String[] args) 


    int N = 144;


    printFunction(N);


  


 


  private static void printFunction(int N)


    int count = 0, j = 0;


    ArrayList x = new ArrayList();


 


    for (int i = 1; i <= N; i++)


    


 


      // logic for j since i+j=N


      j = N - i;


      if (N == 2 * (i ^ j)) 


 


        // Insert the pair into answer


        x.add(i);


        x.add(j);


        // Increase count accordingly


        count++;


      


 


    


 


    if(count == 0)


    


      x.add(-1);


      x.add(-1);


 


      // loop for printing the elements in x


      for(int i = 0; i < x.size(); i = i + 2)


      


        System.out.print(x.get(i));


        System.out.printf("%d", x.get(i + 1));


        System.out.println();


      


 


    else


    


       


      // loop for printing the elements in x


      for(int i = 0; i < x.size(); i = i + 2)


      


        System.out.print(x.get(i));


        System.out.printf("  %d", x.get(i + 1));


        System.out.println();


      


     


      




 


// This code is contributed by msdsk07.






































Python3

















 






 




 



























# python code to solve using above approach


 


# Function to find the pair


def solve(N):


 


    x, y = [], []


    count = 0


    ans = []


 


    # For each element from 1 to N


    # check whether i + j = 2 * (i^j)


    # where j = N - i


    for i in range(1, N + 1):


        j = N - i


 


        if (N == 2 * (i ^ j)):


 


            # Insert the pair into answer


            ans.append([i, j])


 


            # Increase count accordingly


            count += 1


 


    if (count == 0):


        return [[-1, -1]]


 


    return ans


 


# Function to print the pairs


def printPairs(N):


 


    ans = solve(N)


    for x in ans:


        for y in x:


            print(y, end=" ")


        print()


 


# Driver code


if __name__ == "__main__":


    N = 144


 


    # Function call


    printPairs(N)


 


    # This code is contributed by rakeshsahni






































C#

















 






 




 



























// C# Code to implement above approach


 


using System;


using System.Collections;


using System.Collections.Generic;


 


class Solve 


  public static void Main(string[] args)


  


    int N = 144;


    printFunction(N);


  


 


  private static void printFunction(int N)


  


    int count = 0, j = 0;


    List<int> x = new List<int>();


 


    for (int i = 1; i <= N; i++) 


 


      // logic for j since i+j=N


      j = N - i;


      if (N == 2 * (i ^ j)) 


 


        // Insert the pair into answer


        x.Add(i);


        x.Add(j);


        // Increase count accordingly


        count++;


      


    


 


    if (count == 0) 


      x.Add(-1);


      x.Add(-1);


 


      // loop for printing the elements in x


      for (int i = 0; i < x.Count; i = i + 2) 


        Console.Write(x[i]);


        Console.Write(" " + x[i + 1]);


        Console.WriteLine();


      


    


    else 


 


      // loop for printing the elements in x


      for (int i = 0; i < x.Count; i = i + 2) 


        Console.Write(x[i]);


        Console.Write(" " + x[i + 1]);


        Console.WriteLine();


      


    


  




 


// This code is contributed by karandeep1234.






































Javascript

















 






 




 



























// JavaScript+ code to solve using above approach


 


// Function to find the pair


function solve(N)




    let x = [], y = [];


    let count = 0;


    let ans = [];


 


    // For each element from 1 to N


    // check whether i + j = 2 * (i^j)


    // where j = N - i


    for (let i = 1; i <= N; i++) 


        let j = N - i;


 


        if (N == 2 * (i ^ j)) 


 


            // Insert the pair into answer


            ans.push([ i, j ]);


 


            // Increase count accordingly


            count++;


        


    


 


    if (count == 0)


        return [ [ -1, -1 ]];


 


    return ans;




 


// Function to print the pairs


function printPairs(N)




    let ans = solve(N);


    console.log(ans);




 


// Driver code


    let N = 144;


 


    // Function call


    printPairs(N);


 


// This code is contributed by ishankhandelwals.








































Output

36 108 
44 100 
100 44 
108 36 




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







                                            Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.

                                            Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!







 

https://neveropen.tech/find-pair-of-integers-such-that-their-sum-is-twice-their-bitwise-xor/?feed_id=11&_unique_id=683c9f5f2febd












Labels:





























Comments











Post a Comment



















Popular posts from this blog





















Bare Metal Billing Client Portal Guide




























      Contents   Order a Bare Metal Server  My Custom / Contract Pricing   View Contract Details   Location Management      Order History & Status   View Order Details         Introduction  The phoenixNAP Client Portal allows you to purchase bare metal servers  and other phoenixNAP products and services. Using the intuitive interface and its essential tools, you can also easily manage your infrastructure.  This quick guide will show you how to use the new form  to order a bare metal server and how to navigate through new bare metal features  within the phoenixNAP Client Portal.     Order a Bare Metal Server  An order form is an accordion-based process for purchasing phoenixNAP products. Our order form allows you to view the pricing and order multiple products from the same category at the same time.     Note:  The prices on the form are per month . A contract is not required. However, if you want a contracted price, you may be eligible for a discount  depending on the quantity and ...




















Post a Comment









Read more






























Add an element in Array  to make the bitwise XOR as K




























   Given an array arr[]  containing N positive integers, the task is to add an integer such that the bitwise Xor of the new array becomes K.  Examples:    Input: arr[] = 1, 4, 5, 6, K = 4 Output: 2 Explanation: Bit-wise XOR of the array is 6.  And bit-wise XOR of 6 and 2 is 4.  Input: arr[] = 2, 7, 9, 1, K = 5 Output:  8        Approach: The solution to the problem is based on the following idea of bitwise Xor:   If for two numbers X  and Y , the bitwise Xor of X and Y is Z  then the bitwise Xor of X and Z is Y.   Follow the steps to solve the problem:   Let the bitwise XOR of the array elements be X .   Say the required value to be added is Y  such that X Xor Y = K .  From the above observation, it is clear that the value to be added (Y) is the same as X Xor K .   Below is the implementation of the above approach:   C++                                 // C++ code to implement the above approach     #include  using  namespace  std;     // Function to find the required value  int  find_...




















Post a Comment









Read more