Interview Street Challenges - Lucky Numbers

lucky_num.java

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;
	}
}

Solution1.java

/**
 *
 * @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;
    }
}

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.

http://stackoverflow.com/questions/9018614/algorithm-to-find-lucky-numbers/9020599#9020599 This might help u in solving.. You are in correct track. But how did you arrive at the the 4,686,825 unique digit combinations and 17,547. Let me know how u did it. Regards, Saravana.

…

On Sun, Feb 19, 2012 at 7:17 PM, The111 < ***@***.*** > wrote: I believe I've found the key to making this work, but it may still take a lot of coding to actually implement it. Consider this: For the range of numbers from 1 to 10^18, there are 4,686,825 unique digit combinations. However, they result in only 17,547 unique sum pairs, where a sum pair is the set of the two sums we are interested in. 17,547 is a MUCH more manageable number than 10^18. There's a lot more to it than that, but I think that may be the key. --- Reply to this email directly or view it on GitHub: https://gist.github.com/1682408

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

## LinkedIn I'd like to add you to my professional network on LinkedIn. - SaravanaKumar SaravanaKumar Nadar Graduate Assitanship at Rochester Institute of Technology Chennai Area, India Confirm that you know SaravanaKumar Nadar: https://www.linkedin.com/e/-eyzlk0-gzt4xwoq-72/isd/6302197814/XP2f2Qa_/?hs=false&tok=0mkgR6QPEDI581 ## You are receiving Invitation to Connect emails. Click to unsubscribe: http://www.linkedin.com/e/-eyzlk0-gzt4xwoq-72/u36IlaTBWqrDg3XI5etfSIdm9mX-6jz9U3hXP87maZOk61zcUDhXfITqYaOsU589G9hl9k7mftO-uiIxAfCOSr78AmX-IPI9Xl7lfUhzT2O46A8z5G/goo/reply%2Bg-1682408-dfefad955d12d0b154dcbe24a2736a412f39de13-1442087%40reply%2Egithub%2Ecom/20061/I2189524629_1/?hs=false&tok=2yQnER5DkDI581 (c) 2012 LinkedIn Corporation. 2029 Stierlin Ct, Mountain View, CA 94043, USA.

## LinkedIn Hi Nagendra, Your LinkedIn password has been reset successfully. Thank you, ## The LinkedIn Team This email was intended for Nagendra Kumar. Follow this link to learn why we include this information. http://www.linkedin.com/e/-eyzlk0-h37dkubc-67/plh/http%3A%2F%2Fhelp%2Elinkedin%2Ecom%2Fapp%2Fanswers%2Fdetail%2Fa_id%2F4788/-GXI/?hs=false&tok=1WXm3db6dtAlg1 (c) 2012, LinkedIn Corporation. 2029 Stierlin Ct. Mountain View, CA 94043, USA