Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Example
3.1.
Input
3.2.
Output
3.3.
Explanation
4.
Algorithm
4.1.
C++ Code
4.2.
Input
4.3.
Output
5.
Complexities
5.1.
Time complexity
5.2.
Space complexity
6.
Frequently Asked Questions
6.1.
What do you understand by the depth of a vertex?
6.2.
Why does DFS employ stack?
6.3.
What do you mean by a simple path in a graph?
6.4.
What is the load factor of a hash table?
6.5.
What memory representation does a graph have?
7.
Conclusion
Last Updated: Mar 27, 2024
Medium

Optimal read list for given number of days

Author Manan Singhal
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

graph is a data structure defined as a group of vertices where edges help to connect these vertices. Graphs are directedundirected, weighted, unweighted, cyclic, acyclic, etc.

The article will calculate the optimal read list for a given number of days.

Introduction

Problem Statement

You have been given the number of chapters a person wants to read and the days he has to read all the chapters. You need to calculate the optimized solution of chapters so that the person doesn't read too many chapters in a single day.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Example

Input

pages = {3, 2, 2, 4}
days = 3

Output

Day 1: 1 
Day 2: 2 3 
Day 3: 4

Explanation

In the given input graph, all the possible paths will be:

  1. {1,2}, {3}, {4} -> 5
  2. {1}, {2,3}, {4} -> 4
  3. {1}, {3}, {2,4} -> 6
  4. {2}, {1,3}, {4} -> 5
  5. {2}, {3}, {1,4} -> 7
  6. {1}, {2}, {3,4} -> 6
     

The most optimal read will be {1}, {2,3}, {4}. The maximum number of pages to read in a single day will be 4.

Algorithm

With the help of DFS Algorithm, we will solve this problem. We start from chapter 1 and apply DFS to count the edges. We will keep an eye on the visited vertex. If we reach the destination vertex and the sum of reaching the destination is less than the optimal path, then we update the optimal path to this path. We will construct a directed acyclic graph and then find the optimal path using DFS, as mentioned above.

Depth First Search

Let's start with the implementation of the code.

C++ Code

/* C++ Program: Optimal read list for given number of days */
#include <iostream>
#include <vector>
#include <list>
#include <cstring>
#include <cmath>
#include <limits>

using namespace std;

/* print the reading schedule to follow */
void printReadingSchedule(const vector<int>& pages, int nDays) {
    int nChapters = pages.size();

    if (nChapters < nDays) {
        cout << "read a chapter per day." << endl;
        return;
    }

    if (nDays == 0) {
        cout << "no day to read." << endl;
        return;
    }

    /* store optimal costs, each cost means the sum of abs(deviation)s */
    int dp[nDays + 1][nChapters + 1];

    /* for constructing path */
    int prev[nDays + 1][nChapters + 1];
    memset(prev, -1, sizeof(prev));

    /* accumulate sum */
    int sum[nChapters + 1];
    sum[0] = 0;
    for (int i = 1; i <= nChapters; ++i) {
        sum[i] = sum[i - 1] + pages[i - 1];
    }
    int avg = round(sum[nChapters]/(double)nDays);

    /* read all chapters in one day */
    for (int j = 1; j <= nChapters; ++j) {
        dp[1][j] = abs(sum[j] - avg);
    }

    for (int i = 2; i <= nDays; ++i) {
        for (int j = 2; j <= nChapters; ++j) {
            if (i == j) {
                /* if number of days equals to chapters, read a chapter per day */
                dp[i][j] = dp[i - 1][j - 1] + abs(sum[j] - sum[j - 1] - avg);
                prev[i][j] = j - 1;
            } else {
                dp[i][j] = numeric_limits<int>::max();
                for (int k = i - 1; k < j; ++k) {
                    int rangeSum = sum[j] - sum[k];
                    int cost = dp[i - 1][k] + abs(rangeSum - avg);
                    if (cost < dp[i][j]) {
                        dp[i][j] = cost;
                        prev[i][j] = k;
                    }
                }
            }
        }
    }

    /* construct path */
    list<int> path;
    {
        int i = nDays;
        int j = nChapters;

 
        while (prev[i][j] != -1) {
            int k = prev[i][j];
            path.push_front(k);
            i--;
            j = k;
        }
        path.push_back(nChapters);
    }

    /* print */
    int day = 1;
    int s = 0;
    for (auto e : path) {
        printf("Day %d: ", day);
        while (s < e) {
            printf("%d ", s + 1);
            ++s;
        }
        printf("\n");
        ++day;
    }
}

/* Main Program */
int main() {
	printReadingSchedule({3, 2, 2, 4}, 3);
	return 0;
}

Input

pages = {3, 2, 2, 4}
days = 3

Output

Day 1: 1 
Day 2: 2 3 
Day 3: 4

Complexities

Time complexity

O(NxM), where N stands for the pages and M stands for the days available.

Reason: We are traversing all the possible outcomes after calculating the average of the pages in the chapters. So, we can conclude that the time complexity of this algorithm is O(NxM).

Space complexity

O(NxM), where N stands for the pages and M stands for the days available

Reason: We need a matrix of size NxM to save path count from keeping track of the movement of the graph.
Check out this problem - Subarray Sum Divisible By K

Frequently Asked Questions

What do you understand by the depth of a vertex?

The number of branches that lead from a root to a vertex determines the vertex's depth. Therefore, the root's depth is zero. The number of the vertex in the path from the root to the vertex determines the vertex's level.

Why does DFS employ stack?

When a dead end occurs during any iteration, the Depth First Search (DFS) method employs a stack to track where to find the next vertex to begin a search.

What do you mean by a simple path in a graph?

A simple path in geometry is a simple curve, precisely a continuous injective function from an actual number interval to a metric space, topological space, or, more generally. A simple path in graph theory is a path through a graph that doesn't have recurring vertices.

What is the load factor of a hash table?

The load factor can be defined as (m/n), where m is the preferred number of entries that can be added before the size of the underlying data structure needs to be increased, and n is the overall size of the hash table.

What memory representation does a graph have?

A graph can be kept in memory in three ways: Edges act as pointers, and nodes as objects. A matrix that includes each edge weight that connects nodes x and y. edges between numbered nodes, listed.

Conclusion

In the article, we have calculated the optimal read list for a given number of days. We hope this article will help you understand the concept of graphs. Check out our other blogs on this topic:

Refer to our guided paths on Coding Ninjas Studio to learn about Data Structure and Algorithms, Competitive Programming, JavaScript, etc. Enroll in our courses and refer to our mock test available. Have a look at the interview experiences and interview bundle for placement preparations.

Happy Coding!

Previous article
Kahn's Algorithm for Topological Sorting
Next article
All Possible Walks from a Source to a Destination with exactly k Edges
Live masterclass