Algorithm
Problem Name: Data Structures -
In this HackerRank in Data Structures -
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;
}
#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);
}
}
}
#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();
}
#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()
#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);
}
}