Segmented Sieve to find primes in a range

There are many approaches to find the primes below a specific number. few better approaches will be Sieve of Eratosthenes and Segmented Sieve (for larger limit).

Below are the Java implementation of both.

Sieve of Eratosthenes Java Implementation

/**
  * @param limit : The limit can not be large as 1000,000,000
  * @return List of primes up to limit, i.e. in the range [0, limit]
  */
    static List< integer > simpleSieve(int limit) {
         boolean mark[] = new boolean[limit];
         Arrays.fill(mark, true);

         for (int p = 2; p * p < limit; p++) {
              // If p is not changed, then it is a prime
              if (mark[p] == true) {
                  // Update all multiples of p
                  for (int i = p * 2; i < limit; i += p) {
                      mark[i] = false;
                  }
              }
         }

         List< integer > list = new ArrayList<>();
         for (int i = 2; i < limit; i++) {
             if (mark[i]) {
                 list.add(i);
                 count++;
             }
         }
         return list;
    }

Segmented Sieve Java Implementation

/**
  * @param n : The value n can be large
  * @return List of primes up to n, i.e. in the range [0, n]
  */
    static List< integer > segmentedSieve(int n) {
        int limit = (int) Math.sqrt(n) + 1;
        List< integer > primes = simpleSieve(limit);
        List< integer > primesFinalList = new ArrayList<>();
        primesFinalList.addAll(primes);
        int low = 2;
        int high = limit;

        while (low < n) {
            boolean mark[] = new boolean[limit + 1];
            Arrays.fill(mark, true);

            for (int i = 0; i < primes.size(); i++) {
                int temp = primes.get(i);
                int loLim = (int) Math.floor(low * 1.0 / temp) * temp;
                if (loLim < low) {
                    loLim += temp;
                }
                for (int j = loLim; j < high; j += temp) {
                    mark[j - low] = false;
                }
            }
            for (int i = low; i < high; i++) {
                if (mark[i - low] == true) {
                    primesFinalList.add(i);
                    count++;
                }
            }
            low = low + limit;
            high = high + limit;
            if (high >= n) {
                high = n;
            }
         }
         return primesFinalList;
    }

Segmented Sieve for a Range

/**
  * @param leftLimit
  * @param rightLimit
  * @param maxRangeCapacity
  *            : maximum value for (rightLimit - leftLimit)
  * @return primes in the range [leftLimit, rightLimit]
  */
    static List< Integer > segmentedSieveForRange(int leftLimit, int rightLimit,
       int maxRangeCapacity) {
        List< Integer > list = new ArrayList<>();
        // max limit to consider is 1000,000,000
        // sqrt(1000,000,000) <= 31623 ; so lets find all primes upto 40,000
        // with a
        // safe margin
        boolean[] shieves = new boolean[40000];
        int numberOfPrimes = 0;
        // the number of primes below 40,000 is less than 4205 (can even find
        // from brute force)
        int[] index = new int[4205];
        // mark all as true (i.e. as primes)
        Arrays.fill(shieves, true);

        for (int i = 2; i * i < shieves.length - 1; i++) {
            if (shieves[i]) {
                // Update all multiples of i. NOTE : i is a prime
                for (int j = i; i * j < shieves.length; j++) {
                    shieves[j * i] = false;
                }
            }
        }

        // fill the index array where we store our primes below 40000
        for (int i = 0; i < shieves.length; i++) {
            if (shieves[i]) {
                index[numberOfPrimes++] = i;
            }
        }

        if (leftLimit < 2) {
            // the smallest prime
            leftLimit = 2;
        }
        // maxRangeCapacity = 1000,000
        boolean[] isPrime = new boolean[maxRangeCapacity + 1];
        Arrays.fill(isPrime, true);

        for (int k = 2; k < numberOfPrimes; k++) {
            int u = index[k];
            int start = 0;
   
            if (u >= leftLimit) {
                start = 2 * u;
            } else {
                start = leftLimit + ((u - leftLimit % u) % u);
            }

            for (int l = start; l <= rightLimit; l += u) {
                isPrime[l - leftLimit] = false;
            }
        }
  
        for (int p = leftLimit; p <= rightLimit; p++) {
            if (isPrime[p - leftLimit]) {
                list.add(p);
            }
        }
  
        return list;
    }

Sample solution to the problem Twins in Hackerrank

public class TwinPrime {

    public static void main(String[] args) throws NumberFormatException,
      IOException {

         BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
         BufferedWriter out = new BufferedWriter(new OutputStreamWriter(
         System.out));

         String[] temp = in.readLine().split(" ");
         int x = Integer.parseInt(temp[0]);
         int y = Integer.parseInt(temp[1]);

         List< Integer > list = segmentedSieveForRange(x, y, 1000000);

         int count = 0;
         int size = list.size();
         for (int i = 0; i < size - 1; i++) {
             if (list.get(i + 1) - list.get(i) == 2) {
                 count++;
             }
         }
         System.out.println(count);
 }

 /**
  * @param leftLimit
  * @param rightLimit
  * @param maxRangeCapacity
  *            : maximum value for (rightLimit - leftLimit)
  * @return primes in the range [leftLimit, rightLimit]
  */
    static List< Integer > segmentedSieveForRange(int leftLimit, int rightLimit,
      int maxRangeCapacity) {
         List< Integer > list = new ArrayList<>();
         // max limit to consider is 1000,000,000
         // sqrt(1000,000,000) <= 31623 ; so lets find all primes upto 40,000
         // with a
         // safe margin
         boolean[] shieves = new boolean[40000];
         int numberOfPrimes = 0;
         // the number of primes below 40,000 is less than 4205 (can even find
         // from brute force)
         int[] index = new int[4205];
         // mark all as true (i.e. as primes)
         Arrays.fill(shieves, true);

         for (int i = 2; i * i < shieves.length - 1; i++) {
             if (shieves[i]) {
                 // Update all multiples of i. NOTE : i is a prime
                 for (int j = i; i * j < shieves.length; j++) {
                     shieves[j * i] = false;
                 }
             }
         }

         // fill the index array where we store our primes below 40000
         for (int i = 0; i < shieves.length; i++) {
             if (shieves[i]) {
                 index[numberOfPrimes++] = i;
             }
         }

         if (leftLimit < 2) {
             // the smallest prime
             leftLimit = 2;
         }
         // maxRangeCapacity = 1000,000
         boolean[] isPrime = new boolean[maxRangeCapacity + 1];
         Arrays.fill(isPrime, true);

         for (int k = 2; k < numberOfPrimes; k++) {
             int u = index[k];
             int start = 0;
   
             if (u >= leftLimit) {
                 start = 2 * u;
             } else {
                 start = leftLimit + ((u - leftLimit % u) % u);
             }

             for (int l = start; l <= rightLimit; l += u) {
                 isPrime[l - leftLimit] = false;
             }
         }
  
         for (int p = leftLimit; p <= rightLimit; p++) {
             if (isPrime[p - leftLimit]) {
                 list.add(p);
             }
         }
  
         return list;
    }

}

Read More

Fenwick Tree Java Implementation

A Fenwick tree or Binary Indexed Tree is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers. This structure was proposed by Peter Fenwick in 1994 to improve the efficiency of arithmetic coding compression algorithms.

There are situation where we need to execute both update and query operations on an array (typically a number array). Naive solutions may take O(n) time to do a prefix sum search. And when the length of the array get increased this solution will give low performance. BIT can do the operations like prefix sum, point query, update in O(logn) time.

The BIT normally used to perform Segment Query and Point Updates. The below code is a Java implementation of that approach.

public class FenwickTree {

 long[] fenwickTree;
 int treeSize;

 /**
  * create a FenwickTree instance with a tree of a given size
  * 
  * @param size
  *            : size of the original array to consider
  */
 public FenwickTree(int size) {
     this.treeSize = size + 1;
     this.fenwickTree = new long[treeSize];
 }

 /**
  * create a FenwickTree instance with a given array
  * 
  * @param array
  */
 public FenwickTree(long[] array) {
     this.treeSize = array.length + 1;
     this.fenwickTree = new long[treeSize];

     for (int i = 1; i < treeSize; i++) {
          update(i, array[i - 1]);
     }
 }

 /**
  * if a previous value is updated by a new one (eg : 3 by 7), then only the
  * changed difference (7-3) need to be considered as 'value'
  * 
  * @param index
  * @param value
  */
 public void update(int index, long value) {
     while (index < treeSize) {
          fenwickTree[index] += value;
          // Increment the index by the amount up to first significant set bit
          // of index
          // typically finds the next node to consider
          index += index & (-index);
     }
 }

 /**
  * @param rightIndex
  * @return the sum of the range [0, rightIndex]
  */
 public long getPrefixSum(int rightIndex) {
     long sum = 0;
     while (rightIndex > 0) {
          sum += fenwickTree[rightIndex];
          // Decrement the index by the amount up to first significant set bit
          // of index
          // typically finds the parent node to consider
          rightIndex -= rightIndex & (-rightIndex);
     }

     return sum;
 }

 /**
  * (rightIndex >= leftIndex) required
  * 
  * @param leftIndex
  * @param rightIndex
  * @return the sum of the range [leftIndex, rightIndex]
  */
 public long getRangeSum(int leftIndex, int rightIndex) {
     return getPrefixSum(rightIndex) - getPrefixSum(leftIndex - 1);
 }

 /**
  * @return actual size of the tree
  */
 public int size() {
     return fenwickTree.length - 1;
 }

}

With a little help from the above implementation we can perform Segment Update Point Queries as well.

/**
 * SEGMENT UPDATING, POINT QUERY
 * 
 * for calculating cumulative sums and track segment update
 * 
 * NOTE: 1-based indexing
 * 
 * FenwickTreeSUPQ bit = new FenwickTreeSUPQ(10);
 * bit.updateRange(3, 7, 1); // [0, 0, 1, 1, 1, 1, 1, 0, 0, 0]
 * bit.updateRange(1, 10, -1); // [-1, -1, 0, 0, 0, 0, 0, -1, -1, -1]
 * bit.updateRange(4, 8, 5); // [-1, -1, 0, 5, 5, 5, 5, 4, -1, -1]
 * 
 * bit.getPointValue(3); // 0
 * bit.getPointValue(7); // 5
 * bit.getPointValue(10); // -1
 * 
 * @author vnbandara
 *
 */
class FenwickTreeSUPQ extends FenwickTree {
 
    private int size;

    public FenwickTreeSUPQ(int size) {
         //we are updating (rightIndex + 1), so treeSize needs to be
         //more than that. When initializing the FenwickTree, pass size
         //as (original size + 1)
         super(size + 1);
         this.size = size;
    }

 /**
  * @param leftIndex
  * @param rightIndex 
  * @param value
  */
    public void updateRange(int leftIndex, int rightIndex, long value) {
         update(leftIndex, value);
         update(rightIndex + 1, -value);
    }

 /**
  * point value will be the cumulative sum of all the elements before that
  * point (inclusive)
  * 
  * @param index
  * @return
  */
    public long getPointValue(int index) {
         return getPrefixSum(index);
    }

 /**
  * @return the updated array by calculating cumulative sums
  */
    public long[] getUpdatedArray() {
         long[] array = new long[size];
         for (int i = 1; i <= size; i++) {
             array[i - 1] = getPointValue(i);
         }
         return array;
    }

}

And when we want to perform Segment Update Segment Queries we can use two FenwickTrees like below

/**
 * Use two Fenwick trees to track segment updates and segment sum queries
 * 
 * we are using and considering 1 based indexing
 * 
 * @author vnbandara
 * 
 */
public class FenwickTreeSUSQ {

    private FenwickTree bit1;
    private FenwickTree bit2;
    private int size;

    public FenwickTreeSUSQ(int size) {
         this.size = size;
         // size + 1 ; because then we can use 1 based indexing
         // so the bit1 and bit2 will be (size+2) in size. (1 extra for 1-based
         // indexing and another for storing cumulative sums)
         bit1 = new FenwickTree(size + 1);
         bit2 = new FenwickTree(size + 1);
    }

    public void updateReange(int leftIndex, int rightIndex, long value) {
         bit1.update(leftIndex, value);
         bit1.update(rightIndex + 1, -value);
         bit2.update(leftIndex, value * (leftIndex - 1));
         bit2.update(rightIndex + 1, -value * rightIndex);
    }

 /**
  * @param rightIndex
  * @return the sum of elements in range [0, rightIndex] in original array
  */
    public long getPrefixSum(int rightIndex) {
          return bit1.getPrefixSum(rightIndex) * rightIndex
           - bit2.getPrefixSum(rightIndex);
    }

 /**
  * get the sum of all the values in the range [leftIndex, rightIndex] in the
  * updated array
  * 
  * ex: 
  * FenwickTreeSUSQ fen = new FenwickTreeSUSQ(10); 
  * fen.updateReange(3, 7, 2);
  * fen.updateReange(5, 9, 3);
  * 
  * will results : [0, 0, 2, 2, 5, 5, 5, 3, 3, 0] NOTE 1-based indexing
  * 
  * fen.getRangeSum(5, 7) -> 15
  * fen.getRangeSum(4, 7) -> 17
  * fen.getRangeSum(5, 8) -> 18
  * 
  * @param leftIndex
  * @param rightIndex
  * @return sum of all the values in the range [leftIndex, rightIndex] in the updated array
  */
    public long getRangeSum(int leftIndex, int rightIndex) {
         return getPrefixSum(rightIndex) - getPrefixSum(leftIndex - 1);
    } 

    public long getPointValue(int index) {
         return getPrefixSum(index);
    }

 /**
  * Just to look-up how original array get updated
  * 
  * ex: 
  * FenwickTreeSUSQ fen = new FenwickTreeSUSQ(10); 
  * fen.updateReange(3, 7, 2);
  * fen.updateReange(5, 9, 3);
  * 
  * will results : [0, 0, 2, 2, 5, 5, 5, 3, 3, 0] NOTE 1-based indexing
  * 
  * @return
  */
    public long[] getUpdatedArray() {
         long[] array = new long[size];
         for (int i = 1; i <= size; i++) {
             array[i - 1] = getPointValue(i) - getPointValue(i - 1);
         }
         return array;
    }
}

 Some useful resources,

1. https://github.com/mission-peace/interview/blob/master/src/com/interview/tree/FenwickTree.java
2. https://discuss.leetcode.com/topic/31599/java-using-binary-indexed-tree-with-clear-explanation
3. http://algs4.cs.princeton.edu/99misc/FenwickTree.java.html
4. http://www.geeksforgeeks.org/binary-indexed-tree-range-update-range-queries/
5. http://cs.stackexchange.com/questions/33014/range-update-range-query-with-binary-indexed-trees
6. http://stackoverflow.com/questions/27875691/need-a-clear-explanation-of-range-updates-and-range-queries-binary-indexed-tree/27877427#27877427

 Sample Problems : https://www.hackerrank.com/challenges/similarpair

Read More

Finding the unpaired element in an array

Given an integer array there are odd number of elements (each are between 1 and 100). Except for one all others have a duplicate in the array.

ex : [1, 3, 4, 5, 7, 6, 7, 5, 3, 1, 4]

in here only unpaired element is 6. Target is to find the unpaired element of this array.

We can use the Exclusive Or operation to solve this.

The property we are going to use is for an integer 'a' the vale a^a is zero and 0^a is 'a'. When we get the XOR of the given array elements altogether the answer will be the isolated element.

int notPaired(int[] n) {
    int ans = 0 ;
    for (int e:n)
        ans ^= e;
    return ans;
}

Read More

Bit Masking

Lightweight, small sets of Booleans (native support in C/C++/Java). An integer is stored in a computer’s memory as a sequence/string of bits.

" In computer science, a mask is data that are used for bitwise operations, particularly in a bit field. Using a mask, multiple bits in a byte, nibble, word (etc.) can be set either on, off or inverted from on to off (or vice versa) in a single bitwise operation " [Mask (computing)]

The binary representations can be used to hold information about subsets of a set.

Ex:  Consider the set/list A = {a, b, c, d, e, f} or set/list B = {10, 20, 25, 15, 30, 40}

We can represent the set B as {1, 1, 1, 1, 1, 1} (the sub set which has all the element)
Sub set {20, 15} of set B can be represent as {0, 1, 0, 1, 0, 0} (20 in decimal format)

• We can multiply/divide using bit shifting

int s = 34;         // 0100010
int a = 34 << 1;    // 1000100 ; this is equal to 34*2 ; 100010 << 1 => 1000100
int b = 34 >> 1;    // 0010001 ; this is equal to 34/2 ; 100010 >> 1 => 0010001
int c = 34 >> 2;    // 0001000 ;

//Notice that the truncation in the shift right operation automatically rounds the division-by-2 down

• Set/turn on the j-th item (0-based indexing) of the set. Use the bitwise OR operation S |= (1 << j)

// set = {a,b,c,d,e,f,g}
int s = 34;                 // 0100010 : sub-set = {b,f}
int j = 3;                  // the index we need to turn on , means include 'd', since 0-based
int newSet = s | (1 << j);  // 0101010 : sub-set = {b,d,f}

• Set/turn on the j-th item (0-based indexing) of the set. Use the bitwise OR operation S |= (1 << j)

// set = {a,b,c,d,e,f,g}
int s = 34;                 // 0100010 : sub-set = {b,f}
int j = 3;                  // the index we need to turn on , means include 'd', since 0-based
int newSet = s | (1 << j);  // 0101010 : sub-set = {b,d,f}

• To clear/turn off the j-th item of the set. Use bitwise AND operation S &= ~(1 << j)

int s = 38;  // 100110
int j = 2;  // 0-based index
int a = ~(1 << j);  // 111011
int res = s & a;  // 100010

• To check if the j-th item of the set is on, use the bitwise AND operation T = S & (1 << j)

int s = 38;   // 100110
// is 2nd item is on
int j = 2;
int a = (1 << j); // 000100
int t = s & a;  // 000100 , not zero, to be precise it is (t = a) so 2nd item is on
  
// is 3nd item is on
j = 3;
a = (1 << j);  // 001000
t = s & a;  // 000000 , zero , so 2nd item is off

• To toggle (flip the status of) the j-th item of the set, use the bitwise XOR operation S ^= (1 << j)

int s = 40;  // 101000
int j = 2;
int a = (1 << 2); // 000100
s = s ^ a;  // 101100 , turned on
s = s ^ a;  // 101000 , turned off

• To get the value of the least significant bit that is on (first from the right), use T = (S & (~S))

int s = 40;  // 00000000000000000000000000101000
int nS = -40; // 11111111111111111111111111011000 (two’s complement)
int t = s & nS; // 1000 , 8, 3rd bit from the right is on

• To turn on all bits in a set of size n, use S = (1 << n) - 1
• Iterate through all subsets of a set of size n

int n = 5;
for ( int x = 0; x < (1 << n); ++x ){
 // loop will go for (1 << n) turns
}

• Example of usage

 
for (int i = 0; i < (1 << n); ++i) {  // for each subset, O(2^n)
 for (int j = 0; j < n; ++j) {   // check membership, O(n)
  if ((i & (1 << j)) != 0) {   // test if bit ‘j’ is turned on in subset ‘i’ ?
   // if yes, process ‘j’
  }
 }
}

References : Competitive Programming books

Read More

Ignoring in GIT

Let's say we have an eclipse project.
And we have a file called MyFile.java in that project. We want to make sure that this file must not go to a remote repository when we push this to GIT (version control system)

The basic thing we can do is to add this file name in .gitignore file. If your file has no changes (not modified or newly added) then this will work at first time. But assume you added this file to .gitignore after you did some changes to the file. (i.e. when you enter git status, the file will be shown in the modified section). The GIT might be still tracking the file.

What can you do, there are several cases.

case 1 : you don't need this file to be on the remote repository.

git rm --cached MyFile.java

this will remove the file from git index but it won’t do anything with your working copy. It won’t be a part of the git repository anymore. And the next time you push to a remote repository this file won’t be pushed and, if it is already existed on the remote repository, it will be DELETED.

case 2 : You just changed the file because it has some local dependency, such as may be some configurations related to my local IDE or machine. Then you cannot delete this file from the remote repository. What you want is to keep the changed file in the local, but doesn't need to be tracked.

But you can tell the GIT to ignore tracking it's changes.

git update-index --assume-unchanged MyFile.java

//to revert the effect

git update-index --no-assume-unchanged MyFile.java

You can use     git ls-files -v     to view the files. And if the first letter is in lower case then those are the files which --assume-unchanged.
To print just the files that are --assume-unchanged use:

git ls-files -v | grep '^[[:lower:]]'

you can put this to .gitconfig (or .git/config in the repository, or the gloabal one(~/.gitconfig to get the location)) and use this directly.
Edit your .gitconfig file to add this snippet:

[alias]
    ignored = !git ls-files -v | grep "^[[:lower:]]"

now typing git ignored will print the same out-put


References

1) https://jlordiales.wordpress.com/2012/12/28/when-git-ignores-your-gitignore/ 2) http://stackoverflow.com/questions/17195861/undo-git-update-index-assume-unchanged-file 3) https://git.wiki.kernel.org/index.php/Aliases 4) http://stackoverflow.com/questions/2363197/can-i-get-a-list-of-files-marked-assume-unchanged 5) Making git “forget” about a file that was tracked but is now in .gitignore

Read More

JavaScript here and there

• Variables created without the keyword var , are always global, even if they are created inside a function
• A closure is an inner function that has access to the outer (enclosing) function’s variables—scope chain. The closure has three scope chains: it has access to its own scope (variables defined between its curly brackets), it has access to the outer function’s variables, and it has access to the global variables. A closure in JavaScript is like keeping a copy of all the local variables, just as they were when a function exited.

Read More

Why it's bad to use floting point numbers for equality or condition checking ?

Most of the suggestions are to avoid floating-point numbers from equality checking or in condition checking. Because small errors in the rightmost decimal places are likely to arise when calculations are performed on floating-point numbers, And two float or double values (float and double are also different) rarely are exactly equal.

assume ,

double oneThird = 1.0 / 3.0;
double x = oneThird + oneThird + oneThird;

actually expected result is x to be equal to 1. But it probably doesn't. Because the first assignment statement stores an approximation of 1/3 in to oneThird, which is likely to be 0.3333333 (But actually it's 0.33333.....)
So the second statement stores something like 0.9999999 in to x.
So the computer will compare x with 1 and it recognize it as a mismatch. so eventually it will yield false.

Some interesting code snippets are listed below.

double a = 0.9999999999999999999;
if (1 == a) {
    System.out.println("1 equals to 0.9999999999999999999");
} else {
    System.out.println("1 does not equals to 0.9999999999999999999");
}
// prints "1 equals to 0.9999999999999999999"

float x = 1.1f;
double y = 1.1;
if (x != y) {
    System.out.println("1.1f and 1.1 does not match");
}
// prints "1.1f and 1.1 does not match"

double oneThird = 1.0 / 3.0;
double one = oneThird + oneThird + oneThird;
if(1.0000000000000000001 == one){
    System.out.println("1.0000000000000000001 equals to one");
} else {
    System.out.println("1.0000000000000000001 does not equals to one");
}
// prints "1.0000000000000000001 equals to one"

double a1 = 1.0/3.0;
double a2 = 0.333333;
if(a1 == a2){
    // programmer might think this will be the case !!!
    System.out.println("1.0/3.0 is equal to 0.33333");
}else{
    System.out.println("1.0/3.0 is not equal to 0.33333");
}
// prints "1.0/3.0 is not equal to 0.33333"

So how can we avoid this. Instead of checking for equality, we can test for near equality. one famous way to do this is to compute the difference between the numbers and see whether the result is less than some maximum allowable difference.

double EPSILON = 1.0e-7;
if (Math.abs(1 - a) < EPSILON) {
    System.out.println("yes");
} else {
    System.out.println("no");
}
// prints "yes"

Some interesting articles about this area are listed below.
0.999...
Why do so many people reject proofs that 0.999999... = 1?
Relational operators with floating point types
What Every Computer Scientist Should Know About Floating-Point Arithmetic ?
Comparing floating point numbers
Comparing Floating Point Numbers - by Random ASCII
Doubles are not floats, so don’t compare them
Why not use Double or Float to represent currency?

Read More