## Thursday, January 7, 2016

### 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