CODEWITHSUNDEEP
algorithmdynamic-programming
NIRBHAY KUMAR PANDEY
NIRBHAY KUMAR PANDEY

Reputation: 33

dynamic programming, nth string

How to solve the problem https://www.hackerearth.com/problem/algorithm/special-numbers-39d71325/.

The first number in a sequence of numbers is 1. Every subsequent ith number of the sequence is constructed by applying the following operations on the (i-1)th number:

Therefore, the sequence will be as follows:

1, 114, 1141141, 11411411141141114 , ...

Write a program to find a digit which is the jth digit of the ith number in this sequence. If the ith number has less than j digits, print -1.

Input format

Output format

For each test case, print a digit which is the jth digit of the ith number in this sequence. If the ith number has less than j digits, print -1.

Constraints

1<=T<=10000(10 to the power 4)

1<=i<=1000000(10 to the power 6)

1<=j<=1000000000000(10 to the power 12)

Sample input                            Sample output
4
2 2                                               1
2 3                                               4
3 6                                               4
3 7                                               1

Explanation

1st test case: 2nd number in the sequence is 114, 2nd digit is 1.

2nd test case: 2nd number in the sequence is 114, 3rd digit is 4.

3rd test case: 3rd number in the sequence is 1141141, 6th digit is 4.

4th test case: 3rd number in the sequence is 1141141, 7th(last) digit is 1.

Storing all the strings (upto ith string) in vector will take enormous amount of time. The tag of the problem is memoization(dynamic programming). I want code/strategy using memoization(dynamic programming).

I don't think the following approach of mine is even closer to what the actual/correct solution will be.

See the comment after the line vector<string> v(15);

If this is wrong platform to ask such questions, tell me where to ask such questions.

#include<iostream>
#include<string>
#include<vector>
#include<cstring>
#include<climits>
//#define tr(v,it) for(typeof(v.begin()) it=v.begin();it!=v.end();it++)
using namespace std;

int main() {
    vector<string> v(15);//v(14) runs under 1 sec even v(15) gives tle. So think how much time v(1000000) will take.
    v[0]="1";
    vector<string>::iterator it;
    int n,h,i,j,tc;
    string s,s1;


    char ch='a';
    for(it=v.begin()+1;it!=v.end();it++) {//set value
         s=*(it-1); s1="";
         for(unsigned int i=0;i<s.length();i++) {
             char ch=s[i];
             if(ch=='1') {
                 s1=s1+"114";
             }
             else {
                 s1=s1+'1';
             }
         }
         *it=s1;
    }
    /*for(it=v.begin();it!=v.end();it++) {//print value
        cout<<*it<<endl;
    }
    cin>>tc;
    while(tc--) {
        cin>>i>>j;
        cout<<v[i-1][j-1];

    }*/
    return 0;
}

//Thanks and regards

Upvotes: 1

Views: 335

Answers (2)

SomeDude
SomeDude

Reputation: 14228

Based on answer by גלעד ברקן, here is the Java code :

private static void getDigit( int n, long k ) {
    long[] L = new long[n+1];
    L[1] = 1;
    L[2] = 3;
    long MAX = Long.parseUnsignedLong("1000000000000");
    for ( int i = 3; i <= n; i++ ) {
      L[i] = 2*L[i-1] + L[i-2];
      if ( L[i] >= MAX ) break;
    }

    Long k1 = Long.valueOf(k);
    String s = "114";
    while ( n > 2 ) {
      if ( k1 <= L[n-1] ) {
          n--;
      } else if ( k1 > L[n-1] && k1 <= 2*L[n-1] ) {
        k1 = k1 - L[n-1];
        n--;
      } else {
        k1 = k1 - 2*L[n-1];
        n = n - 2;
      }
    }
    System.out.println( String.valueOf( s.charAt(k1.intValue()-1)));
}

You can test it here by passing different n, k values.

Upvotes: 0

גלעד ברקן
גלעד ברקן

Reputation: 23955

Let's look at the sequence and its length;

114
3
114 114 1
7
114 114 1 114 114 1 114
    7         7      3
   773       773     7
773 773 7 773 773 7 773
...

Each length is a doubling of the previous sequence concatenated with the sequence before that, AKA:

length(i) =
  2 * length(i - 1) + length(i - 2)

Given a position in the final string, since we know the previous sequence lengths, we can determine of it's in (1) the first of the doubled previous, (2) the second of the doubled previous, or (3) the appended, second to last sequence.

By tracking it's location, we keep transforming its position to one that's in one of the previous sequences, until we get to the very first.

For example:

    7         7      3
114 114 1 114 114 1 114
                  ^

We know the previous two sequences were of length 7 and 3, so we can determine that we are on the 7th index of the second 7-length sequence. Now we continue:

114 114 1
        ^

The previous two sequence lengths were 3 and 1 so we are on the 1st index of the second to last sequence (the one with length 1).

Result: 1

Upvotes: 1

Related Questions