Om alla decimaltal är sammanlänkade i en sträng kommer vi att få en sträng som ser ut som sträng P som visas nedan. Vi måste berätta det N:te tecknet i denna sträng.
P = 12345678910111213141516171819202122232425262728293031….
Exempel:
N = 10 10th character is 1 N = 11 11th character is 0 N = 50 50th character is 3 N = 190 190th character is 1Recommended Practice N:te tecken i sammanfogad decimalsträng Prova det!
Vi kan lösa detta problem genom att bryta strängen på längden. Vi vet att i decimaler är 9 siffror av längden 1 90 siffror har längden 2 900 siffror är av längden 3 och så vidare så vi kan hoppa över dessa siffror enligt det givna N och kan få önskat tecken.
Processing for N = 190 is explained below P[184..195] = 979899100101 First getting length of number at N 190 – 9 = 181 number length is more than 1 181 – 90*2 = 1 number length is more than 2 1 – 900*3 < 0 number length is 3 Now getting actual character at N 1 character after maximum 2 length number(99) is 1 Processing for N = 251 is explained below P[250..255] = 120121 First getting length of number at N 251 - 9 = 242 number length is more than 1 242 – 90*2 = 62 number length is more than 2 62 – 900*3 < 0 number length is 3 Now getting actual character at N 62 characters after maximum 2 length number(99) is Ceil(62/3) = 21 99 + 21 = 120 120 is the number at N now getting actual digit 62%3 = 2 2nd digit of 120 is 2 so our answer will be 2 only.
Genomförande:
C++// C++ program to get Nth character in // concatenated Decimal String #include
// Java program to get Nth character in // concatenated Decimal String class GFG { // Utility method to get dth digit of number N static char getDigit(int N int d) { String str=Integer.toString(N); return str.charAt(d - 1); } // Method to return Nth character in concatenated // decimal string static char getNthChar(int N) { // sum will store character escaped till now int sum = 0 nine = 9; // dist will store numbers escaped till now int dist = 0 len; // loop for number lengths for (len = 1; ; len++) { // nine*len will be incremented characters // and nine will be incremented numbers sum += nine * len; dist += nine; if (sum >= N) { // restore variables to previous correct state sum -= nine * len; dist -= nine; N -= sum; break; } nine *= 10; } // get distance from last one digit // less maximum number int diff = (int)(Math.ceil((double)(N) / (double)(len))); // d will store dth digit of current number int d = N % len; if (d == 0) d = len; // method will return dth numbered digit // of (dist + diff) number return getDigit(dist + diff d); } // Driver code public static void main (String[] args) { int N = 251; System.out.println(getNthChar(N)); } } // This code is contributed by mits
# Python program to get Nth character in # concatenated Decimal String # Method to get dth digit of number N def getDigit(N d): string = str(N) return string[d-1]; # Method to return Nth character in concatenated # decimal string def getNthChar(N): # sum will store character escaped till now sum = 0 nine = 9 # dist will store numbers escaped till now dist = 0 # loop for number lengths for len in range(1N): # nine*len will be incremented characters # and nine will be incremented numbers sum += nine*len dist += nine if (sum >= N): # restore variables to previous correct state sum -= nine*len dist -= nine N -= sum break nine *= 10 # get distance from last one digit less maximum # number diff = (N // len) + 1 # d will store dth digit of current number d = N % len if (d == 0): d = len # method will return dth numbered digit # of (dist + diff) number return getDigit(dist + diff d); # Driver code to test above methods N = 251 print (getNthChar(N)) # Contributed by Afzal_Saan
// C# program to get Nth character in // concatenated Decimal String using System; class GFG { // Utility method to get dth digit of number N static char getDigit(int N int d) { string str = Convert.ToString(N); return str[d - 1]; } // Method to return Nth character in // concatenated decimal string static char getNthChar(int N) { // sum will store character // escaped till now int sum = 0 nine = 9; // dist will store numbers // escaped till now int dist = 0 len; // loop for number lengths for (len = 1; ; len++) { // nine*len will be incremented characters // and nine will be incremented numbers sum += nine * len; dist += nine; if (sum >= N) { // restore variables to previous // correct state sum -= nine * len; dist -= nine; N -= sum; break; } nine *= 10; } // get distance from last one digit // less maximum number int diff = (int)(Math.Ceiling((double)(N) / (double)(len))); // d will store dth digit of // current number int d = N % len; if (d == 0) d = len; // method will return dth numbered // digit of (dist + diff) number return getDigit(dist + diff d); } // Driver code static void Main() { int N = 251; Console.WriteLine(getNthChar(N)); } } // This code is contributed by mits
// PHP program to get Nth character // in concatenated Decimal String // Method to get dth digit // of number N function getDigit($N $d) { $string = strval($N); return $string[$d - 1]; } // Method to return Nth character // in concatenated decimal string function getNthChar($N) { // sum will store character // escaped till now $sum = 0; $nine = 9; // dist will store numbers // escaped till now $dist = 0; // loop for number lengths for($len = 1; $len < $N; $len++) { // nine*len will be incremented characters // and nine will be incremented numbers $sum += $nine * $len; $dist += $nine; if ($sum >= $N) { // restore variables to // previous correct state $sum -= $nine * $len; $dist -= $nine; $N -= $sum; break; } $nine *= 10; } // get distance from last one // digit less maximum number $diff = ($N / $len) + 1; // d will store dth digit // of current number $d = $N % $len; if ($d == 0) $d = $len; // method will return dth numbered // digit of (dist + diff) number return getDigit($dist + $diff $d); } // Driver code $N = 251; echo getNthChar($N); // This code is contributed by mits ?> <script> // JavaScript program to get Nth // character in concatenated // Decimal String // Utility method to get dth // digit of number N function getDigit(N d) { let str = N.toString(); return str[d - 1]; } // Method to return Nth character in // concatenated decimal string function getNthChar(N) { // Sum will store character // escaped till now let sum = 0 nine = 9; // dist will store numbers // escaped till now let dist = 0 len; // Loop for number lengths for(len = 1; ; len++) { // nine*len will be incremented // characters and nine will be // incremented numbers sum += nine * len; dist += nine; if (sum >= N) { // Restore variables to // previous correct state sum -= nine * len; dist -= nine; N -= sum; break; } nine *= 10; } // Get distance from last one digit // less maximum number let diff = (Math.ceil((N) / (len))); // d will store dth digit // of current number let d = N % len; if (d == 0) d = len; // Method will return dth numbered digit // of (dist + diff) number return getDigit(dist + diff d); } // Driver Code let N = 251; document.write(getNthChar(N)); // This code is contributed by code_hunt </script>
Produktion
2
Tidskomplexitet: O(Log N) där N är det givna heltal.
Hjälputrymme: O(1) eftersom inget extra utrymme används.
Skapa frågesport