where P(0) = 'X', P(1)='Y' and P(2)='Z'
Input Parameters: needle string str to search for and number n
Conditions to handle:
if number n is >= 40 return -1
if string str has any other characters then X,Y and Z return -1
Solution
Solved this problem for preliminary round of one programming contest.
PadovanString.java
[code language="java"]
public class PadovanString {
public int stringOccurrences(int n, String str){
if (n >= 40)
return -1;
if (str.replaceAll("X|Y|Z", "").length() > 0)
return -1;
String res= pad(n);
/* print nth Padovan String
System.out.println(res);*/
/*replace search string with null and caculate number of occurences*/
return (res.length() - res.replaceAll(str, "").length())/(str.length());
}
public String pad(int n){
if (n == 0) return "X";
if (n == 1) return "Y";
if (n == 2) return "Z";
else return pad(n-2) + pad(n-3);
}
}
[/code]
Test.java
[code language="java"]
public class Test {
public static void main(String []args)
{
PadovanString p = new PadovanString();
System.out.println(p.stringOccurrences(20,"YZ"));
}
}
[/code]
Also, Length of Nth padovan string = Nth Padovan number
