CseWay

A Way For Learning

Showing posts with label Strings. Show all posts
Showing posts with label Strings. Show all posts

Fibonacci-Prime Number


Fibonacci-prime number : Given a number N, you need to find if N is fibonacci-prime number or not. A fibonacci-prime is any number that is both a prime and a fibonacci number.

import java.math.BigInteger;
import java.util.HashSet;
import java.util.Scanner;

public class Solution
{
    static boolean isPrime(BigInteger bigInteger)
    {
        if(bigInteger.isProbablePrime(1))
            return true;
        return false;
    }

    @SuppressWarnings("unchecked")
    static void findAndSetFibonacciPrimeNumbers(HashSet set)
    {
        BigInteger a=new BigInteger("0");
        BigInteger b=new BigInteger("1");
        BigInteger s=a.add(b);
        BigInteger range=new BigInteger("10").pow(75);
        while (range.compareTo(s)==1)
        {
            a=b;
            b=s;
            s=a.add(b);
            if(s.isProbablePrime(2))
                set.add(s);
        }
    }
    public static void main(String[] args)
    {
        HashSet<BigInteger> set=new HashSet<>();
        findAndSetFibonacciPrimeNumbers(set);
        /*System.out.println(set.toString());*/
        Scanner sc=new Scanner(System.in);
        int testCases=sc.nextInt();
        while (testCases-->0)
        {
            BigInteger n=new BigInteger(sc.next());
            if(set.contains(n))
                System.out.println(1);
            else System.out.println(0);
        }
    }
}
Read More
,

Program on Strings

Given a string S and a string T, count the number of distinct subsequences of T in S.S = “rabbbit”, T = “rabbit”3.

 class Count {
     public static int foo(String S, String T) {
        //if C[i][j] i means # chars. so C[?][0] === 1
        int m = S.length(), n = T.length();
        int[][] C = new int[m+1][n+1];
        for(int i=0;i<=m;i++) C[i][0] = 1;
        for(int i=1;i<=m;i++) {
            for(int j=1;j<=n;j++) {
                C[i][j] = C[i-1][j];
                if(S.charAt(i-1)==T.charAt(j-1)) C[i][j]+=C[i-1][j-1];
            }
        }
        return C[m][n];
    }
    public static void main(String[] args) {
       System.out.println(foo("rabbbit","rabbit"));
    }  
 }

Reference:
http://www.cs.cmu.edu/~yandongl/distinctseq.html
Read More
,
Subscribe to: Posts ( Atom )