0
/**
 * @input A : Integer
 * 
 * @Output Integer
 */
int solve(int A){
    int ans,i;
    ans=0;
    i=1;
    while(i<=A){
        ans=((ans+def(i))%1000000007);
        i++;
    }
    return (ans);
}

int def(int m){
    int ans,k;
    ans=1;
    k=1;
    while(k<=m){
        if(gcd(k,m)==1){
            ans=ans*k;
        }
        k++;
    }
    return (ans%m);
}

int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b); 
}

main function is calling solve function, everything is fine. I just need to reduce the time complexity. For the input A: 114233 The expected output is 902650983, but my program is giving time limit exceeded. Please help. How can I reduce the time complexity in this problem?

Edit:

Actually main function is passing a value A to solve function then question has asked to implement these following functions:

Def P(m):
    ans=1
    k=1
    while k<=m:
        if GCD(k,m)==1:
            ans*=k
        k+=1
    return (ans % m)

def F(A):
    ans = 0
    i=1
    while i<=A:
        ans+=P(i)
        i+=1
    return ans % 1000000007
Alok Raj
  • 328
  • 3
  • 9
  • `ans+def(i)` would easily overflow – phuclv Aug 26 '18 at 12:55
  • 1
    of course it is time limit exceeded. if A = 100000, your main solve function will run 100K times, and inside def, it loops again from 1 to 100K. 100K * 100K = surely TLE. – rcs Aug 26 '18 at 12:57
  • How can I reduce this? I am stuck here for a long time – Alok Raj Aug 26 '18 at 12:59
  • 1
    Can you explain what the code is doing? – President James K. Polk Aug 26 '18 at 13:04
  • @JamesKPolk Please see the updated question. The title of the question is GCD knows no Limit. – Alok Raj Aug 26 '18 at 13:13
  • Do some math on the problem's statement. Read [How to debug small programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/). Avoid [integer overflow](https://en.wikipedia.org/wiki/Integer_overflow) or use [bignum](https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic)s – Basile Starynkevitch Aug 26 '18 at 13:20
  • 1
    and do not use recursion as it definitely does not help with performance – 0___________ Aug 26 '18 at 13:55
  • And: using `for()` loops will make your program more compact, and improve readability. – wildplasser Aug 26 '18 at 14:09
  • @P__J__ recursion does not hurt, as can be verified on godbolt's *Compiler Explorer*. Any half decent compiler is able to convert it into a loop through tail-call optimization. – Michael Veksler Aug 27 '18 at 14:07
  • The code is wrong. Running it to the end gives results different than what you claim. Replacing `ans=ans*k` with `ans=((long long)ans*k)%1000000007` fixes the overflow, but still does not get the expected result. Replacing `return (ans%m)` with `return ans%1000000007` does not help either. Had I known what you want, I'd be able to do something like: https://stackoverflow.com/q/51776619/4955498 – Michael Veksler Aug 27 '18 at 14:10
  • @MichaelVeksler one trivial example does not proof your very strong opinion. Compilers may in some circumstances convert it. But the key here is : **in some circumstances**. Recursion in most cases hurts the performance and safety of the code, and is barred in many industrial standards (MISRA for example) Should be avoided. – 0___________ Aug 27 '18 at 14:30
  • @P__J__ we are not talking about theoretical code, but about the `gcd` code above. And it is impossible to generalize, since sometimes recursion is faster and sometimes it is slower. Recursion can be faster, e.g., when performing an operation on all nodes of a balanced binary-search-tree (without pointers to parents), is much faster with recursion. Recursion can be slower or troublesome (due to stack depth limit) on many other problems. There is no general rule, and this has to be examined on a case-by-case basis. – Michael Veksler Aug 27 '18 at 14:38
  • @MichaelVeksler ok. discussion is pointless. As I wrote recursion is dangerous and banned in many standards. Usually is also slower. BTW please provide the benchmark which proofs this better recursion performance. – 0___________ Aug 27 '18 at 14:48
  • @P__J__, I was not able to send a direct message with a benchmark. Look at https://godbolt.org/z/yz5pzV , on wandbox.org the iterative code runs almost 10% slower, and is much more complex. It is possible to add another pointer to the structure (pointing to parent), but I specifically stated that the data has no pointer to parent in the problem requirement. In this case, recursion wins both on simplicity and speed. My point is, over-generalization is not doing any good, and things have to be examined on a case-by-case basis. – Michael Veksler Aug 27 '18 at 16:01

0 Answers0