# Non-negative pairs with sum of Bitwise OR and Bitwise AND equal to N

• Last Updated : 23 Apr, 2021

Given an integer N, the task is to find all non-negative pairs (A, B) such that the sum of Bitwise OR and Bitwise AND of A, B is equal to N, i.e., (A | B) + (A & B) = N.

Examples:

Input: N = 5
Output: (0, 5), (1, 4), (2, 3), (3, 2), (4, 1), (5, 0)
Explanation: All possible pairs satisfying the necessary conditions:

1. (0 | 5) + (0 & 5) = 5 + 0 = 5
2. (1 | 4) + (1 & 4) = 5 + 0 = 5
3. (2 | 3) + (2 & 3) = 3 + 2 = 5
4. (3 | 2) + (3 & 2) = 3 + 2 = 5
5. (4 | 1) + (4 & 1) = 5 + 0 = 5
6. (5 | 0) + (5 & 0) = 5 + 0 = 5

Input: N = 7
Output: (0, 7), (1, 6), (2, 5), (3, 4), (4, 3), (5, 2), (6, 1), (7, 0)
Explanation: All possible pairs satisfying the necessary conditions:

1. (0 | 7) + (0 & 7) = 7 + 0 =7
2. (1 | 6) + (1 & 6) = 7 + 0 =7
3. (2 | 5) + (2 & 5) = 7 + 0 =7
4. (3 | 4) + (3 & 4) = 7 + 0 =7
5. (4 | 3) + (4 & 3) = 7 + 0 =7
6. (5 | 2) + (5 & 2) = 7 + 0 =7
7. (6 | 1) + (6 & 1) = 7 + 0 = 7
8. (7 | 0) + (7 & 0) = 7 + 0 = 7

Naive Approach: The simplest approach is to iterate over the range [0, N] and print those pairs (A, B) that satisfy the condition (A | B) + (A & B) = N

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

Efficient Approach: To optimize the above approach, the idea is based on the observation that all those non-negative pairs whose sum is equal to N satisfy the given condition. Therefore, iterate over the range [0, N] using the variable i and print the pair i and (N – i).

Below is the implementation of the above approach.

## C++

 `// C++ program for the above approach``#include ``using` `namespace` `std;` `// Function to print all pairs whose``// sum of Bitwise OR and AND is N``void` `findPairs(``int` `N)``{``    ``// Iterate from i = 0 to N``    ``for` `(``int` `i = 0; i <= N; i++) {` `        ``// Print pairs (i, N - i)``        ``cout << ``"("` `<< i << ``", "``             ``<< N - i << ``"), "``;``    ``}``}` `// Driver Code``int` `main()``{``    ``int` `N = 5;``    ``findPairs(N);` `    ``return` `0;``}`

## Java

 `// Java program for the above approach``import` `java.util.*;``import` `java.lang.*;` `class` `GFG{``    ` `// Function to print all pairs whose``// sum of Bitwise OR and AND is N``static` `void` `findPairs(``int` `N)``{``    ` `    ``// Iterate from i = 0 to N``    ``for``(``int` `i = ``0``; i <= N; i++)``    ``{``        ` `        ``// Print pairs (i, N - i)  ``        ``System.out.print( ``"("` `+ i + ``", "` `+``                          ``(N - i) + ``"), "``);``   ``}``}` `// Driver code``public` `static` `void` `main(String[] args)``{``    ``int` `N = ``5``;``    ` `    ``findPairs(N);``}``}` `// This code is contributed by ajaykr00kj`

## Python3

 `# Python3 program for the above approach` `# Function to print all pairs whose``# sum of Bitwise OR and AND is N``def` `findPairs(N):``    ` `     ``# Iterate from i = 0 to N``     ``for` `i ``in` `range``(``0``, N ``+` `1``):``        ` `        ``# Print pairs (i, N - i)``        ``print``(``"("``, i, ``","``,``              ``N ``-` `i, ``"), "``, end ``=` `"")` `# Driver code``if` `__name__ ``=``=` `"__main__"``:``    ` `    ``N ``=` `5``    ` `    ``findPairs(N)` `# This code is contributed by ajaykr00kj`

## C#

 `// C# program for the above approach``using` `System;`` ` `class` `GFG{`` ` `// Function to print all pairs whose``// sum of Bitwise OR and AND is N``static` `void` `findPairs(``int` `N)``{``    ` `    ``// Iterate from i = 0 to N``    ``for``(``int` `i = 0; i <= N; i++)``    ``{``        ` `        ``// Print pairs (i, N - i)  ``        ``Console.Write( ``"("` `+ i + ``", "` `+``                        ``(N - i) + ``"), "``);``   ``}``}` `// Driver code``public` `static` `void` `Main()``{``    ``int` `N = 5;``     ` `    ``findPairs(N);``}``}` `// This code is contributed by sanjoy_62`

## Javascript

 ``

Output:

`(0, 5), (1, 4), (2, 3), (3, 2), (4, 1), (5, 0),`

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

My Personal Notes arrow_drop_up
{"ft_lang_label":"__label__en","ft_lang_prob":0.66288054,"math_prob":0.9976539,"size":3634,"snap":"2022-27-2022-33","text_gpt3_token_len":1405,"char_repetition_ratio":0.11515152,"word_repetition_ratio":0.37172177,"special_character_ratio":0.4689048,"punctuation_ratio":0.16496164,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9999306,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2022-08-17T00:50:29Z\",\"WARC-Record-ID\":\"<urn:uuid:61815956-320b-48c5-8520-5af94a9565d5>\",\"Content-Length\":\"153790\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:bd8c1100-fd38-4bac-b093-9b3db8496b5e>\",\"WARC-Concurrent-To\":\"<urn:uuid:7f4ad572-7a20-4698-b4f9-9ce4b60a179e>\",\"WARC-IP-Address\":\"23.49.5.212\",\"WARC-Target-URI\":\"https://www.geeksforgeeks.org/non-negative-pairs-with-sum-of-bitwise-or-and-bitwise-and-equal-to-n/?ref=rp\",\"WARC-Payload-Digest\":\"sha1:6GZU2235YYNUZESGCA2IWFUBGVAXAEY7\",\"WARC-Block-Digest\":\"sha1:TDEJUBZT7MF6FD76JABJJ7JDNVYPN55O\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2022/CC-MAIN-2022-33/CC-MAIN-2022-33_segments_1659882572833.78_warc_CC-MAIN-20220817001643-20220817031643-00405.warc.gz\"}"}