A XOR operation

You are given a set $S$ of distinct positive integers of size $n$ ($n$ is always even). Print the minimum positive integer $k$ that is greater than 0 such that after replacing each element $e$ of the set $S$ with $e\oplus k$, set $S$ remains the same.

Print -1 if there is no such $k$.

Example:

Input:  n = 6, a[] = { 5, 6, 9, 10, 13, 14 }
Output: 3

Approach

Java

import java.io.IOException;
import java.util.HashSet;
import java.util.Set;

public class XORTest {
    public static void main(String[] args) throws IOException {
        int t = 1;
        int n = 6;
        int a[] = { 5, 6, 9, 10, 13, 14 };
        System.out.println(getKay(a, n));
    }

    private static int getKay(int[] a, int n) {
        int b[] = new int[32];
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < n; i++) {
            int temp = a[i];
            set.add(temp);
            for (int j = 0; j < 32; j++)
                b[j] += ((temp >> j) & 1);
        }

        for (int i = 0; i < 32; i++)
            b[i] %= 2;

        int ans = 0;
        for (int i = 0; i < 32; i++)
            if (b[i] != 0)
                ans += (int) Math.pow(2, i);

        if (ans == 0)
            return -1;
        for (int i = 0; i < n; i++)
            if (!set.contains(a[i] ^ ans))
                return -1;
        return ans;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

int getKay(vector<int> a, int n)
{
    int b[32];
    for (int i = 0; i < 32; i++)
        b[i] = 0;
    set<int> st;
    for (int i = 0; i < n; i++)
    {
        int temp = a[i];
        st.insert(temp);
        for (int j = 0; j < 32; j++)
        {
            b[j] += ((temp >> j) & 1);
        }
    }

    for (int i = 0; i < 32; i++)
    {
        b[i] %= 2;
    }

    int ans = 0;
    for (int i = 0; i < 32; i++)
    {
        if (b[i] != 0)
            ans += pow(2, i);
    }

    if (ans == 0)
        return -1;
    for (int i = 0; i < n; i++)
    {
        //if not in set then return -1
        if (st.find(a[i] ^ ans) == st.end())
            return -1;
    }
    return ans;
}

int main()
{
    int n = 6;
    vector<int> a = {5, 6, 9, 10, 13, 14};
    cout << getKay(a, n) << "\n";
}

Do you really understand binary search ?

Your seniors from Programming Club made a lot of effort in teaching you binary search. They are looking forward to seeing a lot of accepted solutions to this problem. They might even treat everyone who solves this one.

You are given a set of parallel lines having slope -1 on the 2D coordinate. None of the parallel lines are overlapping. All the lines have a positive integral y-intercept (y-intercept is the y coordinate of the point where x co-ordinate is 0).

It is assumed that the point does not lie on any of the lines.

Example:

Input:  arr[] = { 5, 3 }, x = 3, y = 1
Output: 1

Approach

Java

import java.util.Arrays;

public class BinarySearch2 {

    public static void main(String[] args) throws Exception {
        int arr[] = { 5, 3 };
        Arrays.sort(arr);
        int x = 3;
        int y = 1;
        int intercept = x + y;
        int floor = binarySearch(arr, intercept, arr.length);
        System.out.println(floor + 1);
    }

    static int binarySearch(int arr[], int intercept, int n) {
        int lb = 0;
        int ub = arr.length - 1;
        while (lb <= ub) {
            int mid = lb + (ub - lb) / 2;
            if (arr[mid] == intercept) {
                return mid;
            } else if ((arr[mid] < intercept) && 
     (mid == n - 1 || arr[mid + 1] > intercept)) {
                return mid;
            } else if ((arr[mid] > intercept) && 
      (mid == 0 || arr[mid - 1] < intercept)) {
                return mid - 1;
            } else if (arr[mid] > intercept) {
                ub = mid - 1;
            } else {
                lb = mid + 1;
            }
        }
        return -1;
    }

}

C++

#include <bits/stdc++.h>
using namespace std;

int binarySearch(vector<int> arr, int intercept, int n)
{
    int lb = 0;
    int ub = arr.size() - 1;
    while (lb <= ub)
    {
        int mid = lb + (ub - lb) / 2;
        if (arr[mid] == intercept)
        {
            return mid;
        }
        else if ((arr[mid] < intercept) && (mid == n - 1 || 
                 arr[mid + 1] > intercept))
        {
            return mid;
        }
        else if ((arr[mid] > intercept) && (mid == 0 || 
                 arr[mid - 1] < intercept))
        {
            return mid - 1;
        }
        else if (arr[mid] > intercept)
        {
            ub = mid - 1;
        }
        else
        {
            lb = mid + 1;
        }
    }
    return -1;
}

int main()
{
    vector<int> arr = {5, 3};

    sort(arr.begin(), arr.end());
    int x = 3;
    int y = 1;
    int intercept = x + y;
    int floor = binarySearch(arr, intercept, arr.size());
    cout << floor + 1 << "\n";

    return 0;
}

Solve Me And Get Marks

The problem setter loves movies but you want marks, after all, you have to pass. Listening to your second year, and not taking any advice from third and fourth-year seniors, you cheated in your exam. Now you are worried if you will be caught and run to your problem setter, who is a third-year senior. He tells you not to worry. You should only worry if your paper will go through a plagiarism test.  

The good thing about IIITA this year is that there is a strange law about plagiarism checking. If there are N students in the course, and the score of the ith student is X, then his paper is subjected to plagiarism if and only if there is at least 1 more student whose score lies in the interval [ X-K, X+K ], both included.  

The Profs like to call this number K as NoMercy Value. 

Now, you have all the details regarding the above checking. You know N, number of students taking that course, K =  the Mercy value set by the Prof and the marks scored by all N students. 

You want to find how many students should actually take the pressure of getting caught in the plagiarism test and how many students should simply sit back and relax. You also want to print these values with a message as shown in the sample output. 

Example:

Input: noMercy = 6;  marksArray = { 100, 9, 10, 15, 1 };
Output: 3 students need to worry!
        2 students should relax!

Approach

Java

import java.io.IOException;
import java.util.Arrays;

public class SolveMeAndGetMarks {
    public static void main(String[] args) throws IOException {
        int noMercy = 6;
        int[] marksArray = { 100, 9, 10, 15, 1 };
        Arrays.sort(marksArray);
        int noWorry = 0;
        for (int i = 0; i < marksArray.length; i++) {
            if (i == 0) {
                if (marksArray[0] + noMercy < marksArray[1])
                    noWorry++;
            } else if (i == marksArray.length - 1) {
                if (marksArray[marksArray.length - 1] - noMercy >
                   marksArray[marksArray.length - 2])
                    noWorry++;
            } else if (marksArray[i] - noMercy >
              marksArray[i - 1] && 
               marksArray[i] + noMercy < marksArray[i + 1])
                noWorry++;
        }
        System.out.println(marksArray.length - noWorry 
                   + " students need to worry!");
        System.out.println(noWorry +
         " students should relax!");
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int noMercy = 6;
    vector<int> marksArray = {100, 9, 10, 15, 1};
    sort(marksArray.begin(), marksArray.end());
    int noWorry = 0;
    for (int i = 0; i < marksArray.size(); i++)
    {
        if (i == 0)
        {
            if (marksArray[0] + noMercy < marksArray[1])
                noWorry++;
        }
        else if (i == marksArray.size() - 1)
        {
            if (marksArray[marksArray.size() - 1] - noMercy > 
      marksArray[marksArray.size() - 2])
                noWorry++;
        }
        else if (marksArray[i] - noMercy > marksArray[i - 1] && 
       marksArray[i] + noMercy < marksArray[i + 1])
            noWorry++;
    }
    cout << marksArray.size() - noWorry 
           << " students need to worry!\n";
    cout << noWorry << " students should relax!\n";

    return 0;
}

Will she accept him?

A love Guru determines "whether a guy's proposal is going to be accepted by his crush or not" just by doing some mysterious calculation on their names, but it takes too much time for him. So, he hired you as a programmer and now your task is to write a program that helps the Guru.

He reveals his mystery with you and that is:

If the guy's name is a subsequence of his crush's name, then she is going to accept him, otherwise, she will reject him. 

Example:

Input:  s1 = "rahul"; s2 = "allgirlsallhunontheplanet";
Output: Love you too

Approach

Java

public class WillsheAccept {
    public static void main(String args[]) throws Exception {

        String s1 = "rahul";
        String s2 = "allgirlsallhunontheplanet";
        if (checkSubsequence(s1, s2)) {
            System.out.println("Love you too");
        } else {
            System.out.println("We are only friends");
        }
    }

    static boolean checkSubsequence(String s1, String s2) {
        int currentIndex = 0;
        for (int index = 0; index < s1.length(); index++) {
            char currentChar = s1.charAt(index);
            currentIndex = s2.indexOf(currentChar, currentIndex);
            if (currentIndex == -1) {
                return false;
            }
        }
        return true;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

bool checkSubsequence(string s1, string s2)
{
    int currentIndex = 0;
    for (int index = 0; index < s1.length(); index++)
    {
        char currentChar = s1[index];
        currentIndex = s2.find(currentChar, currentIndex);
        if (currentIndex == -1)
        {
            return false;
        }
    }
    return true;
}
int main()
{

    string s1 = "rahul";
    string s2 = "allgirlsallhunontheplanet";
    if (checkSubsequence(s1, s2))
        cout << "Love you too\n";
    else
        cout << "We are only friends\n";

    return 0;
}