CODEWITHSUNDEEP
algorithm
user12461664
user12461664

Reputation:

Efficiently find the smallest 'steady number' larger than a given integer

Let us call a number "steady" if sum of digits on odd positions is equal to sum of digits on even positions. For example 132 or 4059. Given a number N, program should output smallest/first "steady" number greater than N. For example if N = 4, answer = 11, if N = 123123, answer = 123134. But the constraint is that N can be very large. Number of digits in N can be 100. And time limit is 1 second.

My approach was to take in N as a string store each digit in array of int type and add 1 using long arithmetic, than test if the number is steady or not, if Yes output it, if No add 1 again and test if it is steady. Do this until you get the answer.

It works on many tests, but when the difference between oddSum and EvenSum is very large like in 9090909090 program exceeds time limit. I could not come up with other algorithm. Intuitively I think there might be some pattern in swapping several last digits with each other and if necessary add or subtract something to them, but I don't know. I prefer a good HINT instead of answer, because I want to do it myself.

Upvotes: 2

Views: 197

Answers (3)

David Schwartz
David Schwartz

Reputation: 182829

Use the algorithm that you would use. It goes like this:

Input: 9090909090

Input: 9090909090 Odd:0 Even:45

Input: 909090909? Odd:0 Even:45
Clearly no digit will work, we can make the odd at most 9

Input: 90909090?? Odd:0 Even:36
Clearly no digit will work, we removed a 9 and there is no larger digit (we have to make the number larger)

Input: 9090909??? Odd:0 Even:36
Clearly no digit will work. Even is bigger than odd, we can only raise odd to 18

Input: 909090???? Odd:0 Even:27 Clearly no digit will work, we removed a 9

Input: 90909????? Odd:0 Even:27 Perhaps a 9 will work.

Input: 909099???? Odd:9 Even:27 Zero is the smallest number that might work

Input: 9090990??? Odd:9 Even:27 We need 18 more and only have two digits, so 9 is the smallest number that can work

Input: 90909909?? Odd:18 Even:27 Zero is the smallest number that can work.

Input: 909099090? Odd:18 Even:27 9 is the only number that can work

Input: 9090990909 Odd:27 Even:27 Success

Do you see the method? Remove digits while a solution is impossible then add them back until you have the solution. At first, remove digits until a solution is possible. Only a number than the one you removed can be used. Then add numbers back using the smallest one possible at each stage until you have the solution.

Upvotes: 1

Dave
Dave

Reputation: 9085

Find the parity with the smaller sum. Starting from the smallest digit of that parity, increase digits of that parity to the min of 9 and the remaining increase needed.

This gets you a larger steady number, but it may be too big.

E.g., 107 gets us 187, but 110 would do.

Next, repeatedly decrement the value of the nonzero digit in the largest position of each parity in our steady number where doing so doesn't reduce us below our target.

187,176,165,154,143,132,121,110

This last step as written is linear in the number of decrements. That's fast enough since there are at most 9*digits of them, but it can be optimized.

Upvotes: 0

user7517879
user7517879

Reputation:

You can try Digit DP technique . Your parameter can be recur(pos,oddsum,evensum,str) your state transitions will be like this :

bool ans=0 
for(int i=0;i<10;i++)
{
    ans|=recur(pos+1,oddsum+(pos%2?i:0),evensum+(pos%2?i:0),str+(i+'0') 
    if(ans) return 1;

}

Base case :

if(pos>=n) return oddsum==evensum;

Memorization: You only need to save pos,oddsum,evensum in your DP array. So your DP array will be DP[100][100*10][100*10]. This is 10^8 and will cause MLE, you have to prune some memory.

As oddsum+evensum<9*100 , we can have only one parameter SUM and add / subtract when odd/even . So our new recursion will look like this :
recur(pos,sum,str) state transitions will be like this :

bool ans=0 
for(int i=0;i<10;i++)
{
    ans|=recur(pos+1,SUM+(pos%2?i:-i),str+(i+'0') 
    if(ans) return 1;
}

Base case :

if(pos>=n) return SUM==0;

Memorization: now our Dp array will be 2d having [pos][sum] . we can say DP[100][10*100]

Upvotes: 0

Related Questions