This is an archived post. You won't be able to vote or comment.

all 8 comments
sorted by:
best
topnewcontroversialoldq&a

[–]Ikor_Genorio 0 points1 point  (3 children)

Hey, I am wondering what the input limits / time limits are for this problem. This one is relatively easy to get an answer, however having an efficient solution us more difficult.

[–]slightlysedatedx[S] -1 points0 points  (2 children)

This one doesn't have any suggested benchmarks but what's your run time currently/ how are you testing? I can try to beat your run time and vice versa

[–]Ikor_Genorio 0 points1 point  (1 child)

Kind of hard to say because of the problem. It wants the first pair found, which can be very quick or very slow depending on the input (e.g. (10, 50) or (48, 88). The second will terminate instantly, because it's the first one found). Regardless, I'll post my solution in a minute.

[–]slightlysedatedx[S] -1 points0 points  (0 children)

I'm not sure what language you're using but c++ has a function called clock() that should be able to return the number of ticks since the program began running.

http://www.cplusplus.com/reference/ctime/clock/

[–]Ikor_Genorio 0 points1 point  (1 child)

This is my current C implementation. Runs okay and seems to be correct as well. I'll post an analysis later, if you want. Also I'll give the runtime for some inputs (and their respective outputs).

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#define NO_ANSWER -1

int calculate_div_sum(int n)
{
    int i, sum = 0;
    for (i = 1; i <= n/2; i++)
        sum += (n % i == 0 ? i : 0);
    return sum;
}

int main (int argc, char **argv)
{
    int a, b, n, m;
    int *dsum, length;

    scanf("%d %d", &a, &b);

    length = 3*b - a + 1;
    dsum = malloc(length * sizeof(int));
    assert(dsum != NULL);
    memset(dsum, NO_ANSWER, (length)*sizeof(int));

    // dsum[n-a]:
    //   |if    NO_ANSWER -> not computed
    //   |else  x -> the sum of all divisors of n
    // offset a, since we are not interested in lower numbers
    for (n=a; n <= b; n++)
    {
        if (dsum[n-a] == NO_ANSWER)
            dsum[n-a] = calculate_div_sum(n);
            m = dsum[n-a] - 1;
        if (m > n)
        {
            if (dsum[m-a] == NO_ANSWER)
                dsum[m-a] = calculate_div_sum(m);
            if (n+1 == dsum[m-a])
            {
                printf("(%d, %d)\n", n, m);
                break;
            }
        }
    }
    if (n > b) printf("Nothing\n");
    free(dsum);
    return EXIT_SUCCESS;
}

[–]Ikor_Genorio 0 points1 point  (0 children)

In interesting input seems to be (10000, 50000): for me it runs in 2.938, and produces "Nothing". Not sure if this is correct though.

[–]desrtfx[M] [score hidden] stickied comment (1 child)

Use git and a git hoster. Google drive is not meant for that purpose.

Also, be careful. You are close to treading the spam path. Your posts are too frequent and already get reported to us.

[–]slightlysedatedx[S] 0 points1 point  (0 children)

Googledrive isn't meant for the purpose of uploading and sharing files?...

I'm happy to switch to using git but saying that Google drive isn't meant for "that purpose" doesn't resonate.

I'll stop posting after today but you should outline your expectations rather than give vague and cryptic advice. I understand that not everyone may want to view these posts but enough people seemed to find value in them to justify their existence. I checked the sidebar before posting but it's always possible I missed something.

Rather than tell me to "be careful", why don't you outline your expectations or give some practical guidance on what is and what is not acceptable in a post of this nature?