#practiceLinkDiv { display: none !important; }Biorąc pod uwagę dodatnią liczbę całkowitą n, znajdź liczbę dodatnich liczb całkowitych i takich, że 0<= i <= n and n+i = n^i
Przykłady:
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 = 15Recommended Practice Równa suma i XOR Spróbuj!
Metoda 1 (prosta):
Jednym z prostych rozwiązań jest iteracja po wszystkich wartościach i 0<= i <= n and count all satisfying values.
C++
/* C++ program to print count of values such that n+i = n^i */ #include
/* Java program to print count of values such that n+i = n^i */ import java.util.*; class GFG { // function to count number of values // less than equal to n that satisfy // the given condition public static int countValues (int n) { int countV = 0; // Traverse all numbers from 0 to n // and increment result only when // given condition is satisfied. for (int i = 0; i <= n; i++ ) if ((n + i) == (n ^ i) ) countV++; return countV; } /* Driver program to test above function */ public static void main(String[] args) { int n = 12; System.out.println(countValues(n)); } } // This code is contributed by Arnav Kr. Mandal.
# Python3 program to print count # of values such that n+i = n^i # function to count number # of values less than # equal to n that satisfy # the given condition def countValues (n): countV = 0; # Traverse all numbers # from 0 to n and # increment result only # when given condition # is satisfied. for i in range(n + 1): if ((n + i) == (n ^ i)): countV += 1; return countV; # Driver Code n = 12; print(countValues(n)); # This code is contributed by mits
/* C# program to print count of values such that n+i = n^i */ using System; class GFG { // function to count number of values // less than equal to n that satisfy // the given condition public static int countValues (int n) { int countV = 0; // Traverse all numbers from 0 to n // and increment result only when // given condition is satisfied. for (int i = 0; i <= n; i++ ) if ((n + i) == (n ^ i) ) countV++; return countV; } /* Driver program to test above function */ public static void Main() { int n = 12; Console.WriteLine(countValues(n)); } } // This code is contributed by anuj_67.
// PHP program to print count // of values such that n+i = n^i // function to count number // of values less than // equal to n that satisfy // the given condition function countValues ($n) { $countV = 0; // Traverse all numbers // from 0 to n and // increment result only // when given condition // is satisfied. for ($i = 0; $i <= $n; $i++ ) if (($n + $i) == ($n^$i) ) $countV++; return $countV; } // Driver Code $n = 12; echo countValues($n); // This code is contributed by m_kit ?> <script> /* JavaScript program to print count of values such that n+i = n^i */ // function to count number of values less than // equal to n that satisfy the given condition function countValues (n) { let countV = 0; // Traverse all numbers from 0 to n and // increment result only when given condition // is satisfied. for (let i=0; i<=n; i++ ) if ((n+i) == (n^i) ) countV++; return countV; } // Driver program let n = 12; document.write(countValues(n)); // This code is contributed by Surbhi Tyagi. </script>
Wyjście:
4
Złożoność czasowa: NA)
Złożoność przestrzeni: O(1)
Metoda 2 (wydajna):
Skuteczne rozwiązanie jest następujące
wiemy, że (n+i)=(n^i)+2*(n&i)
Zatem n + i = n ^ i implikuje n i i = 0
Stąd nasz problem sprowadza się do znalezienia wartości i takich, że n & i = 0. Jak znaleźć liczbę takich par? Możemy użyć liczby nieustawionych bitów w binarnej reprezentacji n. Aby n i i wynosiło zero, muszę rozbroić wszystkie ustawione bity n. Jeśli k-ty bit jest ustawiony na konkretną wartość w n, k-ty bit w i musi wynosić 0, w przeciwnym razie k-ty bit i może wynosić 0 lub 1
Stąd całkowita liczba takich kombinacji wynosi 2^(liczba nieustawionych bitów w n)
Rozważmy na przykład n = 12 (reprezentacja binarna: 1 1 0 0).
Wszystkie możliwe wartości i, które mogą rozbroić wszystkie bity n, to 0 0 0/1 0/1, gdzie 0/1 oznacza 0 lub 1. Liczba takich wartości i to 2^2 = 4.
Poniżej znajduje się program bazujący na powyższym pomyśle.
C++/* c++ program to print count of values such that n+i = n^i */ #include
/* Java program to print count of values such that n+i = n^i */ import java.util.*; class GFG { // function to count number of values // less than equal to n that satisfy // the given condition public static int countValues(int n) { // unset_bits keeps track of count // of un-set bits in binary // representation of n int unset_bits=0; while (n > 0) { if ((n & 1) == 0) unset_bits++; n=n>>1; } // Return 2 ^ unset_bits return 1 << unset_bits; } /* Driver program to test above function */ public static void main(String[] args) { int n = 12; System.out.println(countValues(n)); } } // This code is contributed by Arnav Kr. Mandal.
/* C# program to print count of values such that n+i = n^i */ using System; public class GFG { // function to count number of values // less than equal to n that satisfy // the given condition public static int countValues(int n) { // unset_bits keeps track of count // of un-set bits in binary // representation of n int unset_bits=0; while (n > 0) { if ((n & 1) == 0) unset_bits++; n=n>>1; } // Return 2 ^ unset_bits return 1 << unset_bits; } /* Driver program to test above function */ public static void Main(String[] args) { int n = 12; Console.WriteLine(countValues(n)); } } // This code is contributed by umadevi9616
# Python3 program to print count of values such # that n+i = n^i # function to count number of values less than # equal to n that satisfy the given condition def countValues(n): # unset_bits keeps track of count of un-set # bits in binary representation of n unset_bits = 0 while(n): if n & 1 == 0: unset_bits += 1 n = n >> 1 # Return 2 ^ unset_bits return 1 << unset_bits # Driver code if __name__=='__main__': n = 12 print(countValues(n)) # This code is contributed by rutvik
/* PHP program to print count of values such that n+i = n^i */ // function to count number of // values less than equal to n // that satisfy the given // condition function countValues( $n) { // unset_bits keeps track // of count of un-set bits // in binary representation // of n $unset_bits = 0; while ($n) { if (($n & 1) == 0) $unset_bits++; $n = $n >> 1; } // Return 2 ^ unset_bits return 1 << $unset_bits; } // Driver code $n = 12; echo countValues($n); // This code is contributed // by Anuj_67. ?> <script> // Javascript program to print count of values // such that n+i = n^i // Function to count number of values // less than equal to n that satisfy // the given condition function countValues(n) { // unset_bits keeps track of count // of un-set bits in binary // representation of n let unset_bits = 0; while (n > 0) { if ((n & 1) == 0) unset_bits++; n = n >> 1; } // Return 2 ^ unset_bits return 1 << unset_bits; } // Driver Code let n = 12; document.write(countValues(n)); // This code is contributed by susmitakundugoaldanga </script>
Wyjście :
4
Złożoność czasowa: O(log(n))
Złożoność przestrzeni: O(1)
https://www.youtube.com/watch?v=zhu605v9KOI&feature=youtu.be