HackerRank P sequences problem solution

In this HackerRank P-sequences problem solution, We call a sequence of N natural numbers (a1, a2, …, aN) a P-sequence if the product of any two adjacent numbers in it is not greater than P. In other words, if a sequence (a1, a2, …, aN) is a P-sequence, then ai * ai+1 ≤ P ∀ 1 ≤ i < N

You are given N and P. Your task is to find the number of such P-sequences of N integers modulo 10 to power9 plus 7.

Problem solution in Java.

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    public static long pSequences(int n, int p) {
    // Write your code here
    
        long P = 1000000007;
        int r = (int) Math.sqrt((double)p);

        long[] f = new long[2 * r + 3];
        long[] x = new long[2 * r + 3];
        long[] y = new long[2 * r + 3];

        Arrays.fill(f, 1);
        Arrays.fill(x, 1);
        x[0] = 0;

        int max = r, sum = r;
        int next = r;
        while (sum < p) {
            f[++max] = p/(next) - p/(next+1);
            sum += f[max];
            next--;
        }

        int diff = 0;
        if (sum > p) {
            max--;
            diff = 1;
        }

        while(n-- > 0) {
            for (int i = max, j = 1; i > 0; i--, j++) {
                y[i] = (x[j] * f[j+diff] + y[i+1]) % P;
            }

            long[] z = x;
            x = y;
            y = z;
            y[max+1] = 0;
        }
        return x[1];
    }
}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int n = Integer.parseInt(bufferedReader.readLine().trim());

        int p = Integer.parseInt(bufferedReader.readLine().trim());

        long result = Result.pSequences(n, p);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedReader.close();
        bufferedWriter.close();
    }
}

Problem solution in C++.

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

#define REP(i,n) for(int i=0,_n=(n);i<_n;++i)
#define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i)
#define FORD(i,a,b) for(int i=(a),_b=(b);i>=_b;--i)
#define FOREACH(it,arr) for (__typeof((arr).begin()) it=(arr).begin(); it!=(arr).end(); it++)

const int mod  = 1000000007;
const int maxn = 100000;

struct tdata { int from, to, value; };

vector <tdata> v;

int num[maxn] = {0};
int val[maxn] = {0};
int par[maxn] = {0};
int tmp[maxn] = {0};

int main()
{
	int n, p;
	scanf( "%d %d", &n, &p );

	int from, to = 0, value;
	while ( ++to <= p ) {
		value = p / to;
		from  = to;
		to    = p / value;
		v.push_back((tdata){from,to,value});
	}
	
	
	int m = v.size();

	FOR(i,1,m) num[i] = v[i-1].to - v[i-1].from + 1;
	FOR(i,1,m) val[i] = 1;
	
	while ( --n ) {
		memset(par,0,sizeof(par));
		FOR(i,1,m) par[i] = ((long long)num[i] * val[i]) % mod;
		FOR(i,1,m) par[i] = (par[i-1] + par[i]) % mod;
		FOR(i,1,m) tmp[i] = par[m-i+1];
		memcpy(val,tmp,sizeof(val));
	}
	
	int ans = 0;
	FOR(i,1,m) ans = (ans + (long long)val[i] * num[i]) % mod;

	printf( "%dn", ans );

	return 0;
}

Problem solution in C.

#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MOD 1000000007

char* readline();

/*
 * Complete the pSequences function below.
 */
int pSequences(int n, long p) {
    int sqrt = 1;
    while(sqrt*sqrt <= p){
        sqrt++;
    }
    sqrt--;
    long interlen[2*sqrt];
    for(int i = 0; i < sqrt; i++){
        interlen[i] = 1;
        interlen[i + sqrt] = p/(sqrt - i) - p/(sqrt - i + 1);
    }
    interlen[sqrt] = p/sqrt - sqrt;

    long currnum[2*sqrt];
    for(int i = 0; i < 2*sqrt; i++){
        currnum[i] = 0;
    }
    currnum[0] = 1;

    for(int i = 0; i < n + 1; i++){
        long total = 0;
        long nextnum[2*sqrt];
        for(int j = 2*sqrt - 1; j >= 0; j--){
            total = (total + currnum[2*sqrt - j - 1])%MOD;
            nextnum[j] = total;
        }
        for(int j = 0; j < 2*sqrt; j++){
            currnum[j] = (nextnum[j]*interlen[j])%MOD;
        }
    }
    return currnum[0];
}

int main()
{
    FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");

    char* n_endptr;
    char* n_str = readline();
    int n = strtol(n_str, &n_endptr, 10);

    if (n_endptr == n_str || *n_endptr != '') { exit(EXIT_FAILURE); }

    char* p_endptr;
    char* p_str = readline();
    int p = strtol(p_str, &p_endptr, 10);

    if (p_endptr == p_str || *p_endptr != '') { exit(EXIT_FAILURE); }

    int result = pSequences(n, p);

    fprintf(fptr, "%dn", result);

    fclose(fptr);

    return 0;
}

char* readline() {
    size_t alloc_length = 1024;
    size_t data_length = 0;
    char* data = malloc(alloc_length);

    while (true) {
        char* cursor = data + data_length;
        char* line = fgets(cursor, alloc_length - data_length, stdin);

        if (!line) { break; }

        data_length += strlen(cursor);

        if (data_length < alloc_length - 1 || data[data_length - 1] == 'n') { break; }

        size_t new_length = alloc_length << 1;
        data = realloc(data, new_length);

        if (!data) { break; }

        alloc_length = new_length;
    }

    if (data[data_length - 1] == 'n') {
        data[data_length - 1] = '';
    }
    if(data[data_length - 1] != ''){
        data_length++;
        data = realloc(data, data_length);
        data[data_length - 1] = '';
    }

    data = realloc(data, data_length);

    return data;
}