Company: Rakuten
Difficulty: medium
Maximum possible score Problem Description Mike has been gifted an array A of size N on his birthday. The array A is indexed from 1 to N . He comes up with a game. The player has to select an index K ( 1 ≤ K ≤ N ) by which another array B of size N is formed where the i -th element of B is the bitwise XOR ( ^ ) of A_i and A_K such that B_i = (A_i ^ A_K) . The score S of the player is the sum of all elements of array B that is S = ∑ i=1 N B i . Before going out to play with his friends he wants to know the maximum possible score a player can achieve. Examples Example 1: Input: N = 3, A = [15, 11, 8] Output: 11 Explanation: We need to choose an index K from 1 to N (which is 1 to 3 in this case) to maximize the sum of B_i = A_i ^ A_K . If we choose K = 1 (so A_K = A_1 = 15 ): B_1 = A_1 ^ A_1 = 15 ^ 15 = 0 B_2 = A_2 ^ A_1 = 11 ^ 15 = 4 B_3 = A_3 ^ A_1 = 8 ^ 15 = 7 The score S = 0 + 4 + 7 = 11 . If we choose K = 2 (so A_K = A_2 = 11 ): B_1 = A_1 ^ A_2 = 15 ^ 11 = 4 B_2 = A_2 ^ A_2