CareerCup

This is a recursion question where you go from right to left building up and returning count.

static int count(int[]arr){
		if(arr.length == 0) return 0;
		return getCnt(arr, arr.length -1);
	}
	
	static int getCnt(int[]arr, int ind){
		if(ind < 0) return 0;
		if(ind == arr.length-1){
			if(arr[ind] > 0){
				return 1+getCnt(arr, ind-1);
			}else{
				return getCnt(arr, ind-1);
			}
		}
		if(arr[ind] > 0 && arr[ind]*10 + arr[ind+1] <= 26)
			return 1+getCnt(arr, ind-1);
		return getCnt(arr, ind-1);
	}

Can you rephrase the question? It is hard to figure out what it is asking...

This question is really a challenge. Are all the questions at this level so vague??
For all of those that didn't understandd the question, it is asking to find all the sub-sequences of numbers of the array that can be mapped into letters.
For example the array {1, 1, 1} has three sub-sequences {1,1,1} {1, {11}} {{11}, 1}. That is taking all the three elements as different letters, grouping the last two elements of the array as one letter or grouping the two first elements of the array as a letter. One important thing to note is that you can't take arbitrary elements of the array like for example the first element and the third one. We can see this on the next example as some possibilities are discarded because the values are not adjacent. Another important thing to note is that you have to discard all sub-sequences that lead to invalid mappings that is all mappings that contains numbers not between 1 and 26. I hope this explanation helped. Here is the solving code in python.

def compute_number(n):
    res = 0
    for exp, value in enumerate(reversed(n)):
        res += value * 10 ** exp
    return res

def compute_combinations(n):
    if len(n) == 1: return (n,)
    solutions = []
    for x in range(1, len(n)):
        c = compute_combinations(n[x:])
        solutions.extend(map(lambda r: n[:x] + r, c))
        number = compute_number(n[:x])
        if number > 0 and number <= 26:
            solutions.extend(map(lambda r: (number,) + r, c))
            
    number = compute_number(n)
    if number > 0 and number <= 26:
        solutions.append((number,))
    
    return set(filter(lambda x: 0 not in x, solutions))

Dynamic Programming solution:

int getCnt(int[] input) {
	    int[] A = new int[input.length + 1];
	    A[0] = 1;

	    for(int i=1; i<input.length+1; i++) {
	      A[i] = 0;
	      if(input[i-1] > 0) {
	        A[i] += A[i-1];
	      }
	      if (i > 1 && (10*input[i-2] + input[i-1]) <= 26) {
	        A[i] += A[i-2];
	      }
	    }
	    return A[input.length];
	}

Fixed Anon's Dynamic programming solution:

public static void main(String[] args) {
        int[] test1 = new int[] { 0 };
        System.out.println("Test 1 : " + getCountDynamic(test1));

        int[] test2 = new int[] { 1, 1, 1, 1 };
        System.out.println("Test 2 : " + getCountDynamic(test2));

        int[] test3 = new int[] { 1, 1, 0 };
        System.out.println("Test 3 : " + getCountDynamic(test3));
    }

    private static int getCountDynamic(int[] given) {
        if (given.length == 0)
            return 0;

        int counter[] = new int[given.length];
        counter[given.length-1] = (given[given.length-1] > 0 ? 1 : 0);

        for(int i=given.length-2; i >= 0; i--) {
            if (given[i] > 0 && ((given[i]*10 + given[i+1]) <=26))
                counter[i] = 1 + counter[i+1];
            else
                counter[i] = counter[i+1];
        }
        return counter[0];
    }

Test 1 : 0
Test 2 : 4
Test 3 : 2

static void FindSubsets(int[] a, int k, int[] data, int n, ref int count)
        {
            if (IsSolution(a, k, data, n))
            {
                count ++;
            }
            else
            {
                k++;
                var candidates = GetCandidates(data, n);
                foreach (Tuple<int, int> c in candidates)
                {
                    a[k] = c.Item1;
                    FindSubsets(a, k, data, c.Item2, ref count);
                }
            }
        }

        static List<Tuple<int,int>> GetCandidates(int[] data, int n)
        {
           
            List<Tuple<int, int>> ret = new List<Tuple<int, int>>();
            for (int i = n; i < data.Length; i++)
            {
                int cnt = 0;
                for (int j = n, m = 0; j <= i; j++, m++)
                {
                    cnt += (int)(Math.Pow(10, i-j)*data[j]);
                }
              
                ret.Add(new Tuple<int, int>(cnt, i+1));
            }
            return ret;
        }
        static bool IsSolution(int[] a, int k, int[] data, int n)
        {
            List<int> anwers = new List<int>();
            bool ret = false;
            if (n == data.Length)
            {
                ret = true;
                for (int i=0; i<= k; i++)
                {
                    if (a[i] < 1 || a[i] > 26)
                    {
                        ret = false;
                        break;
                    }
                    else
                    {
                        anwers.Add(a[i]);
                    }
                }
            }
            
            return ret;
        }

select a portion of the array from the beginning, if its value is between 1 and 26, count how many ways the rest of the array can be written, recursively.

int findCombs(int [] arr){
	if(arr.length==0) return 0;
	return findCombs(arr,0);
}

int findCombs(int[] arr, int ind){
	if(ind==arr.length) return 1; // found a valid combination
	int sumOfCombinations=0;
	int sumOfInds = 0;
	for(int i=ind; i<arr.length; i++)  {
		sumOfInds = sumOfInds*10 + arr[i];
		if(sumOfInds>=1 && sumOfInds<=26)
			sumOfCombinations += findCombs(arr,i+1);
		}
	}
}