UVA 13131:divisors TLE in java

Question

0.00/5 (No votes)

See more:

I solved a UVA problem: https://onlinejudge.org/external/131/13131.pdf[^]

My solution:

void solve(Scanner sc, int n, int k) {
        int sum=0;
        for(int i=1; i<=n; i++) {
            if(n%i==0 && i%k!=0)sum+=i;
        }
        System.out.println(sum);
}

I got TLE in UVA. It was obvious to get TLE.

So, I tried to optimize my solution and implemented this way:

void solve(Scanner sc, int n, int k) {
        int sum=0;
        for(int i=1; i*i<n; i++) {
            if(n%i==0 && i%k!=0)sum+=i;
            if(n%(n/i)==0 && (n/i)%k!=0)sum+=(n/i);
        }
        System.out.println(sum);
    }

But still I am getting TLE. To understand what's happening here I implemented the second approach in C++ and got accepted. But in Java I am getting TLE. I have no idea why is this happening and can't find out how to get ac. I am requesting you to help me solve the issue.. I am getting depressed, I love java, I don't want to shift in C++ for problem solving.

What I have tried:

Edit: Thanks to CPallini and Patrice T (See their answers and comments)
This is the last submitted solution. Improved the code but still getting TLE.
They both suggested to try a different approach "the list of prime factors of the number".

//package pac1;
import java.util.Scanner;
public class Main{
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int t = sc.nextInt();
        while(t-->0) {
            int n = sc.nextInt();
            int k = sc.nextInt();
            int sum=0;
            int top = (int)Math.sqrt(n);
            for(int i=1; i<=top; i++) {
            	if(n%i==0 ){
            	    if(i%k!=0)sum+=i;
            	    if((n/i)%k!=0)sum+=(n/i);
            	}
            }
            System.out.println(sum);
        }
        
    }
}

Posted 8-Feb-23 19:28pm

Jahirul Sarker

Updated 9-Feb-23 14:34pm

v3

Add a Solution

2 solutions

Add a Solution

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

CPallini · Answer 1 · 2023-02-08T22:06:00

Solution 1

Try

Java

static int solve(int n, int k)
{
  int sum = 0;
  int i;
  for (i=1; i*i<n; ++i)
  {
    if ( n % i == 0)
    {
      if ( i % k != 0)
        sum += i;

      int j = n / i;
      if ( j  % k != 0)
        sum += j;
    }
  }
  if ( i*i == n)
  {
      if ( i % k != 0)
        sum += i;
  }
  return sum;
}

Note: your optimized solution is flawed: it adds twice to the sum the square root of N.

Posted 8-Feb-23 22:06pm

CPallini

Comments

Jahirul Sarker 9-Feb-23 4:40am

"your optimized solution is flawed: it adds twice to the sum the square root of N." I edited the mistake.
I submitted your solution. But still getting TLE. @CPallini

CPallini 9-Feb-23 4:51am

Then you may try a different approach, for example maintaining a list of prime numbers.

Jahirul Sarker 9-Feb-23 5:13am

I searched in Google for the solution of this problem in Java, but found no results. A user asked on this same issue in UVA discussion site.. but no reply has been given.

I don't know how to solve this problem by maintaining a list of prime numbers.

Patrice T 9-Feb-23 16:47pm

+5

CPallini 10-Feb-23 4:18am

Thank you.

Patrice T · Answer 2 · 2023-02-09T10:47:00

Quote:
I got TLE in UVA. It was obvious to get TLE.

This problem is worded the way of challenges sites, you need to know the strait forward solutions (or brute force) are never the solution.
You need to have deep understanding of the problem in order to apply algorithm simplifications and make your solution faster.
In this code, for any N, you loop N times: O(N)=N

Java

for(int i=1; i<=n; i++) {

In this code, for any N, you loop √N times: O(N)=√N

Java

for(int i=1; i*i<n; i++) {

But there is a multiplication on every loop.
In this code, √N multiplications are replace by a single square root function.

Java

Top=int(sqrt(N)
for(int i=1; i<=Top; i++) {

You need to take advantage of any possible shortcut in you code:
Everytime you find a divisor i of N, it imply that N/I is also a divisor of N, without further checking.
This code:

Java

if(n%i==0 && i%k!=0)sum+=i;
if(n%(n/i)==0 && (n/i)%k!=0)sum+=(n/i);

translate as

Java

if(n%i==0 ){
    if(i%k!=0)sum+=i;
    if((n/i)%k!=0)sum+=(n/i);
}
And there is more to find.

You also may want to play with the list of prime factors of the number.

UVA 13131:divisors TLE in java

2 solutions

Solution 1

Solution 2

Add your solution here

Preview 0

UVA 13131:divisors TLE in java

2 solutions

Solution 1

Solution 2

Add your solution here

Preview 0

Existing Members

...or Join us