Find first non repeating character from a string

Given a string find first non repeating character from a string.

We can use HashMap to find the duplicates. To find out first non repeated character, iterate the string to find character which is not repeated. 
 

public class Solution{
    public static void FindFirstNonRepeatingChar(String input){
        if(input.length() > 0){
            HashMap charMap = new HashMap<>();
            for(char ch : input.toCharArray()){
                if(charMap.containsKey(ch))
                    charMap.put(ch, Boolean.TRUE);
                else
                    charMap.put(ch, Boolean.FALSE);
            }

            for (char ch : input.toCharArray()){
                if(charMap.get(ch) == Boolean.FALSE) {
                    System.out.println("First Non Repeating Character : " + ch);
                    return;
                }
            }
        }
        System.out.println("Couldn't find Non Repeating Character");
    }

    public static void main(String[] args){
        FindFirstNonRepeatingChar("asdffdsa");
    }
}

Comments are welcome.

Find out maximum of subarry

Given an array and an size of sub array as k, find out maximum for every contiguous subarray of size k.
The problem looks simple but brute force would require n * k complexity to find out max in every subarray of length k.
We can improve complexity by introducing simple check as below 

• First find max in array of length k.
• For every next element in array post length k, check if its maximum than current max, if yer it becomes new max of current sub array.
• If not then we need new max of current sub array... repeat step 2 & 3 this till end of array.

Worst case complexity of this approach would be n *k.

Code below implements this approach.

  
//Maximum of subarray
public class Solution {
    private static int FindMax(int[] input, int k, int start){
        if(start >= 0) {
            int max_index = start;
            for (int i = start; (i < input.length) && i < start + k; i++) {
                if (input[i] > input[max_index])
                    max_index = i;
            }
            return max_index;
        }
        return -1;
    }

    public static void MaxOfSubArrays(int [] input, int k) {
        if(input.length > k) {
            int max_index = FindMax(input, k, 0);
            int max = input[max_index];

            System.out.print(max + " ");

            for (int i = k; i < input.length; i++) {
                if (input[i] > max) {
                    max = input[i];
                    max_index = i;
                }
                else if (max_index <= i-k ) {
                    max_index = FindMax(input, k, i+1 - k);
                    max = input[max_index];
                }

                System.out.print(max + " ");
            }
        }
    }
    public static void main(String[] args){
        int [] input = {9, 8, 7, 6, 5, 12, 10, 3, 11};
        MaxOfSubArrays(input, 3);
    }
}

Comments are welcome.

Expression evaluator

Given list of expressions

a = 10
b = a + 1
c = a + b
d = c * b + a * c

Print out value of last variable (in our example, it is d). 

First we would need a expression evaluator which will evaluate individual expression. 
Solution below uses two stacks for expression evaluation one for operator and one for operand. First we evaluate operations such as *, / which are high priority then evaluate +, - and = operators in second pass.

//The code below considers
//1. Only int values
//2. Only supports +, -, *, /, = operators  
public class Solution{

    private HashMap VarMap;
    Stack operandStack;
    Stack operatorStack;

    public  Solution(){
        VarMap = new HashMap<>();
        operandStack = new Stack<>();
        operatorStack = new Stack<>();
    }

    public int EvaluateExpression(String statement){
        return Evaluator(statement.replace(" ", ""));
    }

    private int GetNextOperand(String expression, int start){
        int i = start;
        for(; i < expression.length(); i++){
            char operator = expression.charAt(i);
            if(operator =='+' || operator == '-' || operator== '/' || operator == '*' || operator == '=')
               break;
        }
        return i;
    }

    private int EvaluateHighPriorityOpearators(){
        if(operatorStack.empty())
            return 0;
        char lastOperator = operatorStack.peek();
        switch (lastOperator){
            case '+':
            case '-':
                break;
            case '*': {
                String operand2 = operandStack.pop();
                String operand1 = operandStack.pop();

                String resultStr = operand1 + "*" + operand2;
                int result = VarMap.get(operand1) * VarMap.get(operand2);
                VarMap.put(resultStr, result);
                operandStack.push(resultStr);
                operatorStack.pop();
                return result;
            }
            case '/': {
                String operand2 = operandStack.pop();
                String operand1 = operandStack.pop();

                String resultStr = operand1 + "/" + operand2;
                int result = VarMap.get(operand1) / VarMap.get(operand2);
                VarMap.put(resultStr, result);
                operandStack.push(resultStr);
                operatorStack.pop();
                return result;
            }
        }
        return 0;
    }

    private int EvaluateNormalPriorityOperators() {
        if (operandStack.empty())
            return 0;
        int result = 0;
        if( VarMap.containsKey(operandStack.peek()) )
            result = VarMap.get(operandStack.pop());
        else
            result = Integer.parseInt(operandStack.pop());

        while (!operatorStack.empty()) {
            char lastOperator = operatorStack.pop();
            String operand1 = operandStack.pop();
            int val = 0;
            if (VarMap.containsKey(operand1))
                val = VarMap.get(operand1);
            else
                if(lastOperator != '=')
                    val = Integer.parseInt(operand1);

            switch (lastOperator) {
                case '+':
                    result += val;
                    break;
                case '-':
                    result -= val;
                    break;
                case '=':
                    VarMap.put(operand1, result);
                    break;
            }
        }
        return result;
    }

    private int Evaluator(String expression){
        int result = 0;
        String operand = "";
        char operator = ' ';
        for(int start = 0; start < expression.length(); ){
            int i = GetNextOperand(expression, start);
            operand = expression.substring(start, i);
            operandStack.push(operand);
            result = EvaluateHighPriorityOpearators();
            if (i < expression.length()){
                operator = expression.charAt(i);
                operatorStack.push(operator);
            }
            start = i + 1;
        }

        if(!operandStack.isEmpty()){
            result = EvaluateNormalPriorityOperators();
        }
        return result;
    }

    public static void main(String[] args) {
        List input = new ArrayList<>();
        input.add("a = 10");
        input.add("b = a + 1");
        input.add("c = a + b");
        input.add("d = c * b + a * b");

        Solution sol = new Solution();

        for (int i = 0; i < input.size()-1; i++){
            sol.EvaluateExpression(input.get(i));
        }
        System.out.println(sol.EvaluateExpression(input.get(input.size()-1)));
    }
}

//Output of above code
341

Question referenced from geeksforgeeks
Comments are welcome.

Find out order between characters from given dictionary words

Given a dictionary of unknown language and characters. Find out order between characters.
Example : "ab", "bbd", "bed", "bcd", "ce", "de"
Output : a, b, e, c, d

Finding out the sorting order using brute force would be tedious task. We can use topological sorting for this.

We will create a graph having characters as node in graph and have edge between two character if any character appear next to other character. 

Solution below implements full topological sorting approach, where we create a graph and then search the character order using topological sorting.
Graph uses adjacency list implementation.

class Graph{
    int V;
    int vCnt;

    class Node{
        public char data;
        public Node next;

        public Node(char ch, Node nxt){
            data = ch;
            next = nxt;
        }
    }

    Node[] adj;

    public Graph(int v){
        V = v;
        vCnt = 0;
        adj = new Node[v];
    }

    public void AddEdge(char v, char w){
        Node n = SearchNode(v);
        while (n.next != null){
            if(n.next.data == w)
                return;
            n = n.next;
        }
        n.next = new Node(w, null);
        Node m = SearchNode(w);
    }

    private Node SearchNode(char ch){
        for (int i = 0; i < vCnt; i++){
            if(adj[i].data == ch){
                return adj[i];
            }
        }
        adj[vCnt] = new Node(ch, null);
        vCnt++;
        return adj[vCnt-1];
    }

    private void TopologicalUtil(char ch, HashMap visited, Stack stack){
        visited.put(ch, Boolean.TRUE);
        Node n = SearchNode(ch);
        while (n.next != null){
            if(visited.get(n.next.data) == Boolean.FALSE )
                TopologicalUtil(n.next.data, visited, stack);
            n = n.next;
        }
        stack.push(ch);
    }

    public void TopologicalSort(){
        Stack stack = new Stack();
        HashMap visited = new HashMap();
        for(int i = 0; i < vCnt; i++ ){
            visited.put(adj[i].data,Boolean.FALSE);
        }

        for(int i = 0; i < vCnt; i++ ){
            if(visited.get(adj[i].data) == Boolean.FALSE )
                TopologicalUtil(adj[i].data, visited, stack);
        }

        while (!stack.isEmpty()){
            System.out.print(stack.pop() + ", ");
        }
    }
}

public class Solution{

    public static void main(String[] args) {
        List input = new ArrayList<>();
        input.add("ab");
        input.add("bbd");
        input.add("bed");
        input.add("bcd");
        input.add("ce");
        input.add("de");

        Graph g = new Graph(5);

        for (int i = 0; i < input.size()-1; i++) {
            String str = input.get(i);
            String str2 = input.get(i+1);
            if(str.charAt(0) != str2.charAt(0)) {
                char v = str.charAt(0);
                char w = str2.charAt(0);
                g.AddEdge(v, w);
            }
        }

        for (int i = 0; i < input.size()-1; i++){
            String str = input.get(i);
            String str2 = input.get(i+1);
            if(str.charAt(0) == str2.charAt(0)) {
                for (int j = 1; j < Math.min(str.length(), str2.length()); j++) {
                    if(str.charAt(j) != str2.charAt(j)) {
                        char v = str.charAt(j);
                        char w = str2.charAt(j);
                        g.AddEdge(v, w);
                    }
                }
            }
        }

        g.TopologicalSort();
    }
}

Problem referenced from geeksforgeeks.

Find minimum string containing given pattern

Given two string input and pattern. Find minimum window in input which contains all characters from string pattern. E.g : Consider input as "axcerdndnfdkgdfgn" and pattern as "ngdf". Pattern can be found at two instances 8 -12 or 13-16 indices. So minimum sliding windows becomes 13-16.


If there is single instance then problem becomes simple but if there are multiple instances we would need minimum of those.

 
//Below code first find sliding windows then finds minimum of those.
class Solution {

    public  int startIndex;
    public  int min;
    public  int max;

    public boolean getSlidingWindow(String input, String pattern){
        max = -1;
        HashMap charSet = new HashMap();

        for(char ch : pattern.toCharArray()){
            charSet.put(ch, 0);
        }

        PriorityQueue pq1 = new PriorityQueue();

        int soFarCharacters = charSet.size();
        int count = startIndex;
        for (; count < input.length() ; count++){
            char ch = input.charAt(count);
            if(charSet.containsKey(ch)){
                int value = charSet.get(ch);
                if(value == 0){
                    charSet.put(ch, 1);
                    soFarCharacters--;
                }

                if(pq1.size() > 0 && input.charAt(pq1.peek()) == ch ){
                    pq1.poll();
                }
                pq1.offer(count);
                if(count > max) max = count;
            }
            if(soFarCharacters == 0)
                break;
        }
        startIndex = count;
        if(soFarCharacters == 0) {
            min = pq1.peek();
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        String input = "axcerdndnfdkgdfgn";
        String pattern = "ngdf";

        int start = 0;
        int end = input.length();
        boolean found = false;

        Solution sol = new Solution();
        sol.startIndex = 0;
        sol.min = input.length();
        sol.max = -1;

        while (sol.getSlidingWindow(input, pattern )){
            if(end - start > sol.max - sol.min){
                end = sol.max;
                start = sol.min;
            }
            found = true;
        }
        if(found)
            System.out.println("Minimum Sliding Window : " + start + " To " + end);
    }
}

//Output of above code
Minimum Sliding Window : 13 To 16

Question referenced from geeksforgeeks

Valentine's Day Gift

Roman loved diamonds. Monica decided to give him a beautiful gift on Valentine's Day. Her idea of diamonds was different though. She lit up all the windows of her rectangular building with N floors and M windows on each floor, with 2 shapes - / or \ . According to her, a diamond was made when such a shape was created:

/ \ 
\ /

Given the shape of lights in all the windows, help Roman count the number of diamonds formed. Note: The components of the diamond should be adjacent to each other. Input: First line contains T - the number of testcases. For each testcase, First line contains 2 space-separated positive integers - N and M - the no. of floors in the building and the no. of windows on each floor respectively. N lines follow - each line contains M space-separated characters. Every character is either \ or / . Output: Print a single integer - the total no. of diamonds formed. Constraints: 1 ≤ T ≤ 5 2 ≤ N, M ≤ 1000 Sample Input(Plaintext Link)

 1
2 4
/ \ / \
\ / \ /

Output:
2

Solutions

 public class Solution {  
   public static void main(String[] args) throws IOException {  
     Scanner in = new Scanner(System.in);  
     int t;  
     t = in.nextInt();  
     int m, n;  
     for (int i = 0; i < t; i++) {  
       n = in.nextInt();  
       m = in.nextInt();  
       String[][] st1 = new String[n][m];  
       in.nextLine();  
       for (int j = 0; j < n; j++) {  
         st1[j] = in.nextLine().split(" ");  
       }  
       int count = 0;  
       for (int j = 0; j < n - 1; j++) {  
         for (int k = 0; k < m - 1; k++) {  
           if (st1[j][k].equals("/") && st1[j][k + 1].equals("\\")) {  
             if (st1[j + 1][k].equals("\\") && st1[j + 1][k + 1].equals("/")) {  
               count++;  
             }  
           }  
         }  
       }  
       System.out.println(count);  
     }  
   }  
 }  

Comments are welcome.

Find path having maximum gold in matrix

Given a gold mine of n*m dimension. Each field in this mine contains an integer which is amount of gold in tons. Initially miner is in first column but could be at any row i. He can move only right, right up , right down. Find out maximum amount of gold he can collect.

Approach 1: Brute force

For every row find all possible paths and calculate the maximum gold. Find all the paths recursively and return maximum gold.

Approach 2: Dynamic Programming

During brute force approach we search same path multiple times, instead we can store the result and reuse the result for next iterations.

Code below implements approach 2.

class Solution {

    private static boolean isValidMove(int x, int y, int[][] matrix){
        if(x >= 0 && y >= 0){
            if(x < matrix.length && y < matrix[0].length ){
                return true;
            }
        }
        return false;
    }

    public static int findMaxGold(int[][] mines, int x, int y, int[][] storage){
        if(isValidMove(x, y, mines)){
            if(storage[x][y] != -1)
                return  storage[x][y];
            int rightGold = mines[x][y] + findMaxGold(mines, x, y+1, storage);
            int rightUpGold = mines[x][y] + findMaxGold(mines, x-1, y+1, storage);
            int rightDownGold = mines[x][y] + findMaxGold(mines, x+1, y+1, storage);
            int max = Math.max(rightGold, Math.max(rightDownGold, rightUpGold));
            storage[x][y] = max;
            return max;
        }
        return 0;
    }

    public static void main(String[] args) {
        int[][] mines ={{1, 3, 5, 19},
                         {2, 5, 6, 8},
                         {9, 6, 6, 12},
                         {14, 2, 4, 22},
                         {0,  2, 4, 32}};
        int maxGold = Integer.MIN_VALUE;
        int[][] storage = new int [mines.length][mines[0].length];
        for (int i=0; i < storage.length; i++) {
            for(int j=0; j < storage[0].length;j++)
                storage[i][j] = -1;
        }

        for (int i=0; i < mines.length; i++){
            maxGold = Math.max(maxGold, findMaxGold(mines, i, 0, storage));
        }
        System.out.println("MAX Gold in Mine : " + maxGold);
    }
}

Find out minimum operations required

There are three operations given:  

     op1 => divid by 3

     op2 => divide by 2

     op3 => subtract 1

Find minimal no. of operation required to convert a given no. to 1.

E.g.: To convert 10 to 1 minimum "3" operations are required as explained below

10 -> op3 = 9

9   -> op1 = 3

3   -> op1 = 1

Approach 1: Brute force

This problem can be solved using recursion. Try every possible operation till the number becomes equal to 1 and find minimum operations out of these.

class Solution {
   public static int noOfOperations(int n, int cur_op_count, int min_op_count) {

        if (cur_op_count >= min_op_count)
            return cur_op_count;  // this indicate a invalid path(not an optimal) so return
        if (n == 1) return cur_op_count;

        int size1 = Integer.MAX_VALUE;
        int size2 = Integer.MAX_VALUE;
        int size3 = Integer.MAX_VALUE;

        cur_op_count = cur_op_count + 1;

        if (n % 3 == 0)
            size1 = noOfOperations(n / 3, cur_op_count, min_op_count);
        min_op_count = Math.min(min_op_count, size1);

        if (n % 2 == 0)
            size2 = noOfOperations(n / 2, cur_op_count, min_op_count);
        min_op_count = Math.min(min_op_count, size2);

        size3 = noOfOperations(n - 1, cur_op_count, min_op_count);
        return Math.min(Math.min(size1, size2), size3);
    }

    public static void main(String[] args) {
        System.out.println(noOfOperations(22, 0, Integer.MAX_VALUE));
    }
}

Approach 2: Dynamic Programming

In brute force approach we are not storing the results so recursion will try to solve same subproblem every time. Add a temporary storage to hold the result of earlier solutions and use the same for next results.

Code below demonstrate approach 2 implementation.

class Solution {

    public static int minOperations(int input, int[] operations){
        if(input <= 1)
            return 0;
        if(operations[input] != -1)
            return operations[input];

        int divBy3=Integer.MAX_VALUE, divBy2 = Integer.MAX_VALUE;

        if(input % 3 == 0){
            divBy3 = minOperations(input/3, operations) + 1;
        }

        if(input % 2 == 0){
            divBy2 = minOperations(input/2, operations) + 1;
        }
        int sub1 = minOperations(input - 1, operations) + 1;

        int min = Math.min(Math.min(divBy3, divBy2), sub1);
        operations[input] = min;
        return min;
    }

    public static void main(String[] args) {
        int input = 11;
        int[] operations = new int[input+1];
        for(int i=0; i < operations.length; i++) operations[i] = -1;
        operations[0] = 0;
        operations[1] = 0;
        System.out.println("Min Operations : " + minOperations(input, operations));
    }
}

Comments are welcome.

Find out all pairs having difference equals to 'K' in sorted array

We have given a sorted array of integer. Need to find out all pair of element having difference as ‘k'.

Approach 1 : Brute force
We can start with first element of array and subtract it with every other number from array and check the diff. Repeat this for rest all elements. Complexity O(N^2)

Approach 2 : Binary Search
As the array elements are sorted we can use binary search to search the matching element. E.g. take first element from array, and search for element equals to "k - first element". 
This we can repeat for all the elements in the array. Complexity O(NlogN) 

Approach 3 : Use Set/HashMap
If we are allowed to use additional space we can add elements HashSet or HashMap as key one by one and check before adding if element equal to "k - element to be added" exists in set. Complexity O(N)

Approach 4: Increment or decrement indexes based on difference:
Use two indices out of which one starts at beginning and one starts at first index plus one. As the array is sorted, you just want to check if current diff is less than or greater than k (key), based on the result increment or decrement indices. If we found match update both indices. Complexity O(N)

Below solution implements approach 4. This solution will not display duplicate pairs if we have duplicate numbers.

class Solution {
    public static void findPairHavingDiff(int[] numbers, int k){
        if(numbers.length > 0){
            int start = 0;
            int end = 1;
            while(end < numbers.length){
                int diff = numbers[end] - numbers[start] ;
                if(diff == k) {
                    System.out.println("Found Pair : " + numbers[start] + " & " + numbers[end]);
                    start++;
                    end++;
                }
                else if(diff < k) end++;
                else if(diff > k) start++;
            }
        }
        else System.out.println("None found");
    }

    public static void main(String[] args) {
        int[] input = {-1, 2, 3, 4, 5, 6, 7, 8, 10 };
        findPairHavingDiff(input, 9);
    }
}

//Output of the above solution is
Found Pair : -1 & 8

Reverse an array without affecting special characters

Given a string, that contains special character together with alphabets (‘a’ to ‘z’ and ‘A’ to ‘Z’), reverse the string in a way that special characters are not affected. e.g.

    Input:   str = "a,b$c"
    Output:  str = "c,b$a"
    Note that $ and , are not moved anywhere.  
    Only subsequence "abc" is reversed

    Input:   str = "Ab,c,de!$"
    Output:  str = "ed,c,bA!$"
     

Approach 1

 
public class Solution {  
   public static void main(String[] args) {  
     System.out.println(reverseString("man ish#"));  
   }  
   /**  
    * Reverse string with maintaining special character in place  
    *  
    * Algorithm:  
    * 1. create temporary array  
    * 2. copy all character from original array excluding special character  
    * 3. reverse the temporary array  
    * 4. start copying temporary array into original if element is an alphabetic character  
    * @param input  
    * @return  
    */  
   public static String reverseString(String input) {  
     char[] inputArr = input.toCharArray();  
     char[] tempArr = new char[input.length()];  
     int i=0;  
     int j=0;  
     for (char ch:inputArr){  
       if(Character.isAlphabetic(ch)){  
         tempArr[i] = ch;  
         i++;  
       }  
     }  
     i--;  
     while(j<i){  
       char temp = tempArr[i];  
       tempArr[i]= tempArr[j];  
       tempArr[j]=temp;  
       j++;  
       i--;  
     }  
     for(i=0,j=0;i<input.length();i++){  
       if(Character.isAlphabetic(inputArr[i])){  
         inputArr[i]= tempArr[j++];  
       }  
     }  
     return new String(inputArr);  
   }  
 }  

Approach 2

 
public class Solution {  
   public static void main(String[] args) {  
     System.out.println(reverseString("man ish#"));  
   }  
   /**  
    * Reverse a string with maintaining special character position.  
    * Algorithm :  
    * 1) Let input string be 'str[]' and length of string be 'n'  
    * 2) l = 0, r = n-1  
    * 3) While l is smaller than r, do following  
    * a) If str[l] is not an alphabetic character, do l++  
    * b) Else If str[r] is not an alphabetic character, do r--  
    * c) Else swap str[l] and str[r]  
    *  
    * @param input : Input string  
    * @return reverse string  
    */  
   public static String reverseString(String input) {  
     char[] inputArr = input.toCharArray();  
     int l = 0;  
     int r = inputArr.length - 1;  
     while (l < r) {  
       if (!Character.isAlphabetic(inputArr[l])) {  
         l++;  
       } else if (!Character.isAlphabetic(inputArr[r])) {  
         r--;  
       } else {  
         char tempChar = inputArr[l];  
         inputArr[l] = inputArr[r];  
         inputArr[r] = tempChar;  
         l++;  
         r--;  
       }  
     }  
     return new String(inputArr);  
   }  
 }  

Find out all pair of element having sum as ‘k' in given sorted array

We have given a sorted array of integer. Need to find out all pair of element having sum as ‘k'.

Approach 1 : Brute force
We can start with first element of array and add it with every other number from array and check the sum. Repeat this for rest all elements. Complexity O(N^2)
This brute force approach can be slightly improved by adding the elements from the current index + 1 to the index where sum is greater than k (key).

Approach 2 : Binary Search
As the array elements are sorted we can use binary search to search the matching element. E.g. take first element from array, and search for element equals to "k + first element".
This we can repeat for all the elements in the array. Complexity O(NlogN)

Approach 3 : Use Set/HashMap
If we are allowed to use additional space we can add elements HashSet or HashMap as key one by one and check before adding if element equal to "k + element to be added in set" exists in set. Complexity O(N)

Approach 4: Increment or decrement indexes based on sum:
Use two indices out of which one starts at beginning and one starts at end. As the array is sorted, you just want to check if current sum is less than or greater than k (key), based on the result increment or decrement end index. If we found match update both indices. Complexity O(N)

Below solution implements approach 4. This approach does not display duplicate pairs if we have duplicate elements.

class Solution {
    public static void findPair(int[] numbers, int k){
        if(numbers.length > 0){
            //get first & last index from the sorted array
            int start = 0;
            int end = numbers.length - 1;
            while(start < end){
                int sum = numbers[start] + numbers[end];
                if(sum == k) {
                    System.out.println("Found Pair : " + numbers[start] + " & " + numbers[end]);
                    start++;
                    end--;
                }
                else if(sum < k) start++;
                else if(sum > k) end--;
            }
        }
        else System.out.println("None found");
    }

    public static void main(String[] args) {
        int[] input = {0, 2, 3, 5, 6, 8, 12, 15, 18 };
        findPair(input, 18);
    }
}

//Output of the above solution is
Found Pair : 0 & 18
Found Pair : 3 & 15
Found Pair : 6 & 12

Finding duplicate from array having element from 0 to n-2.

An array contains n numbers ranging from 0 to n-2. There is exactly one number duplicated in the array. How do you find the duplicated number? For example, if an array with length 5 contains numbers {0, 2, 1, 3, 2}, the duplicated number is 2. Solution:

class Solution {
    public static int findDuplicate(int numbers[]) {
        int length = numbers.length;
        int sum1 = 0;
        for (int number : numbers) {
            if (number < 0 || number > length - 2)
                throw new IllegalArgumentException("Invalid numbers.");
            sum1 += number;
        }
        // Calcualate the sum of number from 1 to n as n(n-1)/2  
        int sum2 = ((length - 1) * (length - 2)) >> 1;
        return sum1 - sum2;
    }
    public static void main(String[] args) {
        int input[] = {0, 2, 1, 3, 2};
        System.out.println("Duplicate Number : " + findDuplicate(input));
    }
}

//Output of above code will be 
Duplicate Number : 2