7 days ago

admin 1.6k

Hyderabad

Q1

Alex Book

Alex has a book of an infinite number of pages. Imagine practically when a book is opened 2 pages get opened 1 on left and 1 on the right side except starting page which doesn't have any page to its left. In an open book left and right page numbers which open together form a spread. 1st page doesn't have any page to its left so page number 1 itself forms a spread and further all spreads have 2-page numbers in them. The first spread contains page 1, the second spread contains pages 2 and 3, the third spread contains pages 4 and 5 and the fourth spread contains pages 6 and 7 and soon.

Task

Determine the first-page number of the very first spread where the sum of the digits of page numbers is S. If no such spread exists, print -1.

Note: Page number 1 itself forms a spread and thus is the first page for the first spread.

Example

Assumption

• S = 9

Approach

• The first spread contains page 1 only. the sum of digits of page number is 1.

• The second spread contains pages 2 and 3. The sum of digits of page numbers is 5(2+3).

• The third spread contains pages 4 and 5. the sum of digits of page numbers is 9(4+5).

So the third spread is the 1st spread whose sum of digits of page numbers is 9.

Thus, the answer is 4

Function Description 

Complete the function solve provided in the editor. This function takes the following parameters and returns the required answer.

3 months ago

Ayush Gangwani 1.2k

New Delhi

Solution

Analysis

As we don't have the constraints for the problem, we can try to solve the problem for the best constraints possible. We can work out the following observations for the problem:

• If s == 1, we simply return 1
• Otherwise, we can notice that we just need to find the smallest even number e such that sum of digits of e and e+1 equals to s. Now suppose that the sum of digits of e is x. Since e is an even number, we can claim that the sum of digits of e+1 will be x+1. Hence , x+x+1 = s => x = (s-1)/2. Hence the problem reduces to finding the smallest even number e with a given sum of digits.

To solve this, we can assign the largest even digit at the units place possible and then keep assigning as many 9 as we can on the other positions until the sum becomes smaller than 9. After which we assign the remaining sum (which is now a digit itself) to the most significant position.

PseudoCode

solve(s):
    if(s == 1):                             //edge case for the first page
        return 1
    if(s%2 == 0):                           //sum of an even and an odd number is always odd
        return -1                           //thus if s is even, we return -1
    x = (s-1)/2                             //x is the sum of digits of the required number
    ans = ""                                //ans can be large, hence we use a string
    for digit in {8,6,4,2,0}:               //trying out the largest digit possible at units place 
        if(x >= digit):                     
            ans.append(digit)
            x -= digit
            while(x>9):                     //keep adding 9 as many times as possible
                ans.append(9)
                x -= 9 
            if(x):                          //we then append the remaining sum (if its not zero)
                ans.append(x)
    ans.reverse()
    return ans