Algorithm


Problem Name: Data Structures - AND xor OR

Problem Link: https://www.hackerrank.com/challenges/and-xor-or/problem?isFullScreen=true

In this HackerRank in Data Structures - AND xor OR solutions

Given an array A[] of N distinct elements. Let M1 and M2 be the smallest and the next smallest element in the interval [L,R] where 1 <= L <= R <= N

Input Format

First line contains integer N.

Second line contains N integers, representing elements of the array A[].

Constraints

1 <= N <= 10**6

1 <= Ai <= 10**9

Output Format

Print the value of maximum possible value of Si.

Sample Input

5
9 6 3 5 2

Sample Output

15

 

 

 

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming


#include<iostream>
#include<stack>
#include<vector>
using namespace std;
int main()
{	vector  < long int> v;
	stack  s;
	long int temp,i,n;
	long long max_xor = 0,min_xor;
	cin>>n;
	for(i = 0; i  <  n; i++)
	{
		cin >> temp;
		v.push_back(temp);
	}
	for(i = 0; i  <  n; i++)
	{
		while(!s.empty())
		{
			min_xor = v[i]^s.top();
			if(min_xor > max_xor)
			max_xor = min_xor;
			if(v[i] < s.top())
			s.pop();
			else
			break;
		}
		s.push(v[i]>;
	}
	cout << max_xor << endl;
}
Copy The Code & Try With Live Editor

#2 Code Example with Java Programming

Code - Java Programming


import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    static Stack < Long> maxValue = new Stack();
    public static void main(String[] args){
        
        Scanner sc = new Scanner(System.in);
        int number = sc.nextInt();
        
        long[] input = new long[number];
        
        for(int i=0;i < number;i++){
            input[i] = sc.nextLong();
        }
        
        maxValue.push(Long.valueOf("-1"));
        FindS(input, 0, input.length-1);
        
        if(maxValue.peek().compareTo(Long.valueOf("-1")) != 0) System.out.println(maxValue.peek());
    }
    
    static void FindS(long input[], int lower, int higher){
        int length = higher - lower;
        if(length < 1) return;
        if(length == 1){
            long result = input[lower] ^ input[lower+1];
            long stackTop = maxValue.peek(>;
            if(result > stackTop){
                maxValue.push(result);
            }
            return;
        }
        else{
            long s1 = Long.MAX_VALUE;
            long s2 = Long.MAX_VALUE;
            int s1_index = -1;
            for(int i=lower;i<=higher;i++){
                if(input[i]  <  s1){
                    s1 = input[i];
                    s1_index = i;
                }
            }
            for(int i=lower;i < =higher;i++){
                if(i != s1_index){
                    if(input[i] < s2){
                        s2 = input[i];
                    }
                }
            }
            
            
            long result = s1 ^ s2;
            long stackTop = maxValue.peek(>;
            if(result > stackTop){
                maxValue.push(result);
            }
            int n = (lower+higher)/2;
            FindS(input, lower, n);
            FindS(input, n+1, higher);
            
        }
    }
}
Copy The Code & Try With Live Editor

#3 Code Example with Javascript Programming

Code - Javascript Programming


'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', function(inputStdin) {
    inputString += inputStdin;
});

process.stdin.on('end', function() {
    inputString = inputString.split('\n');

    main();
});

function readLine() {
    return inputString[currentLine++];
}

/*
 * Complete the 'andXorOr' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts INTEGER_ARRAY a as parameter.
 */

function andXorOr(a) {

    let rangeArr = [];
    let rangeArr2 = [];
    
    let small1 = 0;
    let small2 = 0;
    
    let makeVal = 0;
    let maxVal = 0;
    
    
    for (let l = 0; l  <  a.length; l++){
        for (let r = l+1; r  <  a.length + 1; r++){
            
            
            rangeArr = a.slice(l, r + 1);
            small1 = Math.min(...rangeArr);
            
            rangeArr2 = rangeArr.filter(item => item !== small1);
            small2 = Math.min(...rangeArr2);
            
            makeVal = (((small1 & small2) ^ (small1 | small2) & (small1 ^ small2)));
            
            if (maxVal  <  makeVal){
                maxVal = makeVal;
            }
            
        }
 
    }
    return maxVal
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const aCount = parseInt(readLine().trim(), 10);

    const a = readLine().replace(/\s+$/g, '').split(' ').map(aTemp => parseInt(aTemp, 10));

    const result = andXorOr(a);

    ws.write(result + '\n');

    ws.end();
}
Copy The Code & Try With Live Editor

#4 Code Example with Python Programming

Code - Python Programming


#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'andXorOr' function below.
#
# The function is expected to return an INTEGER.
# The function accepts INTEGER_ARRAY a as parameter.
#

def andXorOr(a):
    #pA -the result of pairing a[-1] and popped
    #pStack-the result of pairing stack[-1] and popped
    stack=[a.pop()] 
    popped=a.pop()
    maxRes=pStack=pA= -1 
    while True: #
        #pairing and getting the result of the pairs:
        if stack:    
            pStack=stack[-1]^popped
        if a:
            pA=a[-1]^popped
        maxRes=max(maxRes,pA,pStack) #getting the max result so far
        if stack and stack[-1]>popped: 
            stack.pop() #
            continue
        elif not a:
            return maxRes
        elif not stack or stack[-1]a[-1]:
            pass
        popped=a.pop()

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    a_count = int(input().strip())

    a = list(map(int, input().rstrip().split()))

    result = andXorOr(a)

    fptr.write(str(result) + '\n')

    fptr.close()

Copy The Code & Try With Live Editor

#5 Code Example with C# Programming

Code - C# Programming


using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

class Solution {
    static void Main(String[] args) 
    {
        uint n = uint.Parse(Console.ReadLine());
        
        uint[] v = Array.ConvertAll(Console.ReadLine().Split(' '), uint.Parse);
        
        Stack < uint> s = new Stack();
        
        long max = 0;
        
        for (int i = 0; i  <  n; i++)
        {          
            while (s.Any())
            {
                uint c = s.Peek() ^ v[i];
                
                if (c >= max)
                {
                    max = c;
                }
                
                if (v[i]  <  s.Peek())
                {
                    s.Pop();
                }
                else
                {
                    break;
                }
            }
            
            s.Push(v[i]);
        }
        
        Console.WriteLine(max);
    }
}
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] Super Maximum Cost Queries solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
Next
[Solved] No Prefix Set solution in Hackerrank - Hacerrank solution C, C++, java,js, Python