rbrandonstewart
BAN USERO(1) space and time:
int interpretations(String str)
{
int index = str.length() - 1;
int count = 1;
int prevCount = 1, prevPrevCount = 1;
for (int i=index; i>=0; --i)
{
if (i < index)
{
int number = str.charAt(i + 1) - '0' + (str.charAt(i) - '0') * 10;
if (number <= 26)
{
count += prevPrevCount;
}
}
prevPrevCount = prevCount;
prevCount = count;
}
return count;
}
I'm not seeing how DP helps.
int ways(int [] array, int target, int start, int setSize)
{
int count = 0;
if (setSize == 1)
{
for (int i=start; i<array.length; ++i)
{
if (target == array[i])
{
++count;
}
}
}
else
{
for (int i=start; i<array.length; ++i)
{
if (target >= array[i])
{
count += ways(array, target - array[i], i, setSize - 1);
}
}
}
return count;
}
int minimumSubset(int [] array, int target)
{
System.out.println("Target = " + target + ", array = " + Arrays.toString(array));
int s;
int count = 0;
for (s=1; s<=array.length; ++s)
{
count = ways(array, target, 0, s);
if (count > 0)
{
break;
}
}
System.out.println("s = " + s + ", ways = " + count);
return 0;
}
I could have just looked up standard algorithm for Gray codes, but that would have ruined the challenge.
- rbrandonstewart February 24, 2013