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

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