CareerCup

I didn't see a solution in this direction.

Python:

def getDigit (index):
  digits = 0
  min = None
  max = -1
  while (True):
    digits += 1
    min = max + 1
    max = int ('9' * digits)
    size = (max - min + 1) * digits
    if (size > index):
      break
    index -= size
  number = min + (index / digits)
  digit = index % digits
  return int (str(number)[digit])

Unit tested every index from 0 to 38890. aka numbers 0 to 9999 and it seems to be good.

the digits sequence is like 10,90*2,900*3,9000*4...
so it can be done iteratively

private int digitAtIndex(int index){
		
		if( index < 10 ){
			return index;
		}
		
		index -= 10;

		int seqValue = 10;			
		int multiplier = 10;
		
		while( true ) {
			
			int tempValue = seqValue;
			int tempMultiplier = multiplier;			
			int digit = -1;
			
			while( tempMultiplier > 0 && index >= 0 ){
			
				digit = tempValue / tempMultiplier;
				
				tempValue = tempValue % tempMultiplier;
				tempMultiplier = tempMultiplier / 10;
				
				--index;
			}

			if( index < 0 ){
				return digit;
			}					
			
			++seqValue;	
			
			if( seqValue / multiplier > 9 ){
				multiplier *= 10;
			}
		}
	}

My Algo Goes here.

1> float value= Index / 20;
2> if(index=="Even") {
if(value.decimals() is between 0.00 to 0.49)
{
cout<<"Value is "<<floor(value)
} else {
cout<<"Value is ""<<Celing(value);
}
}
3> if(index=="odd")
if(value.decimals() is between 0.00 to 0.49)
{
int least_index=index%20;
// Use following mapping
if (least_index==1)
cout<<"Value is 0"<<endl;
if (least_index==3)
cout<<"Value is 1"<<endl;
if (least_index==5)
cout<<"Value is 2"<<endl;
if (least_index==7)
cout<<"Value is 3"<<endl;
if (least_index==9)
cout<<"Value is 4"<<endl;
} else {
if(value.decimals() is between 0.50 to 0.99)
{
int least_index=index%20;
// Use following mapping
if (least_index==1)
cout<<"Value is 5"<<endl;
if (least_index==3)
cout<<"Value is 6"<<endl;
if (least_index==5)
cout<<"Value is 7"<<endl;
if (least_index==7)
cout<<"Value is 8"<<endl;
if (least_index==9)
cout<<"Value is 9"<<endl;
}
}

JAVA code. I have not gone through all the above replies. Sorry, if a similar code is already posted.


public static void main(String[] args) {
long n = Long.parseLong(args[0]);
double num = 0;
double pos = 1;

while(pos<n){
num++;
pos = pos + (Math.floor(Math.log10(num))+1);
}

long y = (long)((pos-n)+1);
// System.out.println(""+(long)num+", "+y);

long num_long = (long)num;
String num_str = Long.toString(num_long);

long digit = (num_long%((long)(Math.pow(10,y))))/(((long)Math.pow(10,y-1)));
System.out.println(""+digit);
}

We can think in this way:
0-9 only digits means 10 single digits
10-99 90 double digits

So if i need to find out digit at 19 position then,
19 - (10 * single digits) + 1
left part is 10
divide 10/2 note: divide by 2 because no of digits is 2
add 9(biggest number in single digit) + 5 = 14
result will be 4.

int TellNumInSeq(int index) {
    index = index - 1;
    if (index <= 0)
        return -1;
    //Special Case
    if (index <= 10)
        return index;
    if ((index % 2) == 0)
        return ((index - 10) / 2) % 10;
    return ((index / 20) % 10) + 1;
}

If you are interested in only the digit from the sequence then we can use pointer arithmetic on the string.

int getDigit(char* string, int position)
{
       int digit = -1;

       if ( NULL != string && position >= 0 ) 
       {
             char *ch = string + position;
             if ( '0' <= *ch && *ch <= '9')
                    digit = (int) *ch - '0';
       }
       return digit;
}

This works for all two digit number sequences, but things start falling apart after that. Specifically, all tests pass until index 191, but not beyond.

Does anyone have suggestions?

public class IndexOnInfiiniteNumber {

	public static void main(String args[]) {
		int idx = 1000;
		 System.out.println("Answer must be: " + verifier(idx));
		 System.out.println("Actual Answer is: " + calcNumberAtIndex(idx));
	}

	public static char verifier(int idx) {
		String str = "";
		int count = 0;
		if (idx < 0) {
			throw new RuntimeException("Can not be a negative number");
		}
		while (str.length() <= idx) {
			str += count++;
		}
		for (int i = 0; i < str.length(); i++) {
			System.out.println(i + "->" + str.charAt(i));
		}
		return str.charAt(idx);
	}

	public static long calcNumberAtIndex(long idx) {
		if (idx < 0) {
			throw new RuntimeException("Index can not be negative");
		}
		if (idx < 10) {
			return idx;
		}
		long distanceFrom10 = (idx - 10) / 2;
		long number = 10 + distanceFrom10;
		System.out.println("Number at index calc as: " + number);
		long numDigits = howManyDigits(number);
		long factor = (long) Math.pow(10, numDigits - 1);
		if (idx % 2 == 0) {
			return number / factor;
		} else {
			return number - ((number / factor) * factor);
		}
	}

	public static long howManyDigits(long number) {
		long numDigits = 1;
		if (number < 0) {
			number = number * -1;
		}
		while (number >= 10) {
			number = number / 10;
			numDigits++;
		}
		return numDigits;
	}
}

This is giving the correct answer but is worst time possible

int TellSeq(int index) {
    int i = 0, j = 0, k = 0;
    for (; i < 10; i++) {
        cout << "\n" << (i + 1) << " " << i;
        if (i+1 == index)
            return i;
    }
    index--;
    for (i = 10; i <= 65532; i++) {
        if (i % 2 == 0) {
            cout << "\n" << (i + 1) << " " << (j++) % 10 << " ";
            if (i + 1 == index)
                return j % 10;
            if (j % 10 == 0)
                k++;
        } else {
            cout << "\n" << (i + 1) << " " << (k) % 10 << " ";
            if (i + 1 == index)
                return k % 10;
        }
    }
}

public static int each(int length){
if(length < 0) return 0;
if(length == 0) return 1;
else return 9*((int) Math.pow(10, length-1))*length;
}

public static String getNumber(int index){
if(index < 0) return null;
int length = 0;
while (true){
int temp = index -each(length);
if(temp >= 0){
index=temp;
length++;
}
else {
if(length == 0) return Integer.toString(index);
else {
int number =(index/length)+(int)Math.pow(10, length-1);
int pos = index%length;
String svalue = Integer.toString(number);
String value =svalue.substring(pos, pos+1);
return value;
}
}
}
}

int getDigit(int index)
{
      int i=1, base=0;
     
      while(1) {
           if(index - (9*exp(10,i-1)) * (i)) < 0)
                  break;
           index -= (9*exp(10, i-1) * i);
           base += 9*exp(10,i-1);
           i++
     }
     
     int val = base + index / i;
     if(index % i == 0)
             return val % 10;
     else
             return ((val+1) / (10 * (i - index % i))) % 10;
}

How about this?

public class CountTest {
    StringBuffer sb = new StringBuffer();

    public String generateSequence() {
        for (int i = 0; i < 1000; i++) {
            sb.append(i);
        }
        System.out.println(sb.toString());
        return sb.toString();
    }

    char getDigitAt(String seq, int index) {
        char[] chars = seq.toCharArray();
        return chars[index];
    }

    public static void main(String[] args) {
        CountTest test = new CountTest();
        String seq = test.generateSequence();
        System.out.println(test.getDigitAt(seq,5));//5
        System.out.println(test.getDigitAt(seq,13));//1
        System.out.println(test.getDigitAt(seq,19));//4
        System.out.println(test.getDigitAt(seq,100));//5
        System.out.println(test.getDigitAt(seq,30));//2
        System.out.println(test.getDigitAt(seq,31));//0
        System.out.println(test.getDigitAt(seq,1000));//3
    }
}

public static int getKthDigit(int k)
    {
        boolean possible = k > 9;
        int i = 0;
        while (possible)
        {
            if (k > ((i + 1) * 9 * (Math.pow(10, i))))
            {
                k = k - ((i + 1) * 9 * (Double.valueOf(Math.pow(10, i)).intValue()));
                i++;
            }
            else
            {
                possible = false;
            }
        }
        int left = k % (i + 1);
        k = k / (i + 1);
        for ( int j = 0 ; j < i ; j++)
        {
            k = k + (9 * (Double.valueOf(Math.pow(10, j)).intValue()));
        }
        if (left == 0) {
            return k % 10;
        }
        k++;
        return Integer.valueOf(String.valueOf(String.valueOf(k).charAt(left - 1)));
    }

Tricky but works for sure.

public class StringBuilderExample {
    StringBuilder sb = new StringBuilder();

    StringBuilderExample() {
        for (int i = 0; i<1000; i++) {
            sb.append(i);
        }
        System.out.println("sb = " + sb);
    }
    
    public int getByIndex(int index) {
        System.out.println("-- digit at " + index + " = " + sb.charAt(index));
        
        if (index == 0) return '0';
        int nd = 1, pre_nd = 0;
        int i = 0;
        while (index > nd) {
            pre_nd = nd;
            nd += 9 * Math.pow(10, i) * (++i);
        }

        int r = (index +1 - pre_nd) % i;
        int number = (int)Math.pow(10, i-1) -1 + (index+1 - pre_nd) / i;
        
        if (r == 0) return number%10; 
        else return (++number / (int) Math.pow(10, i-r)) % 10; 
    }
    
    public static void main(String[] args) {
        StringBuilderExample s =new StringBuilderExample();
        System.out.println("digit at 19 = " + s.getByIndex(19));
        System.out.println("digit at 100 = " + s.getByIndex(100));
        System.out.println("digit at 30 = " + s.getByIndex(30));
        System.out.println("digit at 1000 = " + s.getByIndex(1000));
        System.out.println("digit at 31 = " + s.getByIndex(31));
        System.out.println("digit at 1215 = " + s.getByIndex(1215));
    }

What about this ?

#include<stdio.h>
int base [1000];

int turnBase()
{
    for(int i = 0; i<1000 ; i++)
    {
            if(base[i]==-1)
            {
               return i-1;
            }
    }
    return 1000;
}

void checker()//
{
     for(int i = 0 ; i< turnBase()+1 ;i++)
     {
          if(10==base[i])
          {   
              base[i] = 0;
              if(base[i+1] != -1)
                base[i+1]=base[i+1]+1;
              else
                 base[i+1]=1;
          }                          
     }
 }

int getNumber(int value)
{
    int j=0;
    for(int i = 0 ; i<1000 ; i++)
         base[i]= -1;
   do{                                
         base[0] = base[0]+1;
         if(base[0]==10)
                 checker();
         for(int k = turnBase() ; k>=0; k--)
         {
                 if(j==value)
                 {
                             return base[k];
                 }else
                 {        
                      j++;
                 }
         }                              
   }while(true);
}

main()
{
      getNumber(19);
      return 0;
}

int GetDigit(int index){
	if(index < 10){
		return index;
	}
	int base = 10, i = 90, j = 2;
	while(index >= base + i * j){
		base += i * j;
		i *= 10;
		j++;
	}
	int num = base + (index - base) / j;
	int numi = (index - base) % j;
	for(int k = j - 1; k > numi; k--){
		num /= 10;
	}
	return num % 10;
}

I found this one a little tricky. Took me a bit of experimentation to work out the transition between the number of digits.

There may be more efficient patterns, but this worked for me.


As others have mentioned, the basic pattern is:

10 x single digits (or 9 plus a 0 if it helps you)
90 x double digits
900 x triple digits
and so on.

Another way of thinking about that is
1 + 9 x 10**0 + 9 x 10**1 + 9 x 10**2 ... + 9 x 10**n

So to work out how many digits are in the number you're grabbing the index of:

you have n+1 digits where n is the power you're applying to 10 i.e.(9 x 10**n)

so applying that to our index,
index =
0-9 - 1 digit (10)
10-189 - 2 digits (2x90 + 10)
190 - 2890 - 3 digits (3x900 + 2x90 + 10)

Now to work out specifically which number we're dealing with, we take the index plus the count of numbers that have come in each band before, then divide by the number of digits

For example, let us say we want the number at index 203

we had 10 matches up to 10, 100 matches up to 190 so we add 110 to 213 then divide by three to get the actual number

323 / 3 = 107
use mod 3 to find out which position in the number you're returning
107 % 3 = 2

That being the case, we return 7 (index 2 of 107)


Here's the implementation in ruby:

def getIndex(index)
  return index if index < 10

  digit_count = 1
  decimal_unit = 1
  index_comparison = 1
  difference = 0

  while index > ( index_comparison + decimal_unit * digit_count * 9 )
    index_comparison += decimal_unit * digit_count * 9
    difference += 10 ** digit_count
    decimal_unit *= 10
    digit_count += 1
  end

  actual_number = (index + difference) / digit_count
  position = (index + difference) % digit_count

  return actual_number.to_s.slice(position).to_i
end

int calculateIndex(int index)
{
int mult=10;
int num=2;
int offset=0;
int prev=10;

if (index<11) return index-1;

while(1)
{
int base= 9*mult;
int range= base*num + prev;

if(index<range)
{
offset=index-prev;
if(offset%num==0)
{
int indexNumber= mult+(offset/num)-1;
return getlastdigit(indexNumber);
}
else
{
int indexNumber= mult+(offset/num);
int indexposition= num-(offset%num)+1;
return getdigit(indexposition,indexNumber);
}
}
mult=mult*10;
num=num+1;
prev=range;
}

return -1000;

}

int getlastdigit(int x)
{
return x%10;
}

int getdigit(int x, int y)
{
int digit;
int i=1;
while(y!=0)
{
digit=y%10;
y=y/10;
x=x-1;
if(x==0)
return digit;
}
}

/* Given a stream of numbers and index, find the digit at that index 
 * e.g. 01234567891011121314 index = 15, answer is 1 (of 12)
 */

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<math.h>

/* Function to find number of digits */
int findNoOfDigits(int* index)
{
    int no_of_digits = 1;
    if(*index <= 10)
    {
        return no_of_digits;
    }
    int num = 90;
    int temp = *index - 10;
    *index = temp;
    while(temp > 0)
    {
        no_of_digits++;
        temp -= (num * no_of_digits);
        if(temp < 0)
        {
            break;
        }
        *index = temp;
        num *= 10;
    }
    return no_of_digits;
}

/* Function to find value at some position */
int position(int index)
{
    int no_of_digits = findNoOfDigits(&index);
    printf("%d %d\n", no_of_digits, index);
    
    if(no_of_digits == 1)
    {
        return index - 1;
    }
    else
    {
        int temp = no_of_digits - 1;
        int num  = pow(10, temp);
        int rem = index % no_of_digits;
        int quotient = index / no_of_digits;
        num += quotient;
        if(rem == 0)
        {
               return (num % 10);
        }
        else
        {
               int digit;
               int count = no_of_digits + 1 - rem;
               while(count > 0)
               {
                   count--;
                   digit = num % 10;
                   num = num / 10;
               }
               return digit;
        }
    }
}

/* Main driver function */
int main(void)
{
    int index;
    scanf("%d", &index);
    printf("\n");
    printf("%d",position(index));
    getch();
    return 0;
    
}

p = position
v = value

formula: v = p/2 + 5

example:
p = 30
v = 30/2 + 5 = 15 + 5 = 20

if v returns an int, take leftmost digit of v, so answer is 2.

if v returns a float, take rightmost digit of int(v). Example:

p = 31
v = 31/2 + 5 = 15.5 + 5 = 20.5

right(int(v)) = right(int(20.5)) = right(20) = 0

Here is the pseudo code implemented:
Should be understandable.

int getDigit (int index) {

    digitsCount = 0;
    digitOnes = 0;
    min = 0;
    max = -1;
    while (True) {
        digitsCount += 1;
        digitOnes = (10*digitOnes) + 1;
        min = max + 1;
        max = 9 * digitOnes;

        size = (max - min + 1) * digitsCount;
        if (size > index)
            break;

        index = index - size;
    }

    number = min + (index / digits);
    digitPositionFromLeft = index % digits;

    digitPositionFromRight = (digits - digitPositionFromLeft);
    number = ( number / pow(10, digitPositionFromRight) );
    return (number%10);
}

(pseudo-code only )
Say, the index value (started from 0) corresponds to (is one bit of) the original number Num.
We try to get the number of digits (n) for Num.

pair<int, int> GetBits (int index) {
  int digits = 0;
  int sum_of_digits = 0;
  int pre_sum_of_digits;
  while (sum_of_digits < index - 1) {
  // we use index - 1 is because the array starts from 0.
    ++digits;
    pre_sum_of_digits = sum_of_digits;
    sum_of_digits += (pow(10, digits) - pow(10, digits - 1)) * digits;
  }
  return pair<int, int>(digits - 1, pre_sum_of_digits +1); // we add the index 0
}

Then for the total number of digits until Num, we have the following equation:

total_digits = pre_sum_of_digits + (Num - 10^(digits - 1) + 1) * digits

And what we need is:

index <= total_digits

we can solve the above equation to get Num.

int GetNum (int index, int digits, int pre_sum_of_digits) {
  int Num = ceil((double)(index - pre_sum_of_digits) / digits) + pow(10, (digits - 1)) - 1;
  return Num;
}

Then, we need to refine and get the specific digital value we want.
we first convert Num to a string and select the right one we want.

Solution in C++:

#include<iostream>
#include<cmath>

using namespace std;

int getDigit(int p)
{
  int n = 1, c = -1;
  while(true)
  {
    for (int i = (n==1?0:pow(10, n-1)); i < pow(10,n); ++i)
    {
      c += n;
      if (c >= p)
      {
        int loop = c-p+1, digit;
        while (loop-- > 0)
        {
          digit = i % 10;
          i = i / 10;
        }
        return digit;
      }
    }
    ++n;
  }
}

int main(int argc, char* argv[])
{
  cout << "index = 100, result = " << getDigit(100) << endl;
  cout << "index = 30, result = " << getDigit(30) << endl;
  cout << "index = 31, result = " << getDigit(31) << endl;
  cout << "index = 1000, result = " << getDigit(1000) << endl;
}

#include <iostream>

using namespace std;

int getdigit(int n)
{
    int weight[]={10, 180, 2700, 36000, 450000, 5400000};
    int add[]={1, 10, 100, 1000, 10000, 10000, 100000};

    if(n<=10) return n-1;
    int i=0;
    while(n/weight[i]>=1)
    {
         n-=weight[i];
      i++;

    }
    int len=i+1;
    cout<<"len: "<<len<<endl;
    int d[len];
    for(int j=0; j<len; j++)
    {
     cout<<"n:  "<<n<<endl;
    d[j]=n/(len*add[i-j]);
    if(j==0)  d[j]++;
     n=n%(len*add[i-j]);
    }
    return d[n];

}
int main()
{
    cout <<getdigit(1000) << endl;
    return 0;
}

/*i m showing just for index 100 this way u can do same for any index/*
#include<iostream>
#include<sstream>
#include<string>

using namespace std;

int main(){

string s;
cin>> s;
cout << s[100] << endl;
return 0;
}

create buckets. Like the first million entries in one file. the next million entries in 2nd file etc. Now if the serch index is 100,000 then you know it is in first file. Read the file till you get the 100,000th item and return the value.