trjhtr

The problem I am trying to solve is as follows:

F. Reducing Salary

time limit per test: 2 seconds

memory limit per test: 256 megabytes

Sohieb started working at Hogwarts School of Witchcraft and Wizardry.
Ibrahim The school headmaster told him that he will get a positive
integer salary equals X, then Ibrahim made a spell that erase the
right most digit of X every month.

For example if he gets X = 1234 in the first month, the second month
he will get X = 123 and in the third month X = 12, and so on.

After a few months Sohieb realized that he didn't get a salary because
X became Zero.

Sohieb now has a total money equals Y which is his salary for all the
previous months, but he can't remember what was the value of X. Could
you help him by telling him what value of X makes his total money
equals Y.

Input

The only line of the input contains a single integer Y (1 ≤ Y ≤
10¹⁸)

Output

Print single integer — the value of X which makes the total money
equals Y. If there is many values of X holds print "ManySolutions"
(without the quotes). If there is no X makes the total money equal
Y print -1.

Examples:

input 1 output 1
input 3000 output 2701
input 565 output -1

import java.util.Scanner;
public class Salary 

public static void main(String args) 
 Scanner input = new Scanner(System.in);
 int left, right, sal;
 left =0;
 right = input.nextInt();
 sal = right;
 int presal = init(sal,left,right);
 System.out.println(presal);

public static int init(int sal, int left, int right)
 int mid = (left+right)/2;
 int count =mid;
 int sum =0;
 while (count>0)
 sum+=count;
 count/=10;
 


 while (left>=0 && left<=right)
 if(sum<sal)
 return init(sal,mid+1,right);
 
 else if(sum>sal)
 return init(sal,left,mid-1);
 
 else if(sum==sal)
 return mid;
 
 
 return -1;
 

Before trying to improve the performance let's do a general review
of your code and clean it up a little.

Spacing

The code is not indented correctly. The use of (horizontal) whitespace
is inconsistent. I would suggest to leave at least spaces around
operators, keywords, and ... blocks.

Variable names

Many variables names could be chosen better. For example:

right = input.nextInt();

does not indicate that this is the total salary.

public static int init(int sal, int left, int right)

does not tell anything about what the function does.
int count inside that function is not a count but a (running) sum.

Separate computation from I/O

Separating the actual computation from the I/O makes the main
method short, increases the clarity of the program, and allows you to add unit tests easily.

Use separate functions for self-contained tasks

The computation of the total salary from the current candidate
value in the binary search is done inside the search function.
Better move this to a separate function

private static int totalSalary(int initialSalary) 
 ...

because it is independent of the search algorithm. It also makes
the search function shorter and more self-explaining.

Also the initial call of the recursive search function is stuffed
into the main function:

left =0;
right = input.nextInt();
sal = right;
int presal = init(sal,left,right);

Again we can move this to a separate function:

private static int initialSalary(int totalSalary) 
 return binarySearch(totalSalary, 0, totalSalary);

The binary search function

• 
  

  All code paths inside

  
  
  

  
  

   while (left>=0 && left<=right)
   // ...
   
  

  
  

  
  
  

  return from the function, therefore an if would express that
  more clearly.

  
  



• I do not see why the left>=0 is necessary.



• 
  

  The medium index

  
  
  

  
  

  int mid = (left+right)/2;
  

  
  

  
  
  

  and the corresponding salary is computed even if right < left, i.e.
  for an empty search interval.

  
  

I find it simpler to do a binary search in a half-open interval
$ [textlow, texthigh) $

Summarizing the suggested changes so far, the program could look like
this:

import java.util.Scanner;

public class Salary 

 public static void main(String args) 

 Scanner input = new Scanner(System.in);
 int totalSalary = input.nextInt();
 int initialSalary = initialSalary(totalSalary);
 System.out.println(initialSalary);
 

 private static int totalSalary(int initialSalary) 
 int salary = initialSalary;
 int sum = 0;
 while (salary > 0) 
 sum += salary;
 salary /= 10;
 
 return sum;
 

 private static int initialSalary(int totalSalary) 
 return binarySearch(totalSalary, 0, totalSalary + 1);
 

 // Binary search original salary for given `totalSalary` in interval
 // `low` (included) ... `high` (excluded).
 private static int binarySearch(int totalSalary, int low, int high) 
 if (low >= high) 
 // Empty interval: not found
 return -1;
 else 
 int mid = (low + high)/2;
 int total = totalSalary(mid);
 if (total == totalSalary) 
 // Found at `mid`
 return mid;
 else if (total > totalSalary) 
 // Value at `mid` is too large, continue search in lower half.
 return binarySearch(totalSalary, low, mid);
 else 
 // Value at `mid` is too small, continue search in upper half.
 return binarySearch(totalSalary, mid + 1, high);
 
 
 

That is not faster than your version, but (hopefully) better to
understand, maintain and test.

(Another step towards more reusable code would be to define a binary search
which takes a function or lambda expression as parameter.)

Performance improvements

You do a binary search for the original salary, which is already quite
efficient. To make it even faster, the initial search interval can
be narrowed.

The initial salary $ S $ and the total salary $ T $ are related by
$$
T = S + leftlfloor fracS10 rightrfloor
+ leftlfloor fracS100 rightrfloor
+ leftlfloor fracS1000 rightrfloor + ldots
$$

It follows that
$$
T le S + fracS10 + fracS100 + fracS1000 + ldots
= frac10 S9
$$
and therefore
$$
S le frac9 T10 , .
$$

For an estimate in the other direction we can use
$$
T ge S + fracS10 - 1
$$
which implies
$$
S le frac10 (T+1)11 , .
$$

As an example, for the input value $ 3000 $ this gives a search
interval $ 2700 ldots 2728 $ instead of $ 0 ldots 3000 $.

To use this improved bounds, only one function has to be updated:

 private static int initialSalary(int totalSalary) 
 int lowerBound = (totalSalary * 9)/10;
 int upperBound = ((totalSalary + 1)*10)/11;
 return binarySearch(totalSalary, lowerBound, upperBound + 1);
 

Addendum: Integer ranges

For input values up to $ 10^18 $ the Java int (which is
a signed 32-bit integer) is not large enough. You'll have to use
long instead.

The most optimized solution is the following:

public static void main(String args) throws IOException 
 int input = 0;
 int b;
 while ((b = System.in.read()) != -1) b > 57)
 break;
 input = input * 10 + (b - 48);
 
 int answer = new int 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -1, 10, 11, ...;
 System.out.println(answer[input]);

It reads input argument directly from System.in without messing with Scanners, and computes the answer in a single lookup. The answer array can be easily precomputed.

Your solution is quite good in terms of performance, but since the input is in range [1..1018], the authors don't force people to try to be optimal.