fork(1) download 
  1. /***********************************************************************
  2. Problem: Numbers are serialized increasingly into a sequence in the format 
  3. of 0123456789101112131415..., which each digit occupies a position in the 
  4. sequence. For instance, the digit in the position 5 is 5, in the position 
  5. 13 is 1, in the position 19 is 4, and so on.
  6.  
  7. Please write a function/method to get the digit on any given position.
  8. ***********************************************************************/
  9.  
  10. #include <iostream>
  11.  
  12. using namespace std;
  13.  
  14. int countOfIntegers(int digits);
  15. int digitAtIndex(int index, int digits);
  16. int beginNumber(int digits);
  17.  
  18.  
  19. int digitAtIndex(int index)
  20. {
  21.     if(index < 0)
  22.         return -1;
  23.  
  24.  
  25.     int digits = 1;
  26.     while(true)
  27.     {
  28.         int numbers = countOfIntegers(digits);
  29.         if(index < numbers * digits)
  30.             return digitAtIndex(index, digits);
  31.  
  32.  
  33.         index -= digits * numbers;
  34.         digits++;
  35.     }
  36.     return -1;
  37. }
  38.  
  39. int countOfIntegers(int digits)
  40. {
  41.     if(digits == 1)
  42.         return 10;
  43.  
  44.  
  45.     int count = 1;
  46.     for(int i = 1; i < digits; ++i)
  47.         count *= 10;
  48.     return 9 * count;
  49. }
  50.  
  51. int digitAtIndex(int index, int digits)
  52. {
  53.     int number = beginNumber(digits) + index / digits;
  54.     int indexFromRight = digits - index % digits;
  55.     for(int i = 1; i < indexFromRight; ++i)
  56.         number /= 10;
  57.     return number % 10;
  58. }
  59.  
  60. int beginNumber(int digits)
  61. {
  62.     if(digits == 1)
  63.         return 0;
  64.  
  65.  
  66.     int begin = 1;
  67.     for(int i = 1; i < digits; ++i)
  68.         begin *= 10;
  69.     return begin;
  70. }
  71.  
  72. //================================= Test Code =================================
  73. void test( char* testName, int inputIndex, int expectedOutput)
  74. {
  75.     if(digitAtIndex(inputIndex) == expectedOutput)
  76.         cout << testName << " passed." << endl;
  77.     else
  78.         cout << testName << " FAILED." << endl;
  79. }
  80.  
  81.  
  82. int main()
  83. {
  84.     test("Test1", 0, 0);
  85.     test("Test2", 1, 1);
  86.     test("Test3", 9, 9);
  87.     test("Test4", 10, 1);
  88.     test("Test5", 189, 9); // last digit of 99
  89.     test("Test6", 190, 1); // first digit of 100
  90.     test("Test7", 1000, 3); // first digit of 370
  91.     test("Test8", 1001, 7); // middle digit of 370
  92.     test("Test9", 1002, 0); // last digit of 370
  93.     return 0;
  94. }
Success #stdin #stdout 0s 3468KB
comments (?)
stdin 
Standard input is empty
stdout 
Test1 passed.
Test2 passed.
Test3 passed.
Test4 passed.
Test5 passed.
Test6 passed.
Test7 passed.
Test8 passed.
Test9 passed.
https://ideone.com/yogYbu
Digits in a Sequence
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!