LIK SUM OG XOR

Prøv det på GfG Practice

#practiceLinkDiv { display: ingen !viktig; }

Gitt et positivt heltall n finn antall positive heltall i slik at 0 <= i <= n and n+i = n^i

Eksempler:

  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 Lik sum og XOR Prøv det!

Metode 1 (enkel):
En enkel løsning er å iterere over alle verdiene til 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# 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>

Produksjon:

Tidskompleksitet: På)

Plass kompleksitet: O(1)

Metode 2 (effektiv):
En effektiv løsning er som følger

vi vet at (n+i)=(n^i)+2*(n&i)
Så n + i = n ^ i innebærer n & i = 0
Derfor reduseres problemet vårt til å finne verdier av i slik at n & i = 0. Hvordan finne antall slike par? Vi kan bruke antallet ikke-innstilte biter i den binære representasjonen av n. For at n & i skal være null, må jeg deaktivere alle sett-biter av n. Hvis den kth biten er satt til en bestemt i n kth bit i i må alltid være 0 ellers kan kth bit av i være 0 eller 1
Derfor er totalt slike kombinasjoner 2^(antall ikke-innstilte biter i n)
Tenk for eksempel på n = 12 (Binær representasjon: 1 1 0 0).
Alle mulige verdier av i som kan deaktivere alle biter av n er 0 0 0/1 0/1 der 0/1 betyr enten 0 eller 1. Antall slike verdier av i er 2^2 = 4.

Følgende er programmet som følger ideen ovenfor.

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# 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>