• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Interview Question Doubt

 
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Alice and Bob are playing a game on two numbers A and B. Bob has to select a random number X from [1,B].Bob wins the game if gcd(X,B) == gcd(A,B).

Find the probability of Bob wining the game, for given A and B. Let S denotes integer part of probability after multiplying it by pow(10,6).Your task is to find S.

Input format:
The first line contains a long, A, denoting the first given number.
The second line contains a long, B, denoting the second given number.

Constraints:
1 <= A <= 10^12
1 <= B <= 10^12

Input :
4
1

Output:
1000000

Input:
2
10

Output:
4000000

This is what I did, but I kept getting TLE(Time Limit Exceeded) whenever I submit. Please suggest me how I can optimize my solution.

 
Saloon Keeper
Posts: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Well, you can already cut your runtime in half by actually using your gcdAB variable. It's very unlikely that will be enough though. You need a smarter solution.

Instead of comparing gcd(x,B) to gcd(A,B) for each value x, it's probably more efficient if you define a separate function isGcd(gcdAB, x, B) that checks whether gcdAB is the greatest common divisor of x and B, without actually calling gcd(x,B) for each x. Such a function can be optimized much more easily than gcd(), for instance by eliminating values of x that aren't a multiple of gcdAB.
 
Why should I lose weight? They make bigger overalls. And they sure don't make overalls for tiny ads:
a bit of art, as a gift, the permaculture playing cards
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic