/*
Given a linked list denoting a number (each key will have numbers from 0-9), implement addOne function which takes a list and add 1 to it.
Example - For number 7899, Linked List would be 7 -> 8 -> 9 -> 9
If you add 1 to 7899, you get 7900 which is 7 -> 9 -> 0 -> 0
*/
class Node {
    public:
    int digit;
    Node* next;
    Node(int _digit, Node* _next) {
        digit = _digit;
        next = _next;
    }
};

class List {
    public:
    Node* first;
    List(Node* _first) {
        first = _first;
    }
};

void printList(List* list) {
    Node* current = list->first;
    while(current) {
        cout << current->digit;
        cout << ' ';
        current = current->next;
    }
    cout << '\n';
}


int calc(Node *list) {
    if (list == nullptr) return 1;
    int newCarry = calc(list->next);
    int dig = list->digit + newCarry;
    list->digit = dig % 10;
    return dig/10;
}

void addOne(List* list) {
    //first add 1 to the last node and propagate the carry to recursion calls
    int carry = calc(list->first);
    if (carry) {
        Node *t = new Node(carry, list->first);
        list->first = t;
    }
}

int main() {
    Node* node1 = new Node(9, NULL);
    Node* node2 = new Node(9, node1);
    Node* node3 = new Node(9, node2);
    Node* node4 = new Node(9, node3);
    List* list = new List(node4);
    printList(list); // 7 8 9 9
    addOne(list);
    printList(list); // 7 9 0 0
}

-- Problem Statement:
-- We are running an online classroom. Students sign up on
-- our platform. During sign up, they provide us their name
-- and the city they come from. Providing city is optional, so
-- some students do not provide that. Our database schema is
-- as follows.

-- We need to write SQL query to find out how many students
-- we have from each city. The report should have two
-- columns - the left column should have the name of the city
-- and the right column should have the number of students
-- from each city.

-- Expected output (order of rows does not matter):
-- Delhi  2
-- Jaipur 1
-- Patna  3
-- null   3


CREATE TABLE city (
  id INTEGER NOT NULL PRIMARY KEY,
  name VARCHAR(100) NOT NULL
);


CREATE TABLE student (
  id INTEGER NOT NULL PRIMARY KEY,
  name vARCHAR(100) NOT NULL,
  city_id INTEGER,
  FOREIGN KEY (city_id) REFERENCES city(id)
);


INSERT INTO city
(id, name)
VALUES
(1, 'Delhi'),
(2, 'Jaipur'),
(3, 'Patna'),
(4, 'Pune');

INSERT INTO student
(id, name, city_id)
VALUES
(1, 'Ravi',    1),
(2, 'Rames',    1),
(3, 'Shubham', 2),
(4, 'Mansi',   null),
(5, 'Rachna',  3),
(6, 'Mohit',   3),
(7, 'Ankita',  null),
(8, 'Anshul',  3),
(9, 'Sanchit', null);

SELECT city.name, COUNT(student.city_id)
FROM student
LEFT JOIN city
ON student.city_id = city.id
GROUP BY student.city_id

SELECT Min(c.NAME),
       Count(s.id)
FROM   student s
       LEFT JOIN city c
              ON s.city_id = c.id
GROUP  BY s.city_id; 

SELECT city.name, COUNT(*) FROM student
LEFT OUTER JOIN city ON city.id = student.city_id 
GROUP BY city.id