# 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) {

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 {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

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

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

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( "%d\n", 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

/*
* 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;
int n = strtol(n_str, &n_endptr, 10);

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

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

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

int result = pSequences(n, p);

fprintf(fptr, "%d\n", result);

fclose(fptr);

return 0;
}

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] = '\0';
}
if(data[data_length - 1] != '\0'){
data_length++;
data = realloc(data, data_length);
data[data_length - 1] = '\0';
}

data = realloc(data, data_length);

return data;
}```