Coding Problem 6: Count possible ways to construct buildings [GFG - Problem Solving]

By -

 There is a road passing through a city with N plots on both sides of the road. Plots are arranged in a straight line on either side of the road. Determine the total number of ways to construct buildings in these plots, ensuring that no two buildings are adjacent to each other. Specifically, buildings on opposite sides of the road cannot be adjacent.

Using * to represent a plot and || for the road, the arrangement for N = 3 can be visualized as follows: * * * || * * *.

Note: As the answer can be very large, print it mod 109+7.

Example 1:

Input: N = 1
Output: 4
Explanation: 
Possible ways for the arrangement are B||*, *||B, B||B, *||*
where B represents a building.

Example 2:

Input: N = 3
Output: 25
Explanation: 
Possible ways for one side are BSS, BSB, SSS, SBS,
SSB where B represents a building and S
represents an empty space. Pairing up with 
possibilities on the other side of the road,
total possible ways are 25.

Your Task:
You don't need to read or print anything. Your task is to complete the function TotalWays() which takes N as input parameter and returns the total possible ways modulo 109 + 7.
 

Expected Time Complexity: O(N)
Expected Space Complexity: O(N)
 

Constraints:
1 <= N <= 100000



Solution : 

package com.coding.problems.gfg;

public class ConstructBuilding {


//User function Template for Java
        public int TotalWays(int N) {
            // Code here
            long mod = 1000000007;
            if (N == 1) {
                return 4;
            }
            long first = 1;
            long second = 1;
            long prev_f = 0, prev_s = 0;
            for (int i = 2; i <= N; i++) {//normal fibonacci
                prev_f = second;
                second = (first + second) % mod;

                first = prev_f;
                prev_s = second;
            }
            long ans = ((prev_f + prev_s));
            return (int) ((ans * ans) % mod);
        }
}

Comments

Post a Comment

Popular posts from this blog

Primitive Data Types in java

By -
Image
Primitive Data Types   Expect boolean and char remaining data types are consider assigned data types because we can represent both positive and negative numbers. byte : size : 1 byte  ( 8 bit) max value : 127 min value: 128 Range: -128 to 127 a byte is the best choice,  if we want to handle data in terms of streams either from file or form the network. syntax : byte b = 10; Default value : 0 short: size: 2 bytes (16 bit) Range: - 2 power 15 to 2 power 15 -1 the short data type is best suitable for 16-bit processors like 8085 but these processors are completed outdated and hence corresponding data type is also outdated datatype. syntax : short b = 10; Default value : 0 int : size: 4 bytes (32 bit) Range: -2 power 31 to 2 power 31 -1 syntax :  int b = 10; Default value : 0 long : size: 8 bytes (64 bit) Range : - 2 power 63 to 2 power 63 -1  syntax : long b = 1051541; Default value : 0 All the above data types (byte, short, int, long ) use to represent integral val...
Read more

let - Keyword in JavaScript (Block scope)

By -
Image
Before ES2015  javascript variable has only two scopes i.e.  Global Scope   and   Function Scope . but in ES2015 they introduced the let keyword. this keyword provides Block scope variables. Block scope means  Variables declared inside a block  {}  cannot be accessed from outside the block. For Example : function getPersonDetails(){       var name ="Nilesh";       let newName = "Nil" } console.log("Print variable with var "+ name);    // you can access name variable outside function console.log("print variable value with let"+newName);  // you can not access newName Variable outside. In the above example getPersonDetails is a function that contains two variables "name " and "newName" with the keyword var and let. hear you can access the name variable which is declared with var keyword outside of the function. but you can not access the newName variables which is declared with the let keyword outside of the f...
Read more

Coding Problem 4: Smallest window containing 0, 1 and 2 [GFG - Problem Solving]

By -
  Given a string   S   consisting of the characters   0 ,   1   and   2 . Your task is to find the length of the   smallest substring  of string   S   that contains all the three characters   0, 1  and   2 . If no such substring exists, then return   -1 . Example 1: Input: S = 10212 Output: 3 Explanation: The substring 102 is the smallest substring that contains the characters 0, 1 and 2. Example 2: Input: S = 12121 Output: -1 Explanation: As the character 0 is not present in the string S, therefor no substring containing all the three characters 0, 1 and 2 exists. Hence, the answer is -1 in this case. Your Task: Complete the function  smallestSubstring()  which takes the string  S  as input, and returns the length of the  smallest substring  of string S that contains all the three characters  0, 1  and  2. Expected Time Complexity:  O( length( S ) ) Expecte...
Read more