We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Mathematics
  3. Number Theory
  4. The Chosen One
  5. Discussions

The Chosen One

Sort by

recency

|

24 Discussions

|

  • jesnavas15
     + 1 comment

    Since I'm in the wedding business, I'm constantly looking for convenient solutions and tools. So, I found this site https://www.quoteroller.com/proposal-templates/wedding-organizer-proposal-template/, which has a lot of great document templates, including the wedding proposal I was looking for. I needed to make the necessary changes, which took me a few minutes, and then I immediately sent the document to the client.

  • DivyamKakkar24
     + 0 comments

    from math import gcd as g n = int(input().strip())

    a = list(map(int, input().rstrip().split()))

    if len(a) == 1: print(a[0] + 1) else:**

    pre = [0] * len(a)
suf = [0] * len(a)

for i in range(len(a)):
    if i == 0:
        pre[i] = a[i]
    else:
        pre[i] = g(pre[i - 1], a[i])

for i in range(len(a)-1, -1, -1):
    if i == len(a) - 1:
        suf[i] = a[i]
    else:
        suf[i] = g(suf[i + 1], a[i])

final_prefix = []

for i in range(len(a)):
    if i == 0:
        final_prefix.append(suf[i + 1])
    elif i == len(a) - 1:
        final_prefix.append(pre[i - 1])
    else:
        final_prefix.append(g(pre[i - 1], suf[i + 1]))

net = {}

for i in final_prefix:
    if i in net:
        net[i] += 1
    else:
        net[i] = 1

for i in net:
    if net[i] == 1:
        ans = i
        break

print(ans)

  • sreeragh_ar
     + 1 comment

    Find the most difficult element. Remove it and calculate gcd of the rest of elemnts.

    let X be a set of numbers. let Y be a superset of X (i.e X + {one or more elemnts} ) GCD of Y is less than or equal to GCD of X (more members less common factors, lower gcd)

    In the problem,

    Iterate and calculate gcd from left to right. Whenever a decline in gcd is observed save that as 'difficult element', continue this (update the 'difficult element' when another decline in gcd is observed - this is a more difficult element than the previous one) towards the end of elements.

    So finally we get the most difficult element. If there was no decline in gcd then that means the first element was the most difficult one. Remove that most difficult element and find gcd of the rest of the elemnts in the set. This GCD will not be a divisor of the difficult element. (That is the requirement in the question, find a number which divides all elements except one)

    Let the numbers be {a0, a1, a2, ... an} calculate gcd(a0, a1), then gcd(a0, a1, a2), then gcd(a0, a1, a2, a3) ... gcd(a0, a1,...an) whenver new gcd is less than previous gcd, save the elemnt which caused the decline.

    Make use of the associative property of GCD i.e

    gcd(a0, a1, a2) = gcd(gcd(a0, a1), a2)

    gcd(a0, a1, a2, a3) = gcd(gcd(a0, a1, a2), a3)

  • ajaibalu_cr_7
     + 0 comments
    #include <bits/stdc++.h>
#define ll long long 
using namespace std;

ll __gcd(ll a, ll b){
    if(b == 0)
        return a;
    return __gcd(b,a%b);
}

signed main()
{
    ll n ;
    cin >> n;
    
    ll a[100000+1];
    
    for(ll i=0;i<n;++i)
        cin >> a[i];
        
    sort(a,a+n);
        
    if(n==1){
        cout << a[0] + 1 << endl;
        return 0;
    }
    
    assert(n >= 2);
    ll prefix[100000+1]{0} , suffix[100000+1]{0};
    
    ll gcd = 0;
    for(ll i=0;i<n;++i){
        gcd = __gcd(gcd,a[i]);
        prefix[i] = gcd;
    }
    
    gcd = 0;
    for(ll i=n-1;i>=0;--i){
        gcd = __gcd(gcd,a[i]);
        suffix[i] = gcd;
    }
    
    if(a[0]%suffix[1]){
        cout << suffix[1] << endl;
    }
    else if(a[n-1]%prefix[n-2])
    {
        cout << prefix[n-2] << endl;
    }
    else{
    for(ll i=1;i<n-1;++i){
        ll preGcd = __gcd(suffix[i+1],prefix[i-1]);
        if(a[i]%preGcd)
            {
                cout << preGcd << endl;
                break;
            }
    }
    }   
    return 0;
}

  • socialscloud
     + 0 comments
    x = int(input()) - 1
given = list(map(int, input().split(" ")))
a = 1
while True:
    count = 0
    for num in given:
        if num % a == 0:
            count += 1
    if count == x:
        print(a)
        break
    a += 1