Click here to Skip to main content
15,908,674 members
Please Sign up or sign in to vote.
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
Updated 9-Feb-23 14:34pm
v3

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.
 
Share this answer
 
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.
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.
 
Share this answer
 
v2
Comments
Jahirul Sarker 9-Feb-23 19:48pm    
Thank you. But still TLE.
Last submitted solution:
```
//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);
}

}
}
```
Patrice T 9-Feb-23 20:12pm    
This change is just 1 step closer to solution. You need to do real study of the problem, and probably try different solutions

Use Improve question to update your question.
So that everyone can pay attention to this information.
Jahirul Sarker 9-Feb-23 20:38pm    
I edited in "What have you tried" section.
CPallini 10-Feb-23 4:17am    
5.
Patrice T 10-Feb-23 12:04pm    
Hi, did you missed something ? :)

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



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900