Ascending order of three integers after XOR operation
Given three distinct integers X, Y, Z. Find an integer N that after performing XOR of each element, integers must follow that X should be minimum and Z should be maximum between three integers. If possible then print the integer, Otherwise print -1.
Examples:
Input: 4, 5, 6
Output: 0
Explanation: 4 XOR 0 = 4, 5 XOR 0 = 5, 6 XOR 0 = 6, so 4 is minimum and 6 is maximum, .Input: 12, 9, 8
Output: 15
Approach: To solve the problem follow the below idea:
The approach checks if the three integers are sorted in ascending or descending order. If it is sorted in ascending order, it outputs 0, because we know that Any Number XOR 0 = That Number. If it is sorted in descending order, calculates the next positive integer of the maximum integer which is a power of 2, and prints that number -1. If the array is not sorted, it outputs -1.
- Check if the integers are sorted in ascending order by comparing X with Y and Y with Z. If it is, output 0.
- Check if the array is sorted in descending order by comparing X with Y and Y with Z. If it is, compute the next positive integer of the maximum integer which is a power of 2 minus 1 using the logarithm and power functions, and output this value.
- If the array is not sorted, output -1.
Below is the implementation of the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; void sortThreeInteger( int X, int Y, int Z, int n) { // Check if the three integers // sorted in ascending order if (X < Y && Y < Z) { // If they sorted in ascending // order, output "Yes 0" cout << 0 << endl; } // Check if the three integers are // sorted in descending order else if (X > Y && Y > Z) { // If the three integers are // sorted in descending order, // compute the smallest power of // 2 greater than the first // element minus one // Compute the logarithm of // the first element to base 2 int d = log2(X); // Compute the smallest power of // 2 greater than the logarithm int u = pow (2, d + 1); // Output "Yes" followed by // the computed value cout << u - 1 << endl; } // If the integers are not sorted, // output "No" else { cout << -1 << endl; } } // Drivers code int main() { int X = 12, Y = 9, Z = 8; // Function call sortThreeInteger(X, Y, Z, 3); return 0; } |
Java
import java.util.*; public class GFG { static void sortThreeInteger( int X, int Y, int Z, int n) { // Check if the three integers sorted in ascending order if (X < Y && Y < Z) { // If they sorted in ascending order, output "Yes 0" System.out.println( 0 ); } // Check if the three integers are sorted in descending order else if (X > Y && Y > Z) { // If the three integers are sorted in descending order, // compute the smallest power of 2 greater than the first element minus one // Compute the logarithm of the first element to base 2 int d = ( int ) (Math.log(X) / Math.log( 2 )); // Compute the smallest power of 2 greater than the logarithm int u = ( int ) Math.pow( 2 , d + 1 ); // Output "Yes" followed by the computed value System.out.println(u - 1 ); } // If the integers are not sorted, output "No" else { System.out.println(- 1 ); } } // Driver code public static void main(String[] args) { int X = 12 , Y = 9 , Z = 8 ; // Function call sortThreeInteger(X, Y, Z, 3 ); } } |
Python3
import math def sortThreeInteger(X, Y, Z, n): # Check if the three integers # sorted in ascending order if X < Y and Y < Z: # If they sorted in ascending # order, output "Yes 0" print ( 0 ) # Check if the three integers are # sorted in descending order elif X > Y and Y > Z: # Compute the logarithm of # the first element to base 2 d = math.ceil(math.log2(X)) # Compute the smallest power of # 2 greater than the logarithm u = 2 * * d # Output "Yes" followed by # the computed value print (u - 1 ) # If the integers are not sorted, # output "No" else : print ( - 1 ) # Test case X = 12 Y = 9 Z = 8 sortThreeInteger(X, Y, Z, 3 ) |
C#
using System; class Program { static void SortThreeInteger( int X, int Y, int Z) { // Check if the three integers sorted in ascending order if (X < Y && Y < Z) { // If they sorted in ascending order, output "Yes 0" Console.WriteLine(0); } // Check if the three integers are sorted in descending order else if (X > Y && Y > Z) { // If the three integers are sorted in descending order, // compute the smallest power of 2 greater than the first element minus one // Compute the logarithm of the first element to base 2 int d = ( int )Math.Log(X, 2); // Compute the smallest power of 2 greater than the logarithm int u = ( int )Math.Pow(2, d + 1); // Output "Yes" followed by the computed value Console.WriteLine(u - 1); } // If the integers are not sorted, output "No" else { Console.WriteLine(-1); } } static void Main( string [] args) { int X = 12, Y = 9, Z = 8; // Function call SortThreeInteger(X, Y, Z); } } //Contributed by Aditi Tyagi |
Javascript
function sortThreeInteger(X, Y, Z, n) { // Check if the three integers // sorted in ascending order if (X < Y && Y < Z) { // If they sorted in ascending // order, output "Yes 0" console.log(0); } // Check if the three integers are // sorted in descending order else if (X > Y && Y > Z) { // Compute the logarithm of // the first element to base 2 let d = Math.ceil(Math.log2(X)); // Compute the smallest power of // 2 greater than the logarithm let u = Math.pow(2, d ); // Output "Yes" followed by // the computed value console.log(u - 1); } // If the integers are not sorted, // output "No" else { console.log(-1); } } // Test case let X = 12, Y = 9, Z = 8; sortThreeInteger(X, Y, Z, 3); |
15
Time Complexity: O(1)
Auxiliary Space: O(1)