Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

singh23saurav's blog

By singh23saurav, history, 4 weeks ago, In English

Problem Breakdown 1. Find LCM for Each Pair: * For each unique pair (a[i], a[j]) in the array a, compute the Least Common Multiple (LCM). * The pairs include (a[i], a[i]) for each single number, as well as every combination of distinct numbers (a[i], a[j]) 2. Calculate Minimum Multiplier: * For each pair (a[i], a[j]), find the smallest integer mmm such that: LCM(a[i],a[j])×m≥k {LCM}(a[i], a[j]) * m .= k LCM(a[i],a[j])×m≥k * This product should also be a multiple of k. 3. Calculate the Cost: * For each pair, compute the cost of the smallest multiplier mmm, which is simply the value of mmm. * Sum up the costs for all pairs to get the total answer. eg: [4,5,6] k=12 ans=>3+12+2+2*(3+2+1)=29, give a complexity less than O(N2) less than 108 as n<=10**5 pairs->(4,4) ,(5,5,) ,(6,6) ,(4,5) ,(5,4) ,(5,6) ,(6,5) , (4,6), (6,4) so(lcm(5,5))=5*12=60 multiple of k leaves value of cost =12 for this pair similarly for others

https://leetcode.com/discuss/interview-question/6029649/google-amaon

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by singh23saurav (previous revision, new revision, compare).

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by singh23saurav (previous revision, new revision, compare).

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by singh23saurav (previous revision, new revision, compare).

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by singh23saurav (previous revision, new revision, compare).

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by singh23saurav (previous revision, new revision, compare).