UVA Problem 11428 ( Cubes ) Solution:
Click here to go to this problem in uva Online Judge.
Solving Technique:
In this problem we are to find the value of “x” and “y”, given “N” from the formula below,
N = x3 – y3
If there are no solution just print “No solution” ( without quotes ).One line that may be confusing is, “If there is more than one solution then output the one with smallest value of y”.
Looping from 1 to square root N is enough. Also an important statement is checking if “x” cube is greater than “N”. Otherwise we calculate we will get a negative result. Because if “x” cube is less than or equal “n”, then there is another “y” cube subtracted from it so it will become negative but we were given positive numbers.
for(x=1; x<=sqrt(n);){
if(x*x*x > n){
/*check for y code goes here*/
}
++x;
}
If “x” cube is greater than “N” then it may be a possible value of “x”. Now we need to calculate for “y” to make sure. In order to do that we loop “j” from 1 to x-1 ( We can’t loop till i otherwise x and y will be equal which result in 0. Also we loop from 1 because subtracting 0 doesn’t change anything ).
/*reaches here only if x cube is greater than N*/
for(y=1; y<x;){
if(x*x*x - y*y*y == n){
works = 1; /* set flag for breaking outer loop and printing x y */
break; /* break inner loop since x cube minus y cube is equal to N, means we found the answer */
}
++y;
}
if(works) break; /* break the outer loop since we found the answer we should loop anymore */
Now i check if “x” cube minus “y” cube is equal to N. In that case i use a flag set it as true ( 1 ) and break the loop. It is important that if the flag is true we exit the outer loop otherwise it’ll keep looping and will give us wrong answer.
That’s it now just print value of x y or, No solution.
Important: Be sure to add or print a new line after each output. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.
Input:
7 37 12 0
Output:
2 1 4 3 No solution
Code Without Optimization:
/*
* Author: Quickgrid ( Asif Ahmed )
* Site: https://quickgrid.wordpress.com
*/
#include<stdio.h>
#include<math.h>
int main(){
int n;
while (scanf("%d", &n) && n){
int works = 0, x, y;
for (x = 1; x <= sqrt(n);){
if (x*x*x > n){
for (y = 1; y < x;){
if (x*x*x - y*y*y == n){
works = 1;
break;
}
++y;
}
if (works) break;
}
++x;
}
if (works){
printf("%d %d\n", x, y);
}else{
printf("No solution\n");
}
}
return 0;
}
With Some Optimization:
/*
* @author Quickgrid ( Asif Ahmed )
* @link https://quickgrid.wordpress.com
*/
#include<stdio.h>
#include<math.h>
int main(){
register unsigned x, y;
unsigned n, k;
while (scanf("%u", &n) && n){
unsigned works = 0;
for (x = 1, k = sqrt(n); x <= k;){
unsigned xcube = x * x * x;
if (xcube > n){
for (y = 1; y < x;){
if (xcube - y * y * y == n){
works = 1;
break;
}
++y;
}
if (works)
break;
}
++x;
}
if (works)
printf("%u %u\n", x, y);
else
printf("No solution\n");
}
return 0;
}
Quickgrid 