Minimum length

3.6

8 votes
String, Brute Force, Algorithms, String Searching, Binary Search, String Algorithms
Problem

You are given an integer N. We call a string S good if it satisfies the following conditions:

  1. S[i]=a or S[i]=b  1ilen(S)
  2. S[i]S[i+1]  1ilen(S)1Recall that a<b according to the numbering of ASCII table.

Here len(S) denotes the length of string S. For example, the strings "aabb", "abb", "aaa", "bbb", "a" are good but strings "aba", "bab", "bba" are not.

Your task is to find the minimum length of a good string which has atleast N distinct substrings.

Notes

  • A substring of a string is a contiguous subsequence of that string. For example, "hacker" is subtring of "hackerearth", but "hackr" is not.
  • Two substrings X and Y are different if:
    • They are of different length.
    • If they are of the same length, then there is an index i such that X[i]Y[i].

Input 

  • The first line contains a single integer T denoting the number of test cases.
  • For each test case, the only line of input contains a single integer N.

Output 

For each test case (in a separate line), output the minimum length of a good string which has at least N distinct substrings.

Constraints

1T50001N109

Sample Input
3
5
8
1000000000
Sample Output
3
4
63244
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

In the first test case, we have N=5, possible good strings are "abb", "aab". For example, distinct substrings of "abb" are "a", "ab", "abb", "b", "bb". It can be proved that no good string of length less than 3 has at least 5 distinct substrings.

In the second test case, we have N=8, possible good string is "aabb". For example, distinct substrings of "aabb" are "a", "aa", "aab", "aabb", "ab", "abb", "b", "bb". It can be proved that no good string of length less than 4 has at least 8 distinct substrings.

Editor Image

?