logo

סכום שווה ו-XOR

נסה את זה ב-GfG Practice ' title= #practiceLinkDiv { display: none !חשוב; }

בהינתן מספר שלם חיובי 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 = 15
Recommended Practice סכום שווה ו-XOR נסה את זה!

שיטה 1 (פשוטה):  
פתרון פשוט אחד הוא לחזור על כל הערכים של i 0<= i <= n and count all satisfying values.  



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) {  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(1)

שיטה 2 (יעיל): 
פתרון יעיל הוא כדלקמן

אנחנו יודעים ש-(n+i)=(n^i)+2*(n&i)
אז n + i = n ^ i מרמזים על n & i = 0
מכאן שהבעיה שלנו מצטמצמת למציאת ערכים של i כך ש-n & i = 0. איך למצוא את הספירה של זוגות כאלה? אנו יכולים להשתמש בספירת סיביות לא מוגדרות בייצוג הבינארי של n. כדי ש-n & i יהיו אפס, אני חייב לבטל את כל ה-set-bits של n. אם הביט ה-kth מוגדר ב-n kth-bit מסוים ב-i חייב להיות 0 תמיד אחרת ה-kth-bit של 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))

מורכבות החלל: O(1)

https://www.youtube.com/watch?v=zhu605v9KOI&feature=youtu.be