An constant space O(1) approach

As you know the life expectancy of chicks is 6 days, so in order to get the number of chicks alive today (lets say ith day), you have to subtract the newBornChick at i – 6th day from ith day and double it, described above. This method of creating vector of size 50 can be reduced by only size 7 or constant space by simply creating a findIndex() method, which takes the ith element as input and return an index by doing a modulo division with 6. if i = 7 then findIndex() will return 1 and we will store the value (newly born chicks on that day) to newBornChicks[i], and if the method return 0, we will store the value at index 6(means this method will return 6).

Here, we will maintain a vector/array of size 7 which will store the number of newly born chicks every day.

Follow the steps below to implement the above idea:

Declare an array newBornChicks[] and totalChicks[] of size 7
- Initialise newBornChicks[1] and totalChicks = 1; giving the initial values.
Run a for loop from 1 to N (inclusive).
check, if i is less than equal 6,
- If true, store double of totalChicks at newBornChicks[i].
- update totalChicks with totalChicks + newBornChicks[i].
if i is greater than 6,
- first find the index by performing modulus division operation
- subtract the number of dead chicks which are born i-6th day, totalChicks -= newBornChicks[index].
- now push the today’s new born chicks to at that index.
- and update the total chicks by totalChicks with today’s newBornChicks
Return the totalChicks.

Below is the implementation of the above approach:

C++

/// C++ implementation 
#include<bits/stdc++.h>
using namespace std;
 
 
class GFG 
{
    int findIndex (int k)
    {
          if(k%6 == 0)
        {
              ///returning the end location which is 6;
              return 6;
        }
          else
        {
            /// returning the mod of 6 to maintain the array location from 1 to 5.
              return (k%6);
        }
    }
     
public:
    long long int NoOfChicks(int N)
    {
        /// if n == 1 
        if(N == 1)
        {
            return 1;
        }
         
          /// declearing newBornChicks array and totalChicks 
        long long int  newBorn[7], totalChicks;
         
          /// initialising by 1 
        newBorn[1] = totalChicks = 1;
         
         
          /// loop will run from 2 to n (inclusive).
        for(int i = 2; i <= N; i++)
        {
            if(i <= 6)
            {
                  /// instead of multiply by two, using leftShift by 1.
                  /// storing today's newBornChicks at index i.
                newBorn[i] = totalChicks<<1;
                  /// updating today total alive chicks
                totalChicks += newBorn[i];
            }
            else
            {
                int index = findIndex(i);
                 
                /// subtracting dead chicks from total chicks present today.
                totalChicks -= newBorn[index];
                 
                /// instead of multiply by two, using leftShift by 1.
                newBorn[index] = totalChicks<<1;
                  /// updating today total alive chicks
                totalChicks += newBorn[index];
            }
        }
        return totalChicks;
    }
};
 
//{ Driver Code Starts.
int main()
{
    int N = 7;
      GFG obj;
    cout << obj.NoOfChicks(N) <<"\n";
    return 0;
}
// } Driver Code Ends

Java

/// Java implementation 
public class GFG
{
    private static int findIndex (int k)
    {
        if(k%6 == 0)
        {
              ///returning the end location which is 6;
              return 6;
        }
          else
        {
            /// returning the mod of 6 to maintain the array location from 1 to 5.
              return (k%6);
        }
    }
     
    public static long NoOfChicks(int N)
    {
        if(N == 1)
        {
            return 1;
        }
         
        /// declearing newBornChicks array and totalChicks 
        long []newBorn = new long[7];
        long totalChicks;
         
        /// initialising by 1 
        newBorn[1] = totalChicks = 1;
         
         
        for(int i = 2; i <= N; i++)
        {
            if(i <= 6)
            {
                /// instead of multiply by two, using leftShift by 1.
                  /// storing today's newBornChicks at index i.
                newBorn[i] = totalChicks<<1;
                  /// updating today total alive chicks
                totalChicks += newBorn[i];
            }
            else
            {
                int index = findIndex(i);
                 
                  /// subtracting dead chicks from total chicks present today.
                totalChicks -= newBorn[index];
                 
                /// instead of multiply by two, using leftShift by 1.
                newBorn[index] = totalChicks<<1;
                  /// updating today total alive chicks
                totalChicks += newBorn[index];
            }
        }
         
        return totalChicks;
    }
   
   
      /// main class 
      public static void main(String[] args)
    {
        int n = 7;
  
        System.out.println(NoOfChicks(n));
    }
}

Python

# Python implementation
def findIndex(k):
 
    if(k % 6 == 0):
        # returning the end location which is 6;
        return 6
    else:
 
        # returning the mod of 6 to maintain the array location from 1 to 5.
        return (k % 6)
 
def NoOfChicks(N):
 
    # if n == 1
    if(N == 1):
        return 1
 
    # ndeclearing newBornChicks array and totalChicks
    newBorn = []
    totalChicks = 0
    for i in range(0, 7):
        newBorn.append(0)
 
    # initialising by 1
    newBorn[1] = totalChicks = 1
 
    # loop will run from 2 to n (inclusive)
    for i in range(2, N + 1):
        if(i <= 6):
            # instead of multiply by two, using leftShift by 1.
            # storing today's newBornChicks at index i.
            newBorn[i] = totalChicks << 1
 
            # updating today total alive chicks
            totalChicks += newBorn[i]
 
        else:
            index = findIndex(i)
 
            # subtracting dead chicks from total chicks present today.
            totalChicks -= newBorn[index]
 
            # instead of multiply by two, using leftShift by 1.
            newBorn[index] = totalChicks << 1
 
            # updating today total alive chicks
            totalChicks += newBorn[index]
 
    return totalChicks
 
# Driver Code
N = 7
print(NoOfChicks(N))
 
# This code is contributed by Samim Hossain Mondal.

C#

// Include namespace system
using System;
 
// / C# implementation
public class GFG
{
    private static int findIndex(int k)
    {
        if (k % 6 == 0)
        {
            // /returning the end location which is 6;
            return 6;
        }
        else
        {
            // / returning the mod of 6 to maintain the array location from 1 to 5.
            return (k % 6);
        }
    }
    public static long NoOfChicks(int N)
    {
        if (N == 1)
        {
            return 1;
        }
        // / declearing newBornChicks array and totalChicks 
        long[] newBorn = new long[7];
        long totalChicks;
        // / initialising by 1 
        newBorn[1] = totalChicks = 1;
        for (int i = 2; i <= N; i++)
        {
            if (i <= 6)
            {
                // / instead of multiply by two, using leftShift by 1.
                // / storing today's newBornChicks at index i.
                newBorn[i] = totalChicks << 1;
                // / updating today total alive chicks
                totalChicks += newBorn[i];
            }
            else
            {
                var index = GFG.findIndex(i);
               
                // / subtracting dead chicks from total chicks present today.
                totalChicks -= newBorn[index];
               
                // / instead of multiply by two, using leftShift by 1.
                newBorn[index] = totalChicks << 1;
               
                // / updating today total alive chicks
                totalChicks += newBorn[index];
            }
        }
        return totalChicks;
    }
   
    // / main class
    public static void Main(String[] args)
    {
        var n = 7;
        Console.WriteLine(GFG.NoOfChicks(n));
    }
}
 
// This code is contributed by utkarshshirode02

Javascript

// Javascript implementation 
    function findIndex (k)
    {
          if(k%6 == 0)
        {
         
              ///returning the end location which is 6;
              return 6;
        }
          else
        {
         
            /// returning the mod of 6 to maintain the array location from 1 to 5.
              return (k%6);
        }
    }
     
function  NoOfChicks( N)
    {
        /// if n == 1 
        if(N == 1)
        {
            return 1;
        }
         
          /// declearing newBornChicks array and totalChicks 
        let  newBorn =[], totalChicks;
        for(let i = 0; i < 7; i++)
            newBorn.push(0);
         
          /// initialising by 1 
        newBorn[1] = totalChicks = 1;
         
         
          /// loop will run from 2 to n (inclusive).
        for(let i = 2; i <= N; i++)
        {
            if(i <= 6)
            {
                  /// instead of multiply by two, using leftShift by 1.
                  /// storing today's newBornChicks at index i.
                newBorn[i] = totalChicks<<1;
                 
                  /// updating today total alive chicks
                totalChicks += newBorn[i];
            }
            else
            {
                let index = findIndex(i);
                 
                /// subtracting dead chicks from total chicks present today.
                totalChicks -= newBorn[index];
                 
                /// instead of multiply by two, using leftShift by 1.
                newBorn[index] = totalChicks<<1;
                 
                  /// updating today total alive chicks
                totalChicks += newBorn[index];
            }
        }
        return totalChicks;
    }
 
 
    let N = 7;
      console.log(NoOfChicks(N));
       
      // This code is contributed by garg28harsh.

Output

Time Complexity: O(N).
Auxiliary Space: O(1).

Find the number of Chicks in a Zoo at Nth day

Given that a zoo has a single chick. A chick gives birth to 2 chicks every day and the life expectancy of a chick is 6 days. The task is to find the number of chicks on the N^th day.

Examples:

Input: N = 3
Output: 9
First day: 1 chick
Second day: 1 + 2 = 3
Third day: 3 + 6 = 9

Input: N = 12
Output: 173988

Simple approach: It is given that the life expectancy of a chick is 6 days, so no chick dies till the sixth day. The everyday population of the current day will be 3 times of the previous day. One more thing is to note that the chick born on ith day is not counted on that day, it will be counted in the next day and the changes begin from the seventh day. So main calculation starts from the seventh day onwards.
On Seventh Day: Chicks from the 1st day die so based on manual calculation it will be 726.
On Eighth Day: Two newborn chicks born on (8-6)th i.e 2nd day dies. This will affect the current population by 2/3. This population needs to be get deducted from the previous day’s population because today i.e 8th day more newborns will be born, so we cannot deduct directly from today’s population. This will then be multiplied by three times because of newborns born on that day.

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
 
// Function to return the number
// of chicks on the nth day
ll getChicks(int n)
{
 
    // Size of dp[] has to be
    // at least 6 (1-based indexing)
    int size = max(n, 7);
    ll dp[size];
 
    dp[0] = 0;
    dp[1] = 1;
 
    // Every day current population
    // will be three times of the previous day
    for (int i = 2; i <= 6; i++) {
        dp[i] = dp[i - 1] * 3;
    }
 
    // Manually calculated value
    dp[7] = 726;
 
    // From 8th day onwards
    for (int i = 8; i <= n; i++) {
 
        // Chick population decreases by 2/3 everyday.
        // For 8th day on [i-6] i.e 2nd day population
        // was 3 and so 2 new born die on the 6th day
        // and so on for the upcoming days
        dp[i] = (dp[i - 1] - (2 * dp[i - 6] / 3)) * 3;
    }
 
    return dp[n];
}
 
// Driver code
int main()
{
    int n = 7;
 
    cout << getChicks(n);
 
    return 0;
}

Java

// Java implementation of the approach
 
import java.util.*;
 
public class GFG {
 
 
// Function to return the number
// of chicks on the nth day
static long getChicks(int n)
{
 
    // Size of dp[] has to be
    // at least 6 (1-based indexing)
    int size = Math.max(n, 7);
    long []dp = new long[size+1];
 
    dp[0] = 0;
    dp[1] = 1;
 
    // Every day current population
    // will be three times of the previous day
    for (int i = 2; i <= 6; i++) {
        dp[i] = dp[i - 1] * 3;
    }
 
    // Manually calculated value
    dp[7] = 726;
 
    // From 8th day onwards
    for (int i = 8; i <= n; i++) {
 
        // Chick population decreases by 2/3 everyday.
        // For 8th day on [i-6] i.e 2nd day population
        // was 3 and so 2 new born die on the 6th day
        // and so on for the upcoming days
        dp[i] = (dp[i - 1] - (2 * dp[i - 6] / 3)) * 3;
    }
 
    return dp[n];
}
 
// Driver code
public static void main(String[] args) {
int n = 7;
 
    System.out.println(getChicks(n));
    }
}
// This code has been contributed by 29AjayKumar

Python3

     
# Python implementation of the approach
  
# Function to return the number
# of chicks on the nth day
def getChicks(n):
  
    # Size of dp[] has to be
    # at least 6 (1-based indexing)
    size = max(n, 7);
    dp = [0]*(size+1);
  
    dp[0] = 0;
    dp[1] = 1;
  
    # Every day current population
    # will be three times of the previous day
    for i in range(2,7):
        dp[i] = dp[i - 1] * 3;
  
    # Manually calculated value
    dp[7] = 726;
  
    # From 8th day onwards
    for i in range(8,n+1):
  
        # Chick population decreases by 2/3 everyday.
        # For 8th day on [i-6] i.e 2nd day population
        # was 3 and so 2 new born die on the 6th day
        # and so on for the upcoming days
        dp[i] = (dp[i - 1] - (2 * dp[i - 6] // 3)) * 3;
  
    return dp[n];
  
# Driver code
n = 7;
  
print(getChicks(n));
 
# This code is contributed by Princi Singh

C#

// C# implementation of the approach
using System;
 
class GFG
{
     
// Function to return the number
// of chicks on the nth day
static long getChicks(int n)
{
 
    // Size of dp[] has to be
    // at least 6 (1-based indexing)
    int size = Math.Max(n, 7);
    long []dp = new long[size+1];
 
    dp[0] = 0;
    dp[1] = 1;
 
    // Every day current population
    // will be three times of the previous day
    for (int i = 2; i <= 6; i++) 
    {
        dp[i] = dp[i - 1] * 3;
    }
 
    // Manually calculated value
    dp[7] = 726;
 
    // From 8th day onwards
    for (int i = 8; i <= n; i++) 
    {
 
        // Chick population decreases by 2/3 everyday.
        // For 8th day on [i-6] i.e 2nd day population
        // was 3 and so 2 new born die on the 6th day
        // and so on for the upcoming days
        dp[i] = (dp[i - 1] - (2 * dp[i - 6] / 3)) * 3;
    }
 
    return dp[n];
}
 
// Driver code
static public void Main ()
{
     
    int n = 7;
    Console.WriteLine(getChicks(n));
}
}
 
// This code has been contributed by @Tushil..

Javascript

<script>
 
    // Javascript implementation of the approach
     
    // Function to return the number
    // of chicks on the nth day
    function getChicks(n)
    {
 
        // Size of dp[] has to be
        // at least 6 (1-based indexing)
        let size = Math.max(n, 7);
        let dp = new Array(size+1);
        dp.fill(0);
 
        dp[0] = 0;
        dp[1] = 1;
 
        // Every day current population
        // will be three times of the previous day
        for (let i = 2; i <= 6; i++)
        {
            dp[i] = dp[i - 1] * 3;
        }
 
        // Manually calculated value
        dp[7] = 726;
 
        // From 8th day onwards
        for (let i = 8; i <= n; i++)
        {
 
            // Chick population decreases by 2/3 everyday.
            // For 8th day on [i-6] i.e 2nd day population
            // was 3 and so 2 new born die on the 6th day
            // and so on for the upcoming days
            dp[i] = (dp[i - 1] - 
            (2 * parseInt(dp[i - 6] / 3, 10))) * 3;
        }
 
        return dp[n];
    }
     
    let n = 7;
    document.write(getChicks(n));
 
</script>

Output

Time Complexity: O(n)
Auxiliary Space: O(max(n, 7)), where n is the given input.

An constant space O(1) approach

C++

Java

Python

C#

Javascript

Find the number of Chicks in a Zoo at Nth day

C++

Java

Python3

C#

Javascript

Categories

Contact US

An constant space O(1) approach

C++

Java

Python

C#

Javascript

Find the number of Chicks in a Zoo at Nth day

C++

Java

Python3

C#

Javascript

Similar Reads

Categories

Contact US