The Castle Gate

• Problem Description

  
  Gudi, a fun loving girl from the city of Dun, travels to Azkahar - a strange land beyond the mountains. She arrives at the gates of Castle Grey, owned by Puchi,the lord of Azkahar to claim the treasure that it guards. However, destiny has other plans for her as she has to move through floors, crossing obstacles on her way to reach the treasure.
  The gates of the castle are closed. An integer N is engraved on the gates. A writing on the wall says
  Tap the gates as many times as there are unordered pairs of distinct integers from 1 to N whose bit-wise XOR does not exceed N
  Help her find the number of the times she has to tap.
  
  Input:
  First line contains an integer T
  T testcases follow.
  Each testcase consists of an integer N
  
  Output:
  Print the answer to each testcase in a newline.
  
  
  Explanation
  For N=4, pairs are (1,2) , (1,3) and (2,3)

• CODING ARENA

• def ans():

      for _ in range(int(input())):

          n=int(input())

          if(n<3):

              yield 0

          else:

                  m=1<<(n.bit_length()-1)

                  yield ((m-1)*(m-2)+3*(n-m+1)*(n-m))//2

  print(*ans(),sep="\n")

• Test Case 1

  
  Input (stdin)

  3
  
  4
  
  6
  
  8
  
  

  Expected Output

  3
  
  12
  
  21

• Test Case 2

  
  Input (stdin)

  5
  
  6
  
  10
  
  20
  
  26
  
  12
  
  

  Expected Output

  12
  
  30
  
  135
  
  270
  
  51

✖

Share this Posts

• Share To Facebook Share To Twitter Share To Pinterest Share To Whatsapp Share To Linkedin Share To Tumblr Share To Telegram Share To Reddit Share To Gmail

Subscribe Our Newsletter