Interviewstreet Puzzle – Lucky Numbers – 1

Addiction is bad, but I must admit that Interview Street Challenges can be very addictive. This week-end I have started with there latest programming puzzle Lucky Number. Very simple puzzle, you are supposed to find sum of the digits of number then find sum of the square of the digits of a number, see if the both the results are prime , If yes then call that number as Lucky Number. I have started as usual with brute-force approach, and I knew that they are going to reject my approach right away. Here is the first version of the code, will update this post once I improve some more.

#include <iostream>
#include <string>
#include <numeric>
/* trying with brute force approach */
long long sum_of_digits(long long input) {
	long long total = 0;
	while (input != 0) {
		total += input % 10;
		input /= 10;
	}
	return total;
}
long long sum_of_square_digits(long long input) {
	long long total = 0;
	while (input != 0) {
		total += (input % 10)* (input % 10);
		input /= 10;
	}
	return total;
}
bool isPrime(long long x) {
        long long max = static_cast <long long> (x);
        if (x <= 0 || x == 1 || (x % 2 == 0 && x != 2)) return false;
        for (long long i = 3; i < max; i += 2)
            if (x % i == 0)
                return false;
        return true;
}
int main ( int argc, char** argv) {
	int T;
	std::cin >> T;

	while ( T-- ) {
		int result = 0;
		long long A;
		long long B;
		std::cin >> A >> B;
		for ( long long i = A; i <= B; i++) {
			long long sum        = sum_of_digits( i );
			long long sum_square = sum_of_square_digits( i );
			if ( isPrime(sum) && isPrime(sum_square)){
				result++;
			}
		}
		std::cout << result << std::endl;
	}
	return 0;
}

Update 2
Just doing some silly optimization but it also does not accepted by the robot. So this is what I was thinking
1. No need to call square computing function if the sum of the digits are not prime
2. No need compute mod operation twice
3. no need to iterate over the number separately and can be clubed into single function call.

#include <iostream>
#include <string>
#include <numeric>
/* trying with brute force approach */
void sum_of_digits_and_square(long long input, long long& sum, long long& sum_square) {
	sum = sum_square = 0L;
	while (input != 0L) {
		long long digit = input % 10L;
		sum        += digit;
		sum_square += digit * digit;
		input /= 10L;
	}	
}
bool isPrime(long long x) {
	long long max = static_cast <long long> (x);
	if (x <= 0 || x == 1 || (x % 2 == 0 && x != 2)) return false;
	for (long long i = 3; i < max; i += 2)
		if (x % i == 0)
			return false;
	return true;
}
int main ( int argc, char** argv) {
	int T;
	std::cin >> T;

	while ( T-- ) {
		int result = 0;
		long long A;
		long long B;
		std::cin >> A >> B;
		for ( long long i = A; i <= B; i++) {
			long long sum        = 0;
			long long sum_square = 0;
			sum_of_digits_and_square(i,sum,sum_square);
			if ( isPrime(sum)) {
				if ( isPrime(sum_square)){
					result++;
				}
			}
		}
		std::cout << result << std::endl;
	}
	return 0;
}

Attempt No – 2

#include <iostream>
#include <cmath>

bool isPrime(long long number) {
	if (number == 1L)
		return false;
	if (number == 2L)
		return true;
	if((number & 1) == 0)
		return false;
	for (long long  d = 3L; d <= (long long)sqrt((double)number); d += 2)
		if (number % d == 0)
			return false;
	return true;
}
int main ( int argc, char** argv) {
	int T;
	std::cin >> T;

	while ( T-- ) {
		int result = 0;
		long long A;
		long long B;
		std::cin >> A >> B;
		for ( register long long i = A; i <= B; ++i) {
			long long sum        = 0;
			long long sum_square = 0;
			for (register long long  n = i; n > 0; sum += n % 10, n /= 10) ;
			if ( isPrime(sum)) {
				for (register long long  n = i; n > 0; sum_square += (n % 10) * (n % 10), n /= 10) ;
				if ( isPrime(sum_square)){
					result++;
				}
			}
		}
		std::cout << result << std::endl;
	}
	return 0;
}
Advertisements

5 thoughts on “Interviewstreet Puzzle – Lucky Numbers – 1

  1. I’m stuck on this problem as well with no hope in sight. So far I’ve managed to pass 1/9 testcases and I’ve done all the optimizing that I could think of. Have you had any luck with passing all the testcases?

  2. given that max value can be 999999…(18 times ). So max sqaure sum can be 1458. So i have kept one array which keeps primes upto 1458 (there some 236 primes). After that i am doing a binary search.

    But still i got TLE.

    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

  3. Pingback: Longlong max | Janetbosshart

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s