randomrandom1810's blog

An interesting problem that was asked in online hiring test of salesforce.
By randomrandom1810, history, 23 months ago, In English

We are provided with 2 integers, F and K and we want to find an integer N such that

  • N is divisible by F
  • N is a number whose sum of digits is an integer K

return minimum N satisfying the 2 conditions.

constraints

1 <= F <= 495

1 <= K <= 5000

Please tell me how to approach this problem.

  • Vote: I like it
  • +28
  • Vote: I do not like it

Comments Comments (12)
| Write comment?
»
23 months ago, # |
  Vote: I like it +20 Vote: I do not like it

A brief approach :
$$$dp[i][j]$$$ denotes the minimum length of the number satisfying the given constraints, where $$$i$$$ denotes the remaining sum of the digits of the number, $$$j$$$ denotes the remainder when divided by $$$F$$$.
Transitions are simple : Assume you add digit $$$x$$$ in the current state $$$dp[i][j]$$$, then you will get $$$dp[i-x]$$$$$$[$$$$$$(j*10 + x)mod F]$$$and you have to take the $$$min$$$ of all the $$$10$$$ possibilities of digits.
Now, you have the $$$min$$$ length of the final answer, you can easily trace back the $$$dp$$$ values to get the final string (or number).

Time Complexity : $$$O(F*K)$$$

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    How to handle the cycle in the DP when adding digit $$$0$$$ repeatedly?

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      You can probably get around cycles through some casework:

      1. If remainder R is zero, it's always optimal to add a non-zero digit at this position.
      2. If remainder R is non-zero, then you have to consider all unique values of (R*10^x)%F before adding a non-zero digit to each of them.

      Nah wait this is probably too slow.

      → Reply
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Write iterative $$$dp$$$, and fill the table using BFS.

      → Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think in this transition, it is difficult to visit all the previous states first, for example, if we are on $$$dp[i][j]$$$, and we want to move to next state considering the number we are inserting is $$$0$$$, then the remainder can decrease as well as increase while the remaining sum is constant. How can you transition such that it is guaranteed all previous states have been visited?

    → Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How do you all get idea of dp states and transitions? I'm practicing dp since days, but still uncomfortable with DP, I'don't get the idea while solving and keep thinking in a wrong way. :/

    → Reply
    • »
      »
      »
      23 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Maintain a sheet for new DP states while solving. Make sure to read that sheet every month. Gradually you will build the intuition and will start solving the problems which use the same idea mentioned in your sheet.
      Also, I am not very good at DP, but this way helps me in improving DP.

      → Reply
»
23 months ago, # |
← Rev. 8   Vote: I like it +3 Vote: I do not like it

Let $$$dp[i][j]$$$ denote the min. no of digits a number can have such that it has sum of digits equals $$$i$$$ and gives remainder $$$j$$$ when divided by $$$F$$$.

Transitions can be done easily via forward-style DP. Once you know $$$dp[i][j]$$$ (say, its value is $$$x$$$), then if your $$$(x+1)$$$th digit is $$$z$$$, then $$$dp[i+z][(j + z*{10}^{x})\,mod F]<--min(dp[i+z][(j + z*{10}^{x})\,mod F],dp[i][j]+1)$$$

To built the number, start placing the leftmost digit $$$j$$$, such that it satisfies $$$dp[k-j][(-{10}^{dp[k][0]})\,mod\,F]$$$ is minimum, and repeat the process for remaining digits.

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Please correct me if I am wrong, I don't see how this works if the digit we are adding to the front i.e. z is 0

    $$$dp[i + 0][j + 0] := min(dp[i + 0][j + 0], dp[i][j] + 1)$$$

    A trivial example can be F=101, K=2 N should be 101

    → Reply
»
23 months ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

Found an exact problem on CF: https://codeforces.com/problemset/problem/1070/A

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution finds the minimum length of number which satisfies both the conditions.

Here is my recursive DP code

Code

I am unable to print the answer through DP table , Anyone pls Help :)

→ Reply