Given three integers A, B, and C. the task is to find the maximum possible sum of three numbers when you are allowed to perform the following operation any number of times (possibly zero):
- Choose any integer X such that X ? max( A, B, C ), and replace A with A^X, B with B^X, and C with C^X. (Here ^ denotes Bitwise XOR operation)
Examples:
Input: A = 2, B = 3, C = 5
Output: 14
Explanation: We can take X = 4, then final sum will be 6 + 7 + 1 = 14.Input: A = 2, B = 2, C = 2
Output: 9
Explanation: We can take X = 1, then final sum will be 3 + 3 + 3 = 9.
Approach: This problem can be solved using Bit-Manipulation.
The idea is to use the concept that a bit is flipped if XOR is with 1 and it remains same if XOR is with 0.
Consider every position in the three numbers and check the sum of bits. Since we want the maximum sum we want to have a maximum of 1s at each position. So if the number of 1s is greater than 0s then at that position we will use 0 in X so that there is no change. Otherwise, we will use 1 at that position in X so that number of 1s becomes equal to or greater than number of 0s and thus maximizing 1s at each position which results in a maximum sum.
Follow the steps mentioned below to implement the idea:
- Check the sum of bits at each position.
- If the sum is less than 2 then we need to flip the bits thus we need 1 at that position in X.
- Otherwise, choose 0 at that position in X.
Below is the implementation of the above approach.
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;int maxSum(int A, int B, int C){ int a = A, b = B, c = C; stack<int> s; while (a > 0 or b > 0 or c > 0) { int num = 0; num += a & 1; num += b & 1; num += c & 1; a >>= 1; b >>= 1; c >>= 1; if (num < 2) s.push(1); else s.push(0); } int x = 0; while (!s.empty()) { x <<= 1; x += s.top(); s.pop(); } return (A ^ x) + (B ^ x) + (C ^ x);}// Drivers codeint main(){ // Function Call cout << maxSum(2, 3, 5) << endl; return 0;} |
Java
// Java code for the above approach:import java.io.*;import java.util.*;class GFG { static int maxSum(int A, int B, int C) { int a = A, b = B, c = C; Stack<Integer> s = new Stack<>(); while (a > 0 || b > 0 || c > 0) { int num = 0; num += a & 1; num += b & 1; num += c & 1; a >>= 1; b >>= 1; c >>= 1; if (num < 2) { s.push(1); } else { s.push(0); } } int x = 0; while (!s.isEmpty()) { x <<= 1; x += s.peek(); s.pop(); } return (A ^ x) + (B ^ x) + (C ^ x); } public static void main(String[] args) { // Function call System.out.println(maxSum(2, 3, 5)); }}// This code is contributed by lokeshmvs21. |
Python3
# Python code for the above approach:def maxSum(A, B, C): a, b, c = A, B, C s = [] while(a > 0 or b > 0 or c > 0): num = 0 num = num + (a & 1) num = num + (b & 1) num = num + (c & 1) a = a >> 1 b = b >> 1 c = c >> 1 if(num < 2): s.append(1) else: s.append(0) x = 0 while(s): x = x << 1 x = x + s[-1] s.pop() return (A ^ x) + (B ^ x) + (C ^ x)# function callprint(maxSum(2, 3, 5))# This code is contributed by lokeshmvs21. |
C#
// C# code for the above approach:using System;using System.Collections;using System.Collections.Generic;public class GFG { static int maxSum(int A, int B, int C) { int a = A, b = B, c = C; Stack s = new Stack(); while (a > 0 || b > 0 || c > 0) { int num = 0; num += a & 1; num += b & 1; num += c & 1; a >>= 1; b >>= 1; c >>= 1; if (num < 2) { s.Push(1); } else { s.Push(0); } } int x = 0; while (s.Count != 0) { x <<= 1; x += (int)s.Peek(); s.Pop(); } return (A ^ x) + (B ^ x) + (C ^ x); } static public void Main() { // Function call Console.WriteLine(maxSum(2, 3, 5)); }}// This code is contributed by lokesh. |
Javascript
// JS code for the above approach:function maxSum(A, B, C){ let a = A, b = B, c = C; let s = []; while (a > 0 || b > 0 || c > 0) { let num = 0; num += a & 1; num += b & 1; num += c & 1; a >>= 1; b >>= 1; c >>= 1; if (num < 2) s.push(1); else s.push(0); } let x = 0; while (s.length!=0) { x <<= 1; x += s[s.length-1]; s.pop(); } return (A ^ x) + (B ^ x) + (C ^ x);}// Drivers code // Function Call console.log(maxSum(2, 3, 5)); // This code is contributed by ksam24000. |
14
Time Complexity: O(log(max(A, B, C)))
Auxiliary Space: O(log(max(A, B, C)))
Related Articles:
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
