âReducing Salaryâ challenge
Clash Royale CLAN TAG#URR8PPP
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0;
up vote
-1
down vote
favorite
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 â¤
1018)
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;
java programming-challenge
add a comment |Â
up vote
-1
down vote
favorite
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 â¤
1018)
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;
java programming-challenge
2
Your problem link redirects to codeforces.com and not to the actual problem. Does it require a login? Is this an active contest?
â Martin R
Apr 30 at 7:57
add a comment |Â
up vote
-1
down vote
favorite
up vote
-1
down vote
favorite
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 â¤
1018)
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;
java programming-challenge
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 â¤
1018)
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;
java programming-challenge
edited May 2 at 1:31
200_success
123k14142399
123k14142399
asked Apr 30 at 5:53
Sheikh Hanif
12
12
2
Your problem link redirects to codeforces.com and not to the actual problem. Does it require a login? Is this an active contest?
â Martin R
Apr 30 at 7:57
add a comment |Â
2
Your problem link redirects to codeforces.com and not to the actual problem. Does it require a login? Is this an active contest?
â Martin R
Apr 30 at 7:57
2
2
Your problem link redirects to codeforces.com and not to the actual problem. Does it require a login? Is this an active contest?
â Martin R
Apr 30 at 7:57
Your problem link redirects to codeforces.com and not to the actual problem. Does it require a login? Is this an active contest?
â Martin R
Apr 30 at 7:57
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
1
down vote
accepted
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 uselong
instead.
So far the solution is perfect. Thank you so much. But the input is too big number 1<totalSalary<10^18.
â Sheikh Hanif
May 1 at 11:48
@SheikhHanif: That was not apparent in your question originally. For numbers in that range you have to replace allint
bylong
â Martin R
May 1 at 13:01
I replace all int variables with long. But how can I know is there are multiple x values which sum up y.
â Sheikh Hanif
May 1 at 15:12
@SheikhHanif: If you found one solution then you could check the next smaller and larger value if it gives the same total salary. (But unless I am mistaken, that will never happen.)
â Martin R
May 1 at 15:35
add a comment |Â
up vote
0
down vote
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.
I doubt thatScanner.nextInt()
is a real performance problem if the input consists of a single line with a single number :)
â Martin R
Apr 30 at 10:22
@MartinR Me too :) But since the author wants the most optimized solution, removing an extra entity does the job. And actually I've had a lot of troubles with Scanner when input contained a few hundred thousands of numbers.
â ekaerovets
Apr 30 at 10:27
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
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 uselong
instead.
So far the solution is perfect. Thank you so much. But the input is too big number 1<totalSalary<10^18.
â Sheikh Hanif
May 1 at 11:48
@SheikhHanif: That was not apparent in your question originally. For numbers in that range you have to replace allint
bylong
â Martin R
May 1 at 13:01
I replace all int variables with long. But how can I know is there are multiple x values which sum up y.
â Sheikh Hanif
May 1 at 15:12
@SheikhHanif: If you found one solution then you could check the next smaller and larger value if it gives the same total salary. (But unless I am mistaken, that will never happen.)
â Martin R
May 1 at 15:35
add a comment |Â
up vote
1
down vote
accepted
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 uselong
instead.
So far the solution is perfect. Thank you so much. But the input is too big number 1<totalSalary<10^18.
â Sheikh Hanif
May 1 at 11:48
@SheikhHanif: That was not apparent in your question originally. For numbers in that range you have to replace allint
bylong
â Martin R
May 1 at 13:01
I replace all int variables with long. But how can I know is there are multiple x values which sum up y.
â Sheikh Hanif
May 1 at 15:12
@SheikhHanif: If you found one solution then you could check the next smaller and larger value if it gives the same total salary. (But unless I am mistaken, that will never happen.)
â Martin R
May 1 at 15:35
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
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 uselong
instead.
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 uselong
instead.
edited May 1 at 16:29
answered Apr 30 at 13:26
Martin R
14k12157
14k12157
So far the solution is perfect. Thank you so much. But the input is too big number 1<totalSalary<10^18.
â Sheikh Hanif
May 1 at 11:48
@SheikhHanif: That was not apparent in your question originally. For numbers in that range you have to replace allint
bylong
â Martin R
May 1 at 13:01
I replace all int variables with long. But how can I know is there are multiple x values which sum up y.
â Sheikh Hanif
May 1 at 15:12
@SheikhHanif: If you found one solution then you could check the next smaller and larger value if it gives the same total salary. (But unless I am mistaken, that will never happen.)
â Martin R
May 1 at 15:35
add a comment |Â
So far the solution is perfect. Thank you so much. But the input is too big number 1<totalSalary<10^18.
â Sheikh Hanif
May 1 at 11:48
@SheikhHanif: That was not apparent in your question originally. For numbers in that range you have to replace allint
bylong
â Martin R
May 1 at 13:01
I replace all int variables with long. But how can I know is there are multiple x values which sum up y.
â Sheikh Hanif
May 1 at 15:12
@SheikhHanif: If you found one solution then you could check the next smaller and larger value if it gives the same total salary. (But unless I am mistaken, that will never happen.)
â Martin R
May 1 at 15:35
So far the solution is perfect. Thank you so much. But the input is too big number 1<totalSalary<10^18.
â Sheikh Hanif
May 1 at 11:48
So far the solution is perfect. Thank you so much. But the input is too big number 1<totalSalary<10^18.
â Sheikh Hanif
May 1 at 11:48
@SheikhHanif: That was not apparent in your question originally. For numbers in that range you have to replace all
int
by long
â Martin R
May 1 at 13:01
@SheikhHanif: That was not apparent in your question originally. For numbers in that range you have to replace all
int
by long
â Martin R
May 1 at 13:01
I replace all int variables with long. But how can I know is there are multiple x values which sum up y.
â Sheikh Hanif
May 1 at 15:12
I replace all int variables with long. But how can I know is there are multiple x values which sum up y.
â Sheikh Hanif
May 1 at 15:12
@SheikhHanif: If you found one solution then you could check the next smaller and larger value if it gives the same total salary. (But unless I am mistaken, that will never happen.)
â Martin R
May 1 at 15:35
@SheikhHanif: If you found one solution then you could check the next smaller and larger value if it gives the same total salary. (But unless I am mistaken, that will never happen.)
â Martin R
May 1 at 15:35
add a comment |Â
up vote
0
down vote
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.
I doubt thatScanner.nextInt()
is a real performance problem if the input consists of a single line with a single number :)
â Martin R
Apr 30 at 10:22
@MartinR Me too :) But since the author wants the most optimized solution, removing an extra entity does the job. And actually I've had a lot of troubles with Scanner when input contained a few hundred thousands of numbers.
â ekaerovets
Apr 30 at 10:27
add a comment |Â
up vote
0
down vote
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.
I doubt thatScanner.nextInt()
is a real performance problem if the input consists of a single line with a single number :)
â Martin R
Apr 30 at 10:22
@MartinR Me too :) But since the author wants the most optimized solution, removing an extra entity does the job. And actually I've had a lot of troubles with Scanner when input contained a few hundred thousands of numbers.
â ekaerovets
Apr 30 at 10:27
add a comment |Â
up vote
0
down vote
up vote
0
down vote
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.
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.
answered Apr 30 at 9:50
ekaerovets
25613
25613
I doubt thatScanner.nextInt()
is a real performance problem if the input consists of a single line with a single number :)
â Martin R
Apr 30 at 10:22
@MartinR Me too :) But since the author wants the most optimized solution, removing an extra entity does the job. And actually I've had a lot of troubles with Scanner when input contained a few hundred thousands of numbers.
â ekaerovets
Apr 30 at 10:27
add a comment |Â
I doubt thatScanner.nextInt()
is a real performance problem if the input consists of a single line with a single number :)
â Martin R
Apr 30 at 10:22
@MartinR Me too :) But since the author wants the most optimized solution, removing an extra entity does the job. And actually I've had a lot of troubles with Scanner when input contained a few hundred thousands of numbers.
â ekaerovets
Apr 30 at 10:27
I doubt that
Scanner.nextInt()
is a real performance problem if the input consists of a single line with a single number :)â Martin R
Apr 30 at 10:22
I doubt that
Scanner.nextInt()
is a real performance problem if the input consists of a single line with a single number :)â Martin R
Apr 30 at 10:22
@MartinR Me too :) But since the author wants the most optimized solution, removing an extra entity does the job. And actually I've had a lot of troubles with Scanner when input contained a few hundred thousands of numbers.
â ekaerovets
Apr 30 at 10:27
@MartinR Me too :) But since the author wants the most optimized solution, removing an extra entity does the job. And actually I've had a lot of troubles with Scanner when input contained a few hundred thousands of numbers.
â ekaerovets
Apr 30 at 10:27
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f193240%2freducing-salary-challenge%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
2
Your problem link redirects to codeforces.com and not to the actual problem. Does it require a login? Is this an active contest?
â Martin R
Apr 30 at 7:57