Forum

Post 03.10.2012   # 1
Subject Problem 400 - DearNumbers

This problem can be solved in a single line sweep or scan. The key here is to keep a variable that will have the count of the prime numbers that were up to m places before our current position.


So whenever you find a prime number, that variable will increase and when you pass m numbers after a certain prime number, that variable will decrease.


Knowing when to increase the variable is easy task. To decrease it you have to store the previous prime numbers that are still active, or just the numbers on which the active primes will expire. Note that I use the word active for primes that are less then m places away from us and contribute to the dearness of the number that we are inspecting.


One solution may use a Boolean array to note on which numbers an active prime will expire:

public class DearNumbers {
    public int dearestNumber(int b, int e, int m) {
       
        //////////////////////////////
        // GENERATING PRIME NUMBERS
        boolean[] p = new boolean[1000001];
        for (int i = 2; i < p.length; i++) {
            p = true;
        }
        for (int i = 2; i < p.length; i++) {
            if (p) {
                for (int j = 2 * i; j < p.length; j += i) {
                    p[j] = false;
                }
            }
        }
        //////////////////////////////
       
        //////////////////////////////
        // LINESWEEP
        int[] vals = new int[1000001];
        boolean[] decrease = new boolean[1000001];
        int ammount = 0;
        for (int i = 1; i < vals.length; i++) {
            // if you dont want to keep an array of milion ints
            // you may want to merge LINESWEEP and GETMAX, then
            // you can delete int[] vals and replace the next line
            // with line that will store the number between b and e
            // that has the max ammount
            vals = ammount;
           
            if (decrease) {
                ammount--;
            }
            if (p) {
                ammount++;
                if (i + m < decrease.length) {
                    decrease[i + m] = true;
                }
            }
        }
        //////////////////////////////
       
        //////////////////////////////
        // GETMAX
        int maxVal = 0, maxNum = 0;
        for (int i = b; i <= e; i++) {
            if (vals > maxVal) {
                maxVal = vals;
                maxNum = i;
            }
        }
        //////////////////////////////
        return maxNum;
    }
}

obi1kenobi used a queue in which he kept the active primes, when the last prime in the queue is no longer valid, ne just removes it:

#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include
<list>
#include <deque>
#include <stack>
#include
<map>
#include <utility>
#include <cstring>
#include <sstream>
#include <climits>
#include <bitset>
#define DBG(x) if(DEBUG) cout << (#x) << ": " << (x) << "\n"
#define DBGM(x,y) if(DEBUG) cout << (#x) << "," << (#y) << ": " << (x) << " " << (y) << "\n"
#define DBGT(x,y,z) if(DEBUG) cout << (#x) << "," << (#y) << "," << (#z) << ": " << (x) << " " << (y) << ' ' << (z) << "\n"
#define FDBG(x,str) str << (#x) << ": " << (x) << "\n"
#define FDBGM(x,y,str) str << (#x) << "," << (#y) << ": " << (x) << " " << (y) << "\n"
#define FDBGT(x,y,z,str) str << (#x) << "," << (#y) << "," << (#z) << ": " << (x) << " " << (y) << " " << (z) << "\n"
#define MSI(x,y) memset((x),(y),sizeof((x)))
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c).begin() i = (c).begin(); i != (c).end(); i++)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define DEBUG false
//#if DEBUG
//#include <iostream>
//#include <fstream>
//#include <cassert>
//#endif
using namespace std;
class DearNumbers
{
  public:
    vector<int> primes;
    bool isPrime(int n)
    {
        if(n==2) return true;
        if(n&1)
        {
            for(int i=0;i<sz(primes);i++)
            {
                if(primes[i]*primes[i]>n) break;
                if(!(n%primes[i]))
                {
                    return false;
                }
            }
            primes.pb(n);
            return true;
        } else return false;
    }
    int dearestNumber(int b, int e, int m)
    {
        int i;
        queue<int> pr;
        int dear=0;
        int best=-1;
        int id;
        for(i=3;i<b;i+=2)
        {
            isPrime(i);
        }
        for(i=max(b-m,2);i<=e;i++)
        {
            if(i>=b && best<dear)
            {
                best = dear;
                id=i;
            }
            if(isPrime(i))
            {
                pr.push(i);
                dear++;
            }
            if(!pr.empty() && (pr.front()+m)==i)
            {
                dear--;
                pr.pop();
            }
        }
        return id;
    }
};

palikrushev is offline Reply

Please login to post reply.