Find the element that appears once

Find the element that appears once

Given an array where every element occurs two times, except one element which occurs only once. Find the element that occurs once?

Approach#1

By using Brute Force technique, search for element which appeared once using two loops.

Complexity: O (n^2).

Approach#2

1. Sort the number.

2. Search for the element appeared once.

Complexity: O (nLogn).

Approach#3

Make a hashmap which will maintain the count of each digit.

Complexity: Worst case time of hashing may be more than O (n) and hashing requires extra space.

Approach#4

XOR all the elements of the array and the result will be the element which appeared once.

Complexity: O (n).

public class IdentifyNumber {

     public static void main(String[] args) {

           int[] array = {11,3,4,5,4,3,6,7,6,7,5};

           int num = indentifyNum(array);

           System.out.println(num);

     }

     private static int indentifyNum(int[] array) {

           int num = 0;

           for (int element : array) {

                num = num ^ element;

           }

           return num;

     }

}

Output: 11

Why interface cannot have instance variables?

Interface variables are static final because Java interfaces cannot be instantiated in their own right; the value of the variable must be assigned in a static context in which no instance exists. The final modifier ensures the value assigned to the interface variable is a true constant that cannot be re-assigned by program code.

Explicit casting from super class to subclass : Downcasting

public class Animal {

    public void eat() {}

}

public class Dog extends Animal {

    public void eat() {}

    public void main(String[] args) {

        Animal animal = new Animal();

        Dog dog = (Dog) animal;

    }

}

The assignment Dog dog = (Dog) animal; at runtime it generates a ClassCastException.

By using a cast you're essentially telling the compiler "trust me that this animal variable is definitely going to be a dog."

Since the animal isn't actually a dog (may be Cat).

The VM throws an exception at runtime because you've violated that trust.

The compiler is a bit smarter than just blindly accepting everything, if you try and cast objects in different inheritance hierarchies then the compiler will throw it back at you because it knows that could never possibly work.

By using instanceof operator, we can avoid the ClassCastException.

It's an animal, you could do Animal animal = new Dog(); and it'd be a dog.

Maximize the robbery

A robber enters a colony of houses numbered from 1 to n.  Every house has a number printed on the top of it. That number is the amount of money inside that house. However, there is one constraint. If the robber cannot robs from money from consecutive houses. How can the robber maximize his robbery?

Solution:

If Robber robs from i-th house, he can't rob house no i-1 and house no i+1.

Dynamic Programming logic:

dp[i] = Math.max(dp[i - 2] + amPerHouse[i], dp[i - 1]);

Implementation in Java:

import java.util.Scanner;

public class MaximiseRobbery {

     public static void main(String[] args) {

           Scanner scan = new Scanner(System.in);

           int houses = scan.nextInt();

           int[] amPerHouse = new int[houses];

           for (int i = 0; i < houses; i++) {

                amPerHouse[i] = scan.nextInt();

           }

           int maximumRobbery = maximizeRobbery(amPerHouse, houses);

           System.out.println(maximumRobbery);

           scan.close();

     }

    

     /**

      * Method to maximise the robbery

      * @param amPerHouse

      */

     private static int maximizeRobbery(int[] amPerHouse,int houses) {

        if (houses == 1) {

              return amPerHouse[0];

        } else if (houses == 2) {

              return Math.max(amPerHouse[0], amPerHouse[1]);

        }

        int[] dp = new int[amPerHouse.length];

        dp[0] = amPerHouse[0];

        dp[1] = amPerHouse[1];

        for (int i = 2; i < houses; i++) {

           dp[i] = Math.max(dp[i - 2] + amPerHouse[i], dp[i - 1]);

        }

        return dp[houses - 1];

     }

}

Reference:

http://www.geeksforgeeks.org/maximum-sum-such-that-no-two-elements-are-adjacent/

Calculate the number of 1’s in the binary representation of a number

Number of 1’s in the binary representation of a number

Complexity of the algorithm is O(Number of 1's).

bitcount(n):

count = 0

while n > 0:

            count = count + 1

            n = n & (n-1)

return count

In worst case (when the number is 2^n - 1, all 1's in binary) it will check every bit.

public class BitCount {

     public static void main(String[] args) {

           int number = 15;

           int count = 0;

           while(number>0) {

                number = number & (number-1);

                count++;

           }

           System.out.println("Number of 1s are: "+count);

     }

}

Output:

Number of 1s are: 4

How to check the number is power of two?

How to check the number is power of two?

Approach #1:

Divide number by 2 reclusively to check it.

Time complexity : O(log2n).

Approach #2:

Bitwise AND the number with its just previous number should be equal to ZERO.

Example: Number = 8

Binary of 8: 1 0 0 0

Binary of 7: 0 1 1 1 and the bitwise AND of both the numbers is 0 0 0 0 = 0.

Time complexity : O(1).

Approach #3:

Bitwise XOR the number with its just previous number should be sum of both numbers.

Example: Number = 8

Binary of 8: 1 0 0 0

Binary of 7: 0 1 1 1 and the bitwise AND of both the numbers is 1 1 1 1 = 15.

Time complexity : O(1).

import java.util.Scanner;

public class PowOfTwo {

      public static void main(String[] args) {

            Scanner scan = new Scanner(System.in);

            int num = scan .nextInt();

            checkUsingANDOperation(num);

            checkUsingXOROperation(num);

            scan.close();

      }

      /**

       * Check Using AND Operation

       */

      private static void checkUsingANDOperation(int num) {

            if((num & (num-1))==0) {

                  System.out.println(num+" is the power of 2");

            } else {

                  System.out.println(num+" is not the power of 2");

            }

      }

      /**

       * Check Using XOR Operation

       */

      private static void checkUsingXOROperation(int num) {

            if((num ^ (num-1))==2*num-1) {

                  System.out.println(num+" is the power of 2");

            } else {

                  System.out.println(num+" is not the power of 2");

            }

      }

}

Output:

8

8 is the power of 2

8 is the power of 2