-
-
Save phaniram/1682408 to your computer and use it in GitHub Desktop.
| package interviewstreet; | |
| import java.util.Scanner; | |
| public class lucky_num { | |
| public static void main(String[] args) { | |
| lucky_num sr = new lucky_num(); | |
| Scanner scanner = new Scanner(System.in); | |
| int no_cases = scanner.nextInt(); | |
| for (int i = 0; i < no_cases; i++) { | |
| System.out.println(sr.solve(scanner.nextLong(), scanner.nextLong())); | |
| } | |
| } | |
| private int solve(long l, long m) { | |
| int count = 0; | |
| for (long i = l; i <= m; i++) { | |
| if (logic(i)) { | |
| count++; | |
| } | |
| } | |
| return count; | |
| } | |
| private boolean logic(long i) { | |
| return (isSUM(i) && isSUMsq(i)); | |
| } | |
| private boolean isSUMsq(long i) { | |
| int sum = 0; | |
| while (i > 9) { | |
| long k = i % 10; | |
| i = i / 10; | |
| sum += k * k; | |
| } | |
| sum += i * i; | |
| return (isPrime(sum)); | |
| } | |
| private boolean isSUM(long i) { | |
| int sum = 0; | |
| while (i > 9) { | |
| long k = i % 10; | |
| i = i / 10; | |
| sum += k; | |
| } | |
| sum += i; | |
| return (isPrime(sum)); | |
| } | |
| private boolean isPrime(int num) { | |
| if(num==2) | |
| return true; | |
| // check if n is a multiple of 2 | |
| if (num % 2 == 0 || num==1 ) | |
| return false; | |
| // if not, then just check the odds | |
| for (int i = 3; i * i <= num; i += 2) { | |
| if (num % i == 0) | |
| return false; | |
| } | |
| return true; | |
| } | |
| } |
| /** | |
| * | |
| * @author cypronmaya | |
| */ | |
| import java.util.Scanner; | |
| class Solution { | |
| boolean[] check; | |
| public static void main(String[] args) { | |
| Solution sr = new Solution(); | |
| sr.sieve(3358); | |
| Scanner scanner = new Scanner(System.in); | |
| int no_cases = scanner.nextInt(); | |
| for (int i = 0; i < no_cases; i++) { | |
| System.out.println(sr.solve(scanner.nextLong(), scanner.nextLong())); | |
| } | |
| } | |
| private int solve(long l, long m) { | |
| int count = 0; | |
| for (long i = l; i <= m; i++) { | |
| if (logic(i)) { | |
| count++; | |
| } | |
| } | |
| return count; | |
| } | |
| private boolean logic(long i) { | |
| return (isSUM_SUMsq(i)); | |
| } | |
| private boolean isSUM_SUMsq(long i) | |
| { | |
| int sum = 0; | |
| int sumsq=0; | |
| while (i > 9) { | |
| long k = i % 10; | |
| i = i / 10; | |
| sum += k; | |
| sumsq += k * k; | |
| } | |
| sum += i; | |
| sumsq +=i*i; | |
| if(check[sum]) | |
| { | |
| return check[sumsq]; | |
| } | |
| return false; | |
| } | |
| private void sieve(int upto) { | |
| int N = upto; | |
| boolean[] isPrime = new boolean[N + 1]; | |
| for (int i = 2; i <= N; i++) { | |
| isPrime[i] = true; | |
| } | |
| for (int i = 2; i * i <= N; i++) { | |
| if (isPrime[i]) { | |
| for (int j = i; i * j <= N; j++) { | |
| isPrime[i * j] = false; | |
| } | |
| } | |
| } | |
| this.check = isPrime; | |
| } | |
| } |
@advetus :
this will give you TLE. I have tried your aproach. I have kept the primes numbers upto n * 81 and for each of the number between A and B i am checking (with binary search ) whether the sum and square sum is available in the array
why do u hv to keep upto n_81? log10(B)_81 =3358, where B 10^18
@phaniram My bad, by n I meant the maximum number of digits aka log10(B)
@nagendracse
My solution was accepted but it wasn't optimal so it only passes 1/9 testcases. Maybe if I cache prime numbers it will pass more testcases. It should run faster because a binary search should be faster than prime checking through division. I'll post my soultion later today.
@phani ram : max sqaure sum will be 999 999 999..(17 times) which is equal to 17 * 81.
@advtus :
accepted means it should pass all the test cases.
@ nagendracse:
I have tried the same approach as you (table of primes for 1 - 1458) and thought for sure this would be fast enough. Here is the weird part. For a set of test cases I came up with, by my own timer, it takes my "naive" code 2+ minutes to solve, but only 6 seconds with the optimized table version. However, on interviewstreet site, BOTH versions take approximately 45 seconds for whatever test cases they have. I cannot understand how for my test cases (which do go all the way to very big numbers), my optimized code is faster by a factor of TWENTY compared to my naive code. But when submitted to the challenge site, both versions perform about the same. That makes absolutely no sense.
@The111 :
Through clever trickery I managed to get part of their testcases. Each testcase will contain 10000 intervals and intervals are very large numbers. Here are the few first intervals in testcase 2 : 487162823133062956 to 681177519744583339, 305402977547472311 to 387592951340431309, etc. PM me for a complete list.
Regarding execution time, the testing server will kill a process after a certain amount of time, you'll see a message: "Killed Success". Try running your program against a large number of testcases and see how much time it takes to process them.
@adevtus
I am not sure where you are seeing that message about "killed success." I've never seen it anywhere. I just see, on my submissions tab, "Your code exceeded the timelimit for this testcase," and then the time it took to execute. My times range from 1 second for the case 1 (which I pass) to 45 seconds for case 9. I am assuming I still get the correct results all the cases, since if I use code with bad logic, I get a message about incorrect results (in addition to execution time, whether it is under or over the limit). But even for case 1, which I pass, no matter which version of my optimized code I submit, it takes almost exactly 1 second. And I have a new version of my optimized code which does in ONE second which my last version took 6 seconds to do, which my first version took 120+ seconds to do. So I've optimized my code by 10000% now, yet every version still takes the same amount of time +/- 5% on test servers. That doesn't make any sense.
Also not sure how you are sniping testcases, but I am not sure how ANY code could handle such a large interval as you suggest. I let one of those run for minutes on my most optimized code, on a pretty fast CPU, and was not able to complete even one interval. To think I could complete 90,000 such intervals (9 test cases times 10,000 intervals per case as you say) in less than 5 seconds, when I can't even complete 1 in several minutes, is just impossible.
One thing I do know, I apparently picked the hardest problem on InterviewStreet for my first one. I tabulated the "success rates" of all the problems based on the stats shown, and Lucky Numbers is the lowest with 2% success (the highest has ~50% success). And now I can't give up...
@nagendracse
"So the main problem is that given A and B we are iterating over every elements . we need to find a way so that we can skip few elements in between"
True. Or make each iteration much faster, which I was able to do my removing 90% of the modulo and division operations from my loops. In the end it sped my code up by a factor of 10 on my machine. But did not even change by any significant amount the execution of testcases on the InterviewStreet servers.
@The111
I got those testcases by throwing an exception with the input that was given, the site will print out a short message with the exception that was thrown. I'm not really sure if the numbers are correct. So far I'm only able to pass the first testcase, how many testcases does your solution pass? Have you used any particular algorithms or just programmer's intuition?
As far as passing all testcases, I think it's impossible, you need to be a top-level coder but it's good exercise and I did learn a lot.
I sorted the digits and stored in a table.so next time a number with same digits come . It simply skips.
For example:
no : 12345 is equal to 53421 and 42315.
More over I discarded the zero if it occurs in the number. so 1023 will be considered as 123 .
But this also didn't helped me. It ran same time as brute force.
Here is how I know this challenge is impossible. The following code does nothing more than read the first line from the input file (the number of test cases) and then print zero for every single one. Of course it is going to be incorrect. But guess what else. It takes 4.4 seconds on InterviewStreet test server! That leaves 0.6 seconds to compute sums of digits and check if they are prime. Not very realistic at all. Try this code yourself!
import java.io.*;
public class Solution
{
public static void main(String[] args)
{
int numOfTests = 0;
int[] lucky;
BufferedReader myReader = null;
try
{
myReader = new BufferedReader(new InputStreamReader(System.in));
numOfTests = Integer.parseInt(myReader.readLine());
}
catch (Exception e)
{
System.err.println("Error:" + e.getMessage());
}
lucky = new int[numOfTests];
int i = 0;
for ( ; i < numOfTests - 1; i++)
{
System.out.println(lucky[i]);
}
System.out.print(lucky[i]);
}
}
Some new ideas to toss around:
There are two main loops to this thing:
outer loop: iterate through test cases
inner loop: iterate through each number in the range of the current test case
As a test, if you reduce the inner loop to only perform one trivial calculation (i.e. not even check for primality) you will exceed the time limit. Further testing has also shown that you are always cut off after more than 5 seconds in a loop. So you don't know exactly HOW much you are exceeding the time limit by. But by playing with the size of the inner loop, it is possible to iterate up to 20,000 times and stay under the time limit (so obviously the ranges involved in each case are much larger than that).
The conclusion is one that nagendracse made already. It is simply impossible to check every single number in each test range and stay within the time limit. So some sort of pattern must be detected in the digit sums, and then by simply looking at the lower and upper limits of the range of the current test case, you can somehow determine how many lucky numbers are within that range. Maybe you have to check some of the numbers within that range, but at the very most you can perform ~20,000 checks per test case (probably far less if your check loop has more than one trivial calculation).
If it was possible to cut and paste a ridiculous amount of code, and if it didn't require more than 256MB, I'd suggest tabulating the entire table of lucky numbers from 1 to 10^18. Obviously not possible, but I am thinking about generating a text listing of that data, just so I can try to search it for patterns. I am fairly confident that is the key to this puzzle. Maybe some sort of binary search that allows you to zero in on certain subranges in the "top range" 1 to 10^18, using a reasonable amount of operations.
I found those values through an algorithm, starting small with ranges like 1-100, 1-1000, etc, that were easy to verify my algorithm was working right. They may not be right, I still have a lot of verification to do.
hi i want a csharp solution to this problem pls help i am not able to take input as needed to be taken
@thahir
I've uploaded my C# solution for this problem: https://gist.github.com/2020902
Let me know if it helps
I'm going to try generating all prime numbers up to n * 81 at the start of the program, or maybe I'll just write them in code and the program will only check if the curent number is in the prime array. I'll have the code ready later today and post it on my account. Let's hope this works and thanks for the info :D