WalmartLabs Coding Solution and Question

WalmartLabs Coding Solution and Question
http://www.geeksforgeeks.org/walmart-lab-interview-experience-set-7-off-campus/
1. Given a number N. print in how many ways it can be represented as N = a+b+c+d , 1< =a< =b< =c< = d; 1<=N< = 5000
2. Given two number l and r (l<=r<=10^6) find most frequent digit among all prime numbers between l and r inclusive. if frequency is same print highest digit.
http://gohired.in/2015/10/walmart-coding-solution-and-question/

Solution 1) What you want to find : number of ways a given number can be formatted. so see the observation
Lets DP[n,k] be the number of ways to represent n as sum of k numbers. Then you are looking for DP[n,4].

For N = 4: Only 1 way - 1 + 1 + 1 + 1
For N = 5: Only 1 way - 1 + 1 + 1 + 2
For N = 6: 2 ways     - 1 + 1 + 1 + 3
                        1 + 1 + 2 + 2
For N = 7: 3 ways     - 1 + 1 + 1 + 4
                        1 + 1 + 2 + 3
                        1 + 2 + 2 + 2
For N = 8: 5 ways     - 1 + 1 + 1 + 5
                        1 + 1 + 2 + 4
                        1 + 1 + 3 + 3
                        1 + 2 + 2 + 3
                        2 + 2 + 2 + 2

So in order to understand this one, lets make Dynamic Programming solution where n = number
k= number of parts here k=4 (a,b,c,d)

DP[n,1] = 1
DP[n,2] = DP[n-2, 2] + DP[n-1,1]
DP[n,3] = DP[n-3, 3] + DP[n-1,2]
DP[n,4] = DP[n-4, 4] + DP[n-1,3]

So Final DP equation is ==>

DP[n,k] = DP[n-k, k] + DP[n-1,k-1]

http://stackoverflow.com/questions/32818613/number-of-ways-to-divide-a-number

Lets DP[n,k] be the number of ways to represent n as sum of k numbers. Then you are looking for DP[n,4].

DP[n,1] = 1
DP[n,2] = DP[n-2, 2] + DP[n-1,1] = n / 2
DP[n,3] = DP[n-3, 3] + DP[n-1,2]
DP[n,4] = DP[n-4, 4] + DP[n-1,3]

I will only explain the last line and you can see right away, why others are true.

Let's take one case of n=a+b+c+d.

If a > 1, then n-4 = (a-1)+(b-1)+(c-1)+(d-1) is a valid sum for DP[n-4,4].

If a = 1, then n-1 = b+c+d is a valid sum for DP[n-1,3].

Also in reverse:

For each valid n-4 = x+y+z+t we have a valid n=(x+1)+(y+1)+(z+1)+(t+1).

For each valid n-1 = x+y+z we have a valid n=1+x+y+z.

Solution 2) We need to find Prime numbers in range [L,R]. and need to find a highest occuring digit and if frequency is same, the highest number is answer.

What can we do for this program is to divide this prog in 3 parts.
1 ) Find prime numbers and store them in Array.
2 ) Create new array from this array with all just digits
ex : prime’s array = [2, 3, 5, 7, 11, 13, 17]
so new Array will be = [2, 3, 5, 7, 1, 1, 1, 3, 1, 7]
3) Find occurrence of each digit like [0,3,1,2,0,1,0,2] (0 comes 0 time, 1 comes 3 times, and so one…)
Now get the highest digit, return its index, if such numbers are more than one, return the highest index.

Coding Soultion :
for Step 1) Use sieve-of-eratosthenes’s code available at http://www.geeksforgeeks.org/sieve-of-eratosthenes/for Step 2) its simple Array formation, traverse array, % and /  each number by 10 and get digits 

Read full article from WalmartLabs Coding Solution and Question