Programming Praxis

3 Responses to “Nth From The End”

1. Globules said

   September 12, 2018 at 4:35 AM

   A Haskell version. “Fundamentally different” is in the eye of the beholder…

   import Data.Maybe (listToMaybe)
   import           Data.Vector ((!?))
   import qualified Data.Vector as V
   import Text.Printf (printf)
   
   -- Reverse the list, returning the leading element (if any) after having dropped
   -- the first n-1 elements.
   nthFromEnd1 :: Int -> [a] -> Maybe a
   nthFromEnd1 n xs | n > 0     = listToMaybe . drop (n - 1) . reverse $ xs
                    | otherwise = Nothing
   
   -- Form a list of key/value pairs, returning the element (if any) whose
   -- zero-based key is equal to the length of the list minus n.
   nthFromEnd2 :: Int -> [a] -> Maybe a
   nthFromEnd2 n xs = let len = length xs
                      in lookup (len - n) $ zip [0..] xs
   
   -- Store the list in a vector, returning the element (if any) whose zero-based
   -- position is the length of the vector minus n.
   nthFromEnd3 :: Int -> [a] -> Maybe a
   nthFromEnd3 n xs = let (ys, len) = (V.fromList xs, V.length ys)
                      in ys !? (len - n)
   
   test :: Show a => String -> (Int -> [a] -> Maybe a) -> Int -> [a] -> IO ()
   test desc f n xs = let x = f n xs
                      in printf "%s %2d %s -> %s\n" desc n (show xs) (show x)
   
   main :: IO ()
   main = do
     let xs = [1..9] :: [Int]
   
     test "nthFromEnd1" nthFromEnd1  0 xs
     test "nthFromEnd2" nthFromEnd2  0 xs
     test "nthFromEnd3" nthFromEnd3  0 xs
   
     test "nthFromEnd1" nthFromEnd1  3 xs
     test "nthFromEnd2" nthFromEnd2  3 xs
     test "nthFromEnd3" nthFromEnd3  3 xs
   
     test "nthFromEnd1" nthFromEnd1 13 xs
     test "nthFromEnd2" nthFromEnd2 13 xs
     test "nthFromEnd3" nthFromEnd3 13 xs
   

   $ ./nthfromend
   nthFromEnd1  0 [1,2,3,4,5,6,7,8,9] -> Nothing
   nthFromEnd2  0 [1,2,3,4,5,6,7,8,9] -> Nothing
   nthFromEnd3  0 [1,2,3,4,5,6,7,8,9] -> Nothing
   nthFromEnd1  3 [1,2,3,4,5,6,7,8,9] -> Just 7
   nthFromEnd2  3 [1,2,3,4,5,6,7,8,9] -> Just 7
   nthFromEnd3  3 [1,2,3,4,5,6,7,8,9] -> Just 7
   nthFromEnd1 13 [1,2,3,4,5,6,7,8,9] -> Nothing
   nthFromEnd2 13 [1,2,3,4,5,6,7,8,9] -> Nothing
   nthFromEnd3 13 [1,2,3,4,5,6,7,8,9] -> Nothing
   
2. Daniel said

   September 13, 2018 at 5:00 PM

   Here’s a solution in C. n is zero-indexed. It doesn’t handle invalid inputs (e.g., setting n=5 for a list with three elements).

   #include <stdio.h>
   #include <stdlib.h>
   
   typedef struct node {
       int value;
       struct node* next;
   } node_t;
   
   void print_list(node_t* list) {
       printf("{");
       node_t* node = list;
       while (node != NULL) {
           if (node != list) printf("->");
           printf("%d", node->value);
           node = node->next;
       }
       printf("}");
   }
   
   int length(node_t* list) {
       node_t* node = list;
       int len = 0;
       while (node != NULL) {
           ++len;
           node = node->next;
       }
       return len;
   }
   
   void reverse(node_t** list) {
       node_t* prev = NULL;
       node_t* node = NULL;
       node_t* next = *list;
       while (next != NULL) {
           prev = node;
           node = next;
           next = next->next;
           node->next = prev;
       }
       *list = node;
   }
   
   // Get length of list. Then walk the list to the
   // nth element from the end and return.
   int from_end1(node_t* list, int n) {
       int len = length(list);
       node_t* node = list;
       for (int i = 1; i < len - n; ++i) {
           node = node->next;
       }
       return node->value;;
   }
   
   // Reverse the list. Then get the nth element.
   // Reverse the list back to its original ordering
   // and return.
   int from_end2(node_t** list, int n) {
       reverse(list);
       node_t* node = *list;
       for (int i = 0; i < n; ++i) {
           node = node->next;
       }
       reverse(list);
       return node->value;
   }
   
   // Walk n elements into the list. Then walk from there
   // and from the beginning of the list until the first
   // pointer reaches the end.
   int from_end3(node_t* list, int n) {
       node_t* n1 = list;
       node_t* n2 = list;
       for (int i = 0; i < n; ++i) {
           n1 = n1->next;
       }
       while (n1 != NULL && n1->next != NULL) {
           n1 = n1->next;
           n2 = n2->next;
       }
       return n2->value;
   }
   
   int main(int argc, char* argv[]) {
       if (argc < 2) {
           fprintf(stderr, "Usage: %s N [X1 [X2 [X3 ...]]]\n", argv[0]);
           return EXIT_FAILURE;
       }
       int n = atoi(argv[1]);
       node_t* list = NULL;
       for (int i = argc - 1; i >= 2; --i) {
           node_t* node = (node_t*)malloc(sizeof(node_t));
           node->value = atoi(argv[i]);
           node->next = list;
           list = node;
       }
       printf("list:\n  ");
       print_list(list);
       printf("\n");
       int e1 = from_end1(list, n);
       printf("from_end1(list, %d):\n  %d\n", n, e1);
       int e2 = from_end2(&list, n);
       printf("from_end2(list, %d):\n  %d\n", n, e2);
       int e3 = from_end3(list, n);
       printf("from_end3(list, %d):\n  %d\n", n, e3);
       node_t* node = list;
       while (node != NULL) {
           node_t* next = node->next;
           free(node);
           node = next;
       }
       return EXIT_SUCCESS;
   }
   

   Example output:

   $ ./a.out 0 {0..9}
   list:
     {0->1->2->3->4->5->6->7->8->9}
   from_end1(list, 0):
     9
   from_end2(list, 0):
     9
   from_end3(list, 0):
     9
   
   $ ./a.out 3 {0..9}
   list:
     {0->1->2->3->4->5->6->7->8->9}
   from_end1(list, 3):
     6
   from_end2(list, 3):
     6
   from_end3(list, 3):
     6
   
   $ ./a.out 8 {0..9}
   list:
     {0->1->2->3->4->5->6->7->8->9}
   from_end1(list, 8):
     1
   from_end2(list, 8):
     1
   from_end3(list, 8):
     1
   
3. sri vignesh said

   September 14, 2018 at 1:55 PM

   I know only one.
   b= [10,9,8,7,6,5,4,3,2,1,0]
   index = 7
   print b[len(b) – (index+1)]