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 (intelement : 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.

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

Circular prime

Circular prime

A circular prime is a prime number with the property that the number generated at each intermediate step when cyclically permuting its (base 10) digits will be prime.

For example, 1193 is a circular prime, since 1931, 9311 and 3119 all are also prime.

Note:

A circular prime with at least two digits can only consist of combinations of the digits 1, 3, 7 or 9, because having 0, 2, 4, 6 or 8 as the last digit makes the number divisible by 2, and having 0 or 5 as the last digit makes it divisible by 5.

Reference:

https://en.wikipedia.org/wiki/Circular_prime

https://www.hackerrank.com/contests/projecteuler/challenges/euler035

Kaprekar number

Kaprekar number

Named after Dattaraya Ramchandra Kaprekar .

Kaprekar number for a given base is a non-negative integer, the representation of whose square in that base can be split into two parts that add up to the original number again.

Examples:

297 is a Kaprekar number for base 10, because 297² = 88209, which can be split into 88 and 209, and 88 + 209 = 297.

45 is a Kaprekar number, because 45² = 2025 and 20+25 = 45.

Let X be a non-negative integer.

X is a Kaprekar number for base b if there exist non-negative integers n, A, and positive number B satisfying:

X² = Abn + B, where 0 < B < bn

X = A + B

Note that X is also a Kaprekar number for base bn, for this specific choice of n. More narrowly, we can define the set K(N) for a given integer N as the set of integers X for which[1]

X² = AN + B, where 0 < B < N

X = A + B

Each Kaprekar number X for base b is then counted in one of the sets K(b), K(b²), K(b³),….

Note:

By convention, the second part may start with the digit 0, but must be nonzero.

For example, 999 is a Kaprekar number for base 10, because 999² = 998001, which can be split into 998 and 001, and 998 + 001 = 999. But 100 is not; although 100² = 10000 and 100 + 00 = 100, the second part here is zero.

Reference: https://en.wikipedia.org/wiki/Kaprekar_number

Longest sub array that has elements in increasing order?

Increasing longest sub array

We can solve it by using:

Brute force – Time Complexity O(n^2)

Dynamic programming - Time Complexity O(n).

Pseudo code:

def DP(a[]):

            dp[1] = 1

            for i = 2 to n:

                    if a[i] > a[i - 1]:

                            dp[i] = dp[i - 1] + 1

                    else:

                            dp[i] = 1