Java - a noob needs some help

[Luka]

So im taking a programming class and we were given an assigment, where you get 2 numbers, x and y, x<y, and you need to find how many numbers between those 2 numbers including the 2 numbers is divisible by atleast one of 2,3,5. They run tests that time out in a second, the problem i have is i have a brute force method with a for and 3 ifs checking every number individually, can anyone help me come up with a solution that will not take as much time, im really out of ideas at this point. Not too advanced if can please, im still a noob. Thanks

[Mo5]

So im taking a programming class and we were given an assigment, where you get 2 numbers, x and y, x<y, and you need to find how many numbers between those 2 numbers including the 2 numbers is divisible by atleast one of 2,3,5. They run tests that time out in a second, the problem i have is i have a brute force method with a for and 3 ifs checking every number individually, can anyone help me come up with a solution that will not take as much time, im really out of ideas at this point. Not too advanced if can please, im still a noob. Thanks

 

So you have something like this?

import java.util.*;class Test{public static void main(String[] args){Scanner sc = new Scanner(System.in);System.out.print("Input x: ");int x = sc.nextInt();System.out.print("Input y: ");int y = sc.nextInt();int z = 0;for(int i=x;i<=y;i++){if(i%2==0){z++; continue;}if(i%3==0){z++; continue;}if(i%5==0){z++; continue;}}System.out.println("Z = "+z);}}

[Nuluvius]

Place the input range into one list and the divisor range into another list. Loop the input list and on each iteration have a nested loop run against the divisor list, if a division is possible then no need to check any more, move on to the next input number.

 

There will likely be a more efficient method to do this but sadly I have dyscalculia so can only assist with architecture and logic

[Luka]

 

So you have something like this?

import java.util.*;class Test{public static void main(String[] args){Scanner sc = new Scanner(System.in);System.out.print("Input x: ");int x = sc.nextInt();System.out.print("Input y: ");int y = sc.nextInt();int z = 0;for(int i=x;i<=y;i++){if(i%2==0){z++; continue;}if(i%3==0){z++; continue;}if(i%5==0){z++; continue;}}System.out.println("Z = "+z);}}

Yep i have something very similar to this, however one input i need to pass in a second is 123456789012345678 and 876543210987654321, and it takes forever brute forcing it

[Luka]

The only other thing i can think of is y-x then dividing that by 2 3 and 5, adding that up then dividing y-x by 6 10 and 15 and adding that up then subtract it from 2 3 5 so doubles dont show but this thing doesnt seem to be right either

[Mo5]

Yep i have something very similar to this, however one input i need to pass in a second is 123456789012345678 and 876543210987654321, and it takes forever brute forcing it

for 2 (and 5) you can just check the last digit

for 3 just sum all numbers and see if the sum is dividable by 3

[Luka]

for 2 (and 5) you can just check the last digit

for 3 just sum all numbers and see if the sum is dividable by 3

Yeah, but how do i go about writing that

[Mo5]

Yeah, but how do i go about writing that

2 and 5 is easy

if((i%10)%2==0){z++; continue;}

if(i%10==0 || i%10==5){z++; continue;}

[Mo5]

import java.util.*;class Test{public static long Sum(long i){long a = i;long sum = 0;while(a > 0){long ii = a%10;sum += i;a /= 10;}return sum;}public static void main(String[] args){Scanner sc = new Scanner(System.in);System.out.print("Input x: ");long x = sc.nextLong();System.out.print("Input y: ");long y = sc.nextLong();long z = 0;long sum = 0;for(long i=x;i<=y;i++){long temp = i%10;if(temp%2==0 || temp == 5 || Sum(i)%3==0){z++;}}System.out.println("Z = "+z);}}

This does work, but it's still not under a second for really big numbers (up to 8 digits it's fairly quick)

 

Edit: Tried it with '123456789012345678' and '876543210987654321' and after 10 minutes I gave up

[madknight3]

So im taking a programming class and we were given an assigment, where you get 2 numbers, x and y, x<y, and you need to find how many numbers between those 2 numbers including the 2 numbers is divisible by atleast one of 2,3,5. They run tests that time out in a second, the problem i have is i have a brute force method with a for and 3 ifs checking every number individually, can anyone help me come up with a solution that will not take as much time, im really out of ideas at this point. Not too advanced if can please, im still a noob. Thanks

What are the min and max values of x and y? Do you have any sample input/output examples given to you for basic testing? Could you list them if you do?

 

This should help provide an optimization, however, it's not enough. You'll still need to optimize it further.

    public static long DivisibleBy235(long x, long y) {        // Start with getting the amount divisible by two        long count = DivisibleBy2(x,y);        // Add the amount divisible by 3 and 5 to count.        // Only consider odd numbers as to not duplicate        // numbers divisible by 2. Make sure x and y are        // correct for this.        if (x > 0 && x%2==0) x++;        if (y%2==0) y--;        // TODO: This is still too inefficient so you'll still have to improve it        for (long i = x; i <= y; i+=2) {            if (i%3==0 || i%5==0) count++;        }        // Return value        return count;    }    public static long DivisibleBy2(long x, long y) {        if (x > 0 && x%2==0) x--;        if (y%2==0) y++;        return (y-x)/2;    }

[darth_bubbles]

2 and 5 is easy

if((i%10)%2==0){z++; continue;}

if(i%10==0 || i%10==5){z++; continue;}

I'm also learning Java so please correct me if I'm wrong, but can't you do something like this to find the last number?

int length = x.length();int lastnum = x.substring(length-1,length);

[madknight3]

 

I'm also learning Java so please correct me if I'm wrong, but can't you do something like this to find the last number?

int length = x.length();int lastnum = x.substring(length-1,length);

Only if you're dealing with 'x' as a String. In this case, it's a long. I expect it's much more inefficient to convert it to a String, get the substring, then convert back to a number.

[darth_bubbles]

Only if you're dealing with 'x' as a String. In this case, it's a long. I expect it's much more inefficient to convert it to a String, get the substring, then convert back to a number.

Okay I see. Thanks

[darth_bubbles]

Only if you're dealing with 'x' as a String. In this case, it's a long. I expect it's much more inefficient to convert it to a String, get the substring, then convert back to a number.

I guess that should be obvious considering it's called substring 

[madknight3]

Hmm, I just realized that simply looping over one of the examples takes too long to complete

// -------------------------------------- Test 1 --------------------------------------// Values used in test 1 (ie: all positive integers)long x = 1;long y = Integer.MAX_VALUE;final long startTime = System.currentTimeMillis();for (long i = x; i <= y; ++i);final long endTime = System.currentTimeMillis();System.out.println("Total execution time: " + (endTime - startTime) );// -------------------------------------- Test 2 --------------------------------------// Values used in test 2 (one of your tests)long x2 = 123456789012345678L;long y2 = 876543210987654321L;final long startTime2 = System.currentTimeMillis();for (long i = x2; i <= y2; ++i);final long endTime2 = System.currentTimeMillis();System.out.println("Total execution time: " + (endTime2 - startTime2) );

Here's the output (in milliseconds):

Test 1 output:Total execution time: 628Test 2 output:Total execution time: (hasn't stopped even after 12 minutes)

So if that is indeed a valid test, and you are limited to 1 second run time, you'll need to find a way to immensely limit the loop range, or find the answer without a loop.

 

It seems to me what you need is some smart mathematics.

[MrSuperb]

Hmm, I just realized that simply looping over one of the examples takes too long to complete

// -------------------------------------- Test 1 --------------------------------------// Values used in test 1 (ie: all positive integers)long x = 1;long y = Integer.MAX_VALUE;final long startTime = System.currentTimeMillis();for (long i = x; i <= y; ++i);final long endTime = System.currentTimeMillis();System.out.println("Total execution time: " + (endTime - startTime) );// -------------------------------------- Test 2 --------------------------------------// Values used in test 2 (one of your tests)long x2 = 123456789012345678L;long y2 = 876543210987654321L;final long startTime2 = System.currentTimeMillis();for (long i = x2; i <= y2; ++i);final long endTime2 = System.currentTimeMillis();System.out.println("Total execution time: " + (endTime2 - startTime2) );

Here's the output (in milliseconds):

Test 1 output:Total execution time: 628Test 2 output:Total execution time: (hasn't stopped even after 12 minutes)

So if that is indeed a valid test, and you are limited to 1 second run time, you'll need to find a way to immensely limit the loop range, or find the answer without a loop.

 

It seems to me what you need is some smart mathematics.

 

0.628s times 2^32 = 2 697 239 462s

== 44 953 991 min

== 749 233 h

== 31 218 days

== 85 years

 

 

edit: btw it is probably significantly less than 85 years to loop from 0 to the max long value, but it will still take some time.

[MrSuperb]

a small hint:

1) you don't actually need a for loop

2) every other number is divisible by 2 (i.e. 2,4,6,8,etc.)

3) every 3rd number is divisible by 3 (i.e. 3,6,9,12,etc.)

4) every 5th number is divisible by 5 (i.e. 5,10,15,20,etc.)

 

So what about numbers that are divisible by both 2 and 3?

- every 6th number is divisible by both 2 and 3 (i.e. 6,12,18,etc.)

[MrSuperb]

1) checking every number for divisibility is expensive (i.e. takes long time) because divisions are expensive.

2) generating that numbers would be significantly cheaper but still be expensive

3) if you don't need the actual numbers, but rather just the total count, than this can be done quite cheap in a single line of code.

[Luka]

1) checking every number for divisibility is expensive (i.e. takes long time) because divisions are expensive.

2) generating that numbers would be significantly cheaper but still be expensive

3) if you don't need the actual numbers, but rather just the total count, than this can be done quite cheap in a single line of code.

All i would need is the total count of numbers between x and y what are divisible by 2 3 5 (no duplicates as in it musnt count numbers that are divisible say by 2 and 3 as 2 numbers but as 1)

[MrSuperb]

All i would need is the total count of numbers between x and y what are divisible by 2 3 5 (no duplicates as in it musnt count numbers that are divisible say by 2 and 3 as 2 numbers but as 1)

 

the count of numbers divisible by 2, 3 or 5 for 1 to n is:

(n/2) + (n/3) + (n/5) - (n/(2*3)) - (n/(2*5)) - (n/(3*5)) + (n/(2*3*5))

==

(n/2) + (n/3) + (n/5) - (n/6) - (n/10) - (n/15) + (n/30)

 

(!!! Integer division !!!)

 

 

If you want the count for x to n then you have to substract

(x-1/2) + (x-1/3) + (x-1/5) - (x-1/6) - (x-1/10) - (x-1/15) + (x-1/30)

from

(n/2) + (n/3) + (n/5) - (n/6) - (n/10) - (n/15) + (n/30)

[MrSuperb]

complexity is O(1) compared to a brute force O(n).

 

Time needed for the single calculation is not measureable (i.e. <1 ms)

[MrSuperb]

for 123456789012345678 to 876543210987654321

the number of integers divisibile by 2,3 or 5 is: 552263376115226339

[Midnight]

The trick is not iterate through the entire range. Use math (and strings).

[MrSuperb]

The trick is not iterate through the entire range. Use math (and strings).

no strings needed at all. I basicaly already wrote the solution

[Midnight]

no strings needed at all. I basicaly already wrote the solution

 

When the OP said large numbers, I thought he meant numbers which are hundreds to thousands of digits long, which can't be represented in int or a long.