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 <bits/stdc++.h>using namespace std;// Function to find the pairvector<vector<int> > solve(int& N){ vector<int> x, y; int count = 0; vector<vector<int> > 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 pairsvoid printPairs(int& N){ vector<vector<int> > ans = solve(N); for (auto& x : ans) { for (auto& y : x) cout << y << " "; cout << endl; }}// Driver codeint 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<Integer> x = new ArrayList<Integer>(); 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 pairdef 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 pairsdef printPairs(N): ans = solve(N) for x in ans: for y in x: print(y, end=" ") print()# Driver codeif __name__ == "__main__": N = 144 # Function call printPairs(N) # This code is contributed by rakeshsahni |
C#
// C# Code to implement above approachusing 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 pairfunction 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 pairsfunction 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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
