Given a positive integer n, find count of positive integers i such that 0 <= i <= n and n+i = n^i
Examples :
Input : n = 7
Output : 1
Explanation:
7^i = 7+i holds only for only for i = 0
7+0 = 7^0 = 7 Input: n = 12
Output: 4
12^i = 12+i hold only for i = 0, 1, 2, 3
for i=0, 12+0 = 12^0 = 12
for i=1, 12+1 = 12^1 = 13
for i=2, 12+2 = 12^2 = 14
for i=3, 12+3 = 12^3 = 15
Method 1 (Simple) : One simple solution is to iterate over all values of i 0<= i <= n and count all satisfying values.
#include <iostream>
using namespace std;
int countValues (int n)
{
int countV = 0;
for (int i=0; i<=n; i++ )
if ((n+i) == (n^i) )
countV++;
return countV;
}
int main()
{
int n = 12;
cout << countValues(n);
return 0;
}
import java.util.*;
class GFG {
public static int countValues (int n)
{
int countV = 0;
for (int i = 0; i <= n; i++ )
if ((n + i) == (n ^ i) )
countV++;
return countV;
}
public static void main(String[] args)
{
int n = 12;
System.out.println(countValues(n));
}
}
def countValues (n):
countV = 0;
for i in range(n + 1):
if ((n + i) == (n ^ i)):
countV += 1;
return countV;
n = 12;
print(countValues(n));
using System;
class GFG {
public static int countValues (int n)
{
int countV = 0;
for (int i = 0; i <= n; i++ )
if ((n + i) == (n ^ i) )
countV++;
return countV;
}
public static void Main()
{
int n = 12;
Console.WriteLine(countValues(n));
}
}
<?php
function countValues ($n)
{
$countV = 0;
for ($i = 0; $i <= $n; $i++ )
if (($n + $i) == ($n^$i) )
$countV++;
return $countV;
}
$n = 12;
echo countValues($n);
?>
<script>
function countValues (n)
{
let countV = 0;
for (let i=0; i<=n; i++ )
if ((n+i) == (n^i) )
countV++;
return countV;
}
let n = 12;
document.write(countValues(n));
</script>
Output:
4
Time Complexity: O(n)
Space Complexity: O(1)
Method 2 (Efficient) : An efficient solution is as follows
we know that (n+i)=(n^i)+2*(n&i)So n + i = n ^ i implies n & i = 0Hence our problem reduces to finding values of i such that n & i = 0. How to find count of such pairs? We can use the count of unset-bits in the binary representation of n. For n & i to be zero, i must unset all set-bits of n. If the kth bit is set at a particular in n, kth bit in i must be 0 always, else kth bit of i can be 0 or 1Hence, total such combinations are 2^(count of unset bits in n)For example, consider n = 12 (Binary representation : 1 1 0 0).
All possible values of i that can unset all bits of n are 0 0 0/1 0/1 where 0/1 implies either 0 or 1. Number of such values of i are 2^2 = 4.
The following is the program following the above idea.
#include <bits/stdc++.h>
using namespace std;
int countValues(int n)
{
int unset_bits=0;
while (n)
{
if ((n & 1) == 0)
unset_bits++;
n=n>>1;
}
return 1 << unset_bits;
}
int main()
{
int n = 12;
cout << countValues(n);
return 0;
}
import java.util.*;
class GFG {
public static int countValues(int n)
{
int unset_bits=0;
while (n > 0)
{
if ((n & 1) == 0)
unset_bits++;
n=n>>1;
}
return 1 << unset_bits;
}
public static void main(String[] args)
{
int n = 12;
System.out.println(countValues(n));
}
}
using System;
public class GFG {
public static int countValues(int n)
{
int unset_bits=0;
while (n > 0)
{
if ((n & 1) == 0)
unset_bits++;
n=n>>1;
}
return 1 << unset_bits;
}
public static void Main(String[] args)
{
int n = 12;
Console.WriteLine(countValues(n));
}
}
def countValues(n):
unset_bits = 0
while(n):
if n & 1 == 0:
unset_bits += 1
n = n >> 1
return 1 << unset_bits
if __name__=='__main__':
n = 12
print(countValues(n))
<?php
function countValues( $n)
{
$unset_bits = 0;
while ($n)
{
if (($n & 1) == 0)
$unset_bits++;
$n = $n >> 1;
}
return 1 << $unset_bits;
}
$n = 12;
echo countValues($n);
?>
<script>
function countValues(n)
{
let unset_bits = 0;
while (n > 0)
{
if ((n & 1) == 0)
unset_bits++;
n = n >> 1;
}
return 1 << unset_bits;
}
let n = 12;
document.write(countValues(n));
</script>
Output :
4
Time Complexity: O(log(n))
Space Complexity: O(1)
This article is contributed by Nikhil Chakravartula. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to . See your article appearing on the GeeksforGeeks main page and help other Geeks.
