Table of Contents
P-sequences – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ replace HackerRank Solution
#include<math.h>
#include<algorithm>
#include<cstdlib>
#include<iostream>
#include<stdio.h>
#include<map>
#include<ext/hash_map>
#include<ext/hash_set>
#include<set>
#include<string>
#include<assert.h>
#include<vector>
#include<time.h>
#include<queue>
#include<deque>
#include<sstream>
#include<stack>
#include<sstream>
#define MA(a,b) ((a)>(b)?(a):(b))
#define MI(a,b) ((a)<(b)?(a):(b))
#define AB(a) (-(a)<(a)?(a):-(a))
#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define pob pop_back
#define ep 0.0000000001
#define Pi 3.1415926535897932384626433832795
using namespace std;
using namespace __gnu_cxx;
const long long MO=1000000000+7;
int x,y,i,j,k,n,m,mid,l,r;
int a[100000],p,kk;
long long b[2][100000];
int main()
{
cin>>n>>p;
kk=k=int(sqrt(p));
for (i=1;i<=k;i++) a[i]=i;
for (i=kk;i>=1;i--)
{
if (p/i>a[k]) {k++; a[k]=p/i;}
}
for (i=1;i<=k;i++)
b[1][i]=a[i];
b[0][0]=0;
b[1][0]=0;
for (i=2;i<=n;i++)
{
r=k;
for (j=1;j<=k;j++){
while (a[r]*a[j]>p) r--;
b[(i&1)][j]=(b[(!(i&1))][r]*(a[j]-a[j-1])+b[(i&1)][j-1])%MO;
// cout<<b[(i&1)][j]<<" "<<a[j]<<" -- ";
}
// cout<<endl;
}
cout<<b[(n&1)][k]<<endl;
return 0;
}
Java rep HackerRank Solution
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
public class Solution {
static InputStream is;
static PrintWriter out;
static String INPUT = "";
static void solve()
{
int n = ni(), P = ni();
int s = (int)Math.sqrt(P);
int[][] vals = new int[80000][];
int p = 0;
for(int i = 1;i <= P/s;i++){
if(i == 1 || P/i != P/(i-1)){
vals[p++] = new int[]{P/i, 1};
}else{
vals[p-1][1]++;
}
}
for(int i = s-1;i >= 1;i--){
vals[p++] = new int[]{i, P/i-P/(i+1)};
}
int[] cum = new int[p+1];
for(int i = 0;i < p;i++){
cum[i+1] = cum[i] + vals[i][1];
}
long[] pre = new long[p];
long[] cur = new long[p];
for(int i = 0;i < p;i++){
pre[i] = 1;
}
int mod = 1000000007;
for(int i = 0;i < n-1;i++){
int q = 0;
long lcum = 0;
for(int j = p-1;j >= 0;j--){
while(q < p && cum[q+1] < vals[j][0]){
lcum += pre[q] * vals[q][1];
q++;
}
cur[j] = (lcum + (vals[j][0] - cum[q]) * pre[q]) % mod;
}
long[] dum = pre; pre = cur; cur = dum;
}
long ret = 0;
for(int i = 0;i < p;i++){
ret += pre[i] * vals[i][1];
}
out.println(ret%mod);
}
public static void main(String[] args) throws Exception
{
long S = System.currentTimeMillis();
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
solve();
out.flush();
long G = System.currentTimeMillis();
tr(G-S+"ms");
}
private static boolean eof()
{
if(lenbuf == -1)return true;
int lptr = ptrbuf;
while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false;
try {
is.mark(1000);
while(true){
int b = is.read();
if(b == -1){
is.reset();
return true;
}else if(!isSpaceChar(b)){
is.reset();
return false;
}
}
} catch (IOException e) {
return true;
}
}
private static byte[] inbuf = new byte[1024];
static int lenbuf = 0, ptrbuf = 0;
private static int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private static double nd() { return Double.parseDouble(ns()); }
private static char nc() { return (char)skip(); }
private static String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private static char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private static char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private static int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private static int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}
Python 3 rep HackerRank Solution
Python 2 rep HackerRank Solution
# Enter your code here. Read input from STDIN. Print output to STDOUT
def get_num_final(N,P):
ls = int(P**0.5) + 1
cn = [i for i in range(ls)]
ca = [P/i for i in range(1,ls)]
ca.insert(0,0)
gs = [(P/(i-1) - P/i) for i in range(2,ls)]
gs.insert(0,0)
gs.append(ca[-1] - cn[-1])
pn =list(cn)
pa =list(ca)
for n in range(N - 1):
for i in range(1,ls):
cn[i] = (pa[i] + cn[i - 1]) % (10**9+7)
ca[-1] = (cn[-1] + (pn[-1])*(gs[-1]) )% (10**9+7)
for i in xrange(ls - 2,0,-1):
ca[i] = ((pn[i])*(gs[i]) + ca[i + 1]) % (10**9+7)
pn = list(cn)
pa = list(ca)
print ca[1]% (10**9+7)
N = int(raw_input())
P = int(raw_input())
get_num_final(N,P)
C rep HackerRank Solution
#include <stdio.h>
#define P 1000000007LL
long long b[100000][3],i,j,k,l,m,n,t;
long long a[1010][65000];
int main()
{
scanf("%lld %lld",&n,&t);
k = 1;
l = 0;
while(k<=t)
{
b[l][0] = k;
b[l][1] = t/(t/k);
b[l][2] = b[l][1] - b[l][0] + 1;
k = b[l][1] + 1;
l++;
}
for(i=0;i<l;i++) a[0][i] = 0;
a[0][0] = 1;
for(i=1;i<=n;i++)
{
k = 0;
for(j=0;j<l;j++)
{
k = (k+a[i-1][j]*b[j][2])%P;
a[i][l-1-j] = k;
}
}
k = 0;
for(i=0;i<l;i++) k = (k+a[n][i]*b[i][2])%P;
printf("%lld\n",k);
//for(i=0;i<l;i++) printf("%lld: %lld-%lld -> %lld\n",i,b[i][0],b[i][1],t/b[i][0]);
return 0;
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
