In this post, we will solve HackerRank Favorite sequence Problem Solution.
Johnny, like every mathematician, has his favorite sequence of distinct natural numbers. Let’s call this sequence M. Johnny was very bored, so he wrote down N copies of the sequence M in his big notebook. One day, when Johnny was out, his little sister Mary erased some numbers(possibly zero) from every copy of M and then threw the notebook out onto the street. You just found it. Can you reconstruct the sequence?
In the input there are N sequences of natural numbers representing the N copies of the sequence M after Mary’s prank. In each of them all numbers are distinct. Your task is to construct the shortest sequence $ that might have been the original M. If there are many such sequences, return the lexicographically smallest one. It is guaranteed that such a sequence exists.
Note
Sequence A[1…n] is lexicographically less than sequence B[1…n] if and only if there exists 1 <i<n such that for all 1 <j<i, A[j] = B[j] and A[i] < B[i].
Input Format
In the first line, there is one number N denoting the number of copies of M.
This is followed by K
and in next line a sequence of length K representing one of sequences after Mary’s prank. All numbers are separated by a single space.
Output Format
In one line, write the space-separated sequence S-the shortest sequence that might have been the original M. If there are many such sequences, return the lexicographically smallest one.
Sample Input
2
2
1 3
3
2 3 4
Sample Output
1 2 3 4Explanation
You have 2 copies of the sequence with some missing numbers: [1, 3] and [2, 3, 4]. There are two candidates for the original sequence M: [1, 2, 3, 4] and [2, 1, 3, 4], where the first one is lexicographically least.
Favorite sequence C Solution
#include <stdio.h>
#include <stdlib.h>
typedef struct{
int u;
int w;
int p;
} node;
void sort_a2(int*a,int*b,int size);
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size, int right_size);
int get_i(int*a,int num,int size);
int med(int*a,int size);
void heap_insert(node *heap,node *elem,int *size,int *heap_list);
void heap_update(node *heap,node *elem,int *heap_list);
void heap_read(node *heap,int *size,int *heap_list,node *ans);
int main(){
int N,i,j,max=0,size=0,tsize=0,heap_size=0,temp=0;
int *K,*e,*p,*pp,*u,*v,*ptr;
node t,*heap;
e=(int*)malloc(1000000*sizeof(int));
p=(int*)malloc(1000000*sizeof(int));
pp=(int*)malloc(1000000*sizeof(int));
for(i=0;i<1000000;i++)
e[i]=p[i]=pp[i]=0;
scanf("%d",&N);
K=(int*)malloc(N*sizeof(int));
int **table=(int**)malloc(N*sizeof(int*));
for(i=0;i<N;i++){
scanf("%d",&K[i]);
size+=K[i]-1;
table[i]=(int*)malloc(K[i]*sizeof(int));
for(j=0;j<K[i];j++){
scanf("%d",&table[i][j]);
e[table[i][j]-1]=1;
if(table[i][j]-1>max)
max=table[i][j]-1;
}
}
u=(int*)malloc(size*sizeof(int));
v=(int*)malloc(size*sizeof(int));
size=0;
for(i=0;i<N;i++)
for(j=1;j<K[i];j++){
u[size]=table[i][j-1]-1;
v[size]=table[i][j]-1;
p[table[i][j]-1]++;
size++;
}
sort_a2(u,v,size);
for(i=0;i<N;i++)
free(table[i]);
free(K);
free(table);
ptr=(int*)malloc(1000000*sizeof(int));
heap=(node*)malloc(1500000*sizeof(node));
for(i=0;i<=max;i++)
if(e[i]){
t.p=p[i];
t.w=(p[i])?2000000+i:i;
t.u=i;
heap_insert(heap,&t,&heap_size,ptr);
}
while(heap_size){
heap_read(heap,&heap_size,ptr,&t);
pp[tsize++]=t.u;
for(i=get_i(u,pp[tsize-1],size);i>=0 && i<size && u[i]==pp[tsize-1];i++){
t=heap[ptr[v[i]]];
t.p--;
if(t.p==0)
t.w-=2000000;
heap_update(heap,&t,ptr);
}
}
for(i=0;i<tsize;i++)
printf("%d ",pp[i]+1);
return 0;
}
void sort_a2(int*a,int*b,int size){
if (size < 2)
return;
int m = (size+1)/2,i;
int*left_a,*left_b,*right_a,*right_b;
left_a=(int*)malloc(m*sizeof(int));
right_a=(int*)malloc((size-m)*sizeof(int));
left_b=(int*)malloc(m*sizeof(int));
right_b=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++){
left_a[i]=a[i];
left_b[i]=b[i];
}
for(i=0;i<size-m;i++){
right_a[i]=a[i+m];
right_b[i]=b[i+m];
}
sort_a2(left_a,left_b,m);
sort_a2(right_a,right_b,size-m);
merge2(a,left_a,right_a,b,left_b,right_b,m,size-m);
free(left_a);
free(right_a);
free(left_b);
free(right_b);
return;
}
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size, int right_size){
int i = 0, j = 0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
j++;
} else if (j == right_size) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
} else if (left_a[i] <= right_a[j]) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
} else {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
j++;
}
}
return;
}
int get_i(int*a,int num,int size){
if(size==0)
return 0;
if(num>med(a,size))
return get_i(&a[(size+1)>>1],num,size>>1)+((size+1)>>1);
else
return get_i(a,num,(size-1)>>1);
}
int med(int*a,int size){
return a[(size-1)>>1];
}
void heap_insert(node *heap,node *elem,int *size,int *heap_list){
(*size)++;
int index=(*size);
while(index>1 && elem->w<heap[index/2].w){
heap[index]=heap[index/2];
heap_list[heap[index].u]=index;
index/=2;
}
heap[index]=(*elem);
heap_list[elem->u]=index;
return;
}
void heap_update(node *heap,node *elem,int *heap_list){
int index=heap_list[elem->u];
while(index>1 && elem->w<heap[index/2].w){
heap[index]=heap[index/2];
heap_list[heap[index].u]=index;
index/=2;
}
heap[index]=(*elem);
heap_list[elem->u]=index;
return;
}
void heap_read(node *heap,int *size,int *heap_list,node *ans){
(*ans)=heap[1];
int index=1;
while(index*2<*size && heap[*size].w>heap[index*2].w || index*2+1<*size && heap[*size].w>heap[index*2+1].w){
index=(heap[index*2].w>heap[index*2+1].w)?index*2+1:index*2;
heap[index/2]=heap[index];
heap_list[heap[index].u]=index/2;
}
heap[index]=heap[*size];
heap_list[heap[index].u]=index;
(*size)--;
return;
}Favorite sequence C++ Solution
#include <algorithm>
#include <cstring>
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
vector<int> gr[1000001];
int indeg[1000001];
priority_queue<int, vector<int>, greater<int>> pq;
int main()
{
int n;
scanf("%d", &n);
int maxval = -1;
for (int i = 0; i < n; i++)
{
int len;
scanf("%d", &len);
int prev;
for (int j = 0; j < len; j++)
{
int tmp;
scanf("%d", &tmp);
if (tmp > maxval)
maxval = tmp;
if (j != 0)
gr[prev].push_back(tmp), indeg[tmp]++;
prev = tmp;
}
}
for (int i = 1; i <= maxval; i++)
{
if (indeg[i] == 0 && !gr[i].empty())
pq.push(i);
}
while (!pq.empty())
{
int next = pq.top();
printf("%d ", next);
pq.pop();
int sz = (int)gr[next].size();
for (int i = 0; i < sz; i++)
{
int node = gr[next][i];
indeg[node]--;
if (indeg[node] == 0)
pq.push(node);
}
}
printf("\n");
return 0;
}Favorite sequence C Sharp Solution
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
class Node
{
public Node(int value)
{
Value = value;
Children = new List<Node>();
ParentsCount = 0;
}
public int Value { get; private set; }
public List<Node> Children { get; private set; }
public int ParentsCount { get; private set; }
public void AddNext(Node n)
{
Children.Add(n);
n.ParentsCount++;
}
public List<Node> DetachChildren()
{
var oldChildren = Children;
foreach (var child in oldChildren)
child.ParentsCount--;
Children = new List<Node>();
return oldChildren;
}
}
class NodeComparer : IComparer<Node>
{
public int Compare(Node x, Node y)
{
return x.Value.CompareTo(y.Value);
}
}
static class Solution
{
static void Main(string[] args)
{
Dictionary<int, Node> nodes = new Dictionary<int, Node>();
int N = int.Parse(Console.ReadLine());
for (int i = 0; i < N; i++)
{
Console.ReadLine(); // skip line with K
var sequence = Console.ReadLine().Split(' ').Select(str => int.Parse(str));
nodes.AddSequence(sequence);
}
var startingNodes = nodes.Values.Where(n => n.ParentsCount == 0);
SortedSet<Node> queue = new SortedSet<Node>(startingNodes, new NodeComparer());
List<int> result = new List<int>();
while (queue.Count > 0)
{
var currentNode = queue.Min;
queue.Remove(currentNode);
result.Add(currentNode.Value);
var children = currentNode.DetachChildren();
foreach (var child in children.Where(c => c.ParentsCount == 0))
queue.Add(child);
}
Console.WriteLine(string.Join(" ", result));
}
static void AddSequence(this Dictionary<int, Node> nodes, IEnumerable<int> sequence)
{
var enumerator = sequence.GetEnumerator();
enumerator.MoveNext();
Node from = nodes.GetOrAdd(enumerator.Current);
while (enumerator.MoveNext())
{
Node to = nodes.GetOrAdd(enumerator.Current);
from.AddNext(to);
from = to;
}
}
static Node GetOrAdd(this Dictionary<int, Node> nodes, int value)
{
if (!nodes.TryGetValue(value, out Node node))
{
node = new Node(value);
nodes[value] = node;
}
return node;
}
}Favorite sequence Java Solution
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Scanner;
import java.util.TreeSet;
public class Solution {
public static final int MAXN = 1000000;
public static void main(String[] args) {
int[] cnt = new int[MAXN+1];
int[] pcnt = new int[MAXN+1];
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
TreeSet<Integer> tree = new TreeSet<Integer>();
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[][] A = new int[N][];
int pnum = 0;
int mp = 0;
for (int i = 0; i < N; ++i) {
int M = sc.nextInt();
int[] AM = new int[M];
A[i] = AM;
pnum = 0;
for (int j = 0; j < M; ++j) {
cnt[pnum] += 1;
pnum = sc.nextInt();
AM[j] = pnum;
pcnt[pnum]++;
if (pnum > mp) {
mp = pnum;
}
}
}
int[][] B = new int[mp + 1][];
B[0] = new int[N];
int[] BP = new int[mp + 1];
for (int i = 0; i <= mp; ++i) {
B[i] = new int[cnt[i]];
}
for (int i = 0; i < N; ++i) {
int M = A[i].length;
int[] AM = A[i];
pnum = 0;
int[] Bpnum = B[pnum];
for (int j = 0; j < M; ++j) {
int AMj = AM[j];
Bpnum[BP[pnum]++] = AMj;
pnum = AMj;
Bpnum = B[pnum];
}
}
for(int i=0;i<B[0].length;++i) {
pcnt[B[0][i]]--;
}
for (int i = 1; i <= mp; ++i) {
if(cnt[i]>0 || pcnt[i]>0) {
tree.add((i - 1) + pcnt[i] * MAXN);
}
}
try {
boolean first = true;
while (true) {
Integer t = tree.pollFirst();
if (t == null) {
break;
}
int tv = t % MAXN + 1;
if(first) {
first = false;
}else {
bw.write(' ');
}
bw.write(Integer.toString(tv));
int[] Btv = B[tv];
for (int i = 0; i < Btv.length; ++i) {
assert(pcnt[Btv[i]]>0);
tree.remove((Btv[i] - 1) + (pcnt[Btv[i]]--) * MAXN);
tree.add((Btv[i] - 1) + (pcnt[Btv[i]]) * MAXN);
}
}
} catch (IOException e) {
}finally {
try {
bw.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
}Favorite sequence JavaScript Solution
let root=undefined
function processData(input) {
//Enter your code here
const inputAr=input.split('\n')
const DAG=[]
const numberOfSeq=inputAr.shift()
for(let i=0;i<numberOfSeq;i++){
const size=inputAr[i*2]
const numbers=inputAr[i*2+1].split(' ')
let parent=undefined
numbers.forEach((number,index)=>{
const node=findOrAddToBST(root,parseInt(number),DAG.length)
addToDag(parent,node,DAG)
parent=node
})
}
topSortDAG(DAG)
}
// const inOrder=(root)=>{
// if(!root){
// return
// }
// inOrder(root.left)
// console.log(root.number)
// inOrder(root.right)
// }
const removeEdgeFromParent=(node,dag,sources)=>{
dag[node.dagKey]=undefined
node.next.forEach(child=>{
// console.log("child",child)
const index=child.parents.findIndex(parent=>parent.number===node.number)
child.parents.splice(index,1)
if(child.parents.length<1){
let i=0
while(i<sources.length &&sources[i].number>child.number){
i++
}
sources.splice(i,0,child)
}
})
}
const findMinSource=(dag)=>{
let min=undefined
dag.filter(node=>node && node.parents.length===0).forEach(node=>{
if(!min){
min=node
}
if(node.number<min.number){
min=node
}
})
return min
}
const getSortedSources=(dag)=>{
const sources=dag.filter(node=>node && node.parents.length===0).sort((a,b)=>b.number-a.number)
// console.log("sources",sources)
return sources
}
const topSortDAG=(dag)=>{
const seq=[]
const sources=getSortedSources(dag)
while (seq.length<dag.length){
const source=sources.pop()
seq.push(source.number)
removeEdgeFromParent(source,dag,sources)
}
console.log(seq.join(' '))
}
const addToDag=(parent,node,DAG)=>{
const dagNode=DAG[node.dagKey]?
DAG[node.dagKey]:{number:node.number,next:[],parents:[],dagKey:node.dagKey}
if(!DAG[node.dagKey]){
DAG.push(dagNode)
}
if(parent){
DAG[parent.dagKey].next.push(dagNode)
DAG[node.dagKey].parents.push(parent)
}
}
const findOrAddToBST=(parent,number,dagKey)=>{
if(!parent){ // happens only for an empty tree
const newNode={number,dagKey,left:undefined,right:undefined}
root=newNode
return newNode
}
if(parent.number===number){
return parent
}
if(parent.number>number){
if(parent.left){
return findOrAddToBST(parent.left,number,dagKey)
}
const newNode={number,dagKey,left:undefined,right:undefined}
parent.left=newNode
return newNode
}
else {
if(parent.right){
return findOrAddToBST(parent.right,number,dagKey)
}
const newNode={number,dagKey,left:undefined,right:undefined}
parent.right=newNode
return newNode
}
}
process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
_input += input;
});
process.stdin.on("end", function () {
processData(_input);
});Favorite sequence Python Solution
from collections import defaultdict
n = int(input())
before_maps = defaultdict(set)
after_maps = defaultdict(set)
for _ in range(n):
k = int(input())
sequence = map(int, input().split())
prev = 0
for num in sequence:
if prev:
before_maps[num].add(prev)
after_maps[prev].add(num)
prev = num
m = []
actives = set(active for active in after_maps[0] if not before_maps[active])
while actives:
next_step = sorted(actives)[0]
actives.remove(next_step)
for step in after_maps[next_step]:
before_maps[step].remove(next_step)
actives.update(active for active in after_maps[next_step] if not before_maps[active])
m.append(next_step)
print(' '.join(map(str, m)))
