Рівна сума та XOR
Спробуйте на GfG Practice 
#practiceLinkDiv { display: none !important; }
#practiceLinkDiv { display: none !important; } Дано натуральне число n. Знайдіть кількість натуральних чисел i таких, що 0 <= i <= n and n+i = n^i
Приклади:
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 Рівна сума та XOR Спробуйте!
Спосіб 1 (простий):
Одним із простих рішень є перебір усіх значень i 0 <= i <= n and count all satisfying values.
/* C++ program to print count of values such that n+i = n^i */ #include using namespace std ; // function to count number of values less than // equal to n that satisfy the given condition 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 int main () { int n = 12 ; cout < < countValues ( n ); return 0 ; }
Java /* 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 # 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# /* 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 // 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 ?>
JavaScript < 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>
Вихід:
4
Часова складність: O(n)
Космічна складність: О(1)
Спосіб 2 (ефективний):
Ефективним рішенням є наступне
ми знаємо, що (n+i)=(n^i)+2*(n&i)
Отже, n + i = n ^ i означає, що n & i = 0
Отже, наша задача зводиться до пошуку таких значень i, щоб n & i = 0. Як знайти кількість таких пар? Ми можемо використовувати кількість невстановлених бітів у двійковому представленні n. Щоб n & i було нульовим, я повинен скинути всі встановлені біти n. Якщо k-й біт встановлено як певний у n, k-й біт в i має бути 0, завжди інакше k-й біт i може бути 0 або 1
Отже, загальна кількість таких комбінацій становить 2^(кількість невстановлених бітів у n)
Наприклад, розглянемо n = 12 (двійкове представлення: 1 1 0 0).
Усі можливі значення i, які можуть скинути всі біти n, є 0 0 0/1 0/1, де 0/1 означає 0 або 1. Кількість таких значень i становить 2^2 = 4.
Нижче наведено програму, що відповідає вищезгаданій ідеї.
C++ /* c++ program to print count of values such that n+i = n^i */ #include using namespace std ; // function to count number of values less than // equal to n that satisfy the given condition 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 ) { if (( n & 1 ) == 0 ) unset_bits ++ ; n = n >> 1 ; } // Return 2 ^ unset_bits return 1 < < unset_bits ; } // Driver code int main () { int n = 12 ; cout < < countValues ( n ); return 0 ; }
Java /* 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# /* 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 # 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 /* 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. ?>
JavaScript < 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>
Вихід:
4
Часова складність: O(log(n))
Космічна складність: О(1)
https://www.youtube.com/watch?v=zhu605v9KOI&feature=youtu.be
Створіть вікторину
