Q8. Given an array A, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.


## Intuition Behind the Algorithm

The core idea behind this algorithm is the efficient reorganization of the array elements. The goal is to shift all zeros to the end of the array while preserving the relative order of non-zero elements. This is achieved through a two-pointer approach where one pointer (`j`) is used to track the position for the next non-zero element, and the other (`i`) iterates through the array.

```cpp
#include <bits/stdc++.h>
using namespace std;

// Function to move all zeros to the end of the array
void moveZeroes(vector<int> &nums) {
 int n = nums.size(); // Size of the input array
 int j = 0; // Pointer to track the position for the next non-zero element

 // Iterate through the array
 for (int i = 0; i < n; i++) {
 // Check if the current element is non-zero
 if (nums[i] != 0) {
 // Swap the non-zero element with the element at position 'j'
 swap(nums[i], nums[j]);
 // Increment 'j' to update the position for the next non-zero element
 j++;
 }
 }
}

// Main function
int main() {
 int n; // Variable to hold the size of the array
 cin >> n; // Input for the size of the array

 vector<int> nums(n); // Vector to store the elements of the array

 // Input the elements of the array
 for (int i = 0; i < n; i++)
 cin >> nums[i];

 moveZeroes(nums); // Call the function to rearrange the array

 // Output the rearranged array
 for (int i = 0; i < n; i++)
 cout << nums[i] << " ";

 return 0; // End of the program
}
```

## Code Walkthrough

The function `moveZeroes` takes a vector of integers `nums` as its argument. It starts by initializing two variables: n, representing the size of the array, and j, a counter for the position of the next non-zero element.

The algorithm then iterates through the array using a for-loop. Inside the loop, it checks each element. If the current element (`nums[i]`) is non-zero, it is swapped with the element at the position indicated by `j`. This operation effectively places the non-zero element in its correct position while moving the zero towards the end. The counter `j` is then incremented.

In the `main` function, the array size (`n`) and the array elements are taken as input from the user. The `moveZeroes` function is called to perform the rearrangement, and the modified array is printed.

## Time and Space Complexity Analysis

* The time complexity of this algorithm is O(n), where n is the number of elements in the array. This is because the algorithm iterates through the array once, performing a constant number of operations for each element.

* The space complexity is O(1), indicating that the algorithm uses a constant amount of extra space. The rearrangement is done in place without requiring additional storage proportional to the input size.

## Key Points of the Algorithm

* Two-Pointer Technique: This is crucial for efficiently sorting the elements in a single pass.
* In-Place Rearrangement: The algorithm does not use extra space for another array, making it space-efficient.
* Preservation of Order: Non-zero elements maintain their original order post rearrangement.

## Conclusion

The presented algorithm efficiently solves the "Move Zeros" problem with optimal time and space complexity.

Web development is the work involved in developing a website for the Internet or an Intranet. It can range from developing a simple single static page of plain text to complex web applications.

WEB DEVELOPMENT

Q1. You have to given an array A of size N. Find all the elements which appear more than floor(N/3) times in the given array. There is a condition that you have to do your job in O(N) time complexity and O(1) space complexity.

Question Link - [Click Here to Solve This Problem](https://codeskiller.codingblocks.com/problems/1509)

## Intuition Behind the Algorithm

The algorithm is designed based on the idea that if a number appears more than 
N/3 times in an array, there can be at most two such numbers. This is because if there were three or more such numbers, their total count would exceed *N*, which is impossible.

To identify these potential candidates, the algorithm maintains two counters and two potential elements. The key idea is to pair different elements and effectively 'cancel' them out, keeping track of potential majority elements.

```cpp
#include<iostream>
#include<vector>

using namespace std;

// Function to find all elements appearing more than floor(N/3) times in the array
vector<int> majorityElements(vector<int> v) {
 // Initialize the first potential majority element and its count
 int element1 = v[0];
 int count1 = 1;

 // Initialize the second potential majority element and its count
 int element2 = 0;
 int count2 = 0;

 // First pass: Identify potential majority elements
 for (int i = 1; i < v.size(); i++) {
 if (element1 == v[i]) {
 count1++;
 } else if (element2 == v[i]) {
 count2++;
 } else if (count1 == 0) {
 element1 = v[i];
 count1 = 1;
 } else if (count2 == 0) {
 element2 = v[i];
 count2 = 1;
 } else {
 count1--;
 count2--;
 }
 }

 // Reset counts for the second pass
 count1 = count2 = 0;

 // Second pass: Confirm the majority elements
 for (int i = 0; i < v.size(); i++) {
 if (v[i] == element1) count1++;
 else if (v[i] == element2) count2++;
 }

 // Prepare the answer vector
 vector<int> ans;
 if (count1 > v.size() / 3) {
 ans.push_back(element1);
 }
 if (count2 > v.size() / 3) {
 ans.push_back(element2);
 }

 return ans;
}

int main() {
 // Read the size of the array
 int n;
 cin >> n;

 // Read the elements of the array
 vector<int> v;
 int x;
 for (int i = 0; i < n; i++) {
 cin >> x;
 v.push_back(x);
 }

 // Find majority elements
 vector<int> ans = majorityElements(v);

 // Output the results
 if (ans.size() == 0) {
 cout << "No Majority Elements" << endl;
 } else {
 for (int i = 0; i < ans.size(); i++) {
 cout << ans[i] << ' ';
 }
 }

 cout << endl;

 return 0;
}
```

## Description of the Code
 
1. Initialization:

* Two elements (element1 and element2) are initialized with the first element of the array and a dummy value (0), respectively.
* Corresponding counts (count1 and count2) are set to 1 and 0.

2. First Pass - Identifying Potential Majority Elements:

* Iterate through the array:
 
a) Increment the count of element1 or element2 if the current element matches either.
 
b) If count1 or count2 is zero, replace the respective element with the current element and reset its count to 1.
 
c) If the current element matches neither element1 nor element2, decrement both count1 and count2.
* This step ensures that by the end, element1 and element2 are the candidates for being the majority elements.

3. Reset Counts:

* Reset count1 and count2 to zero for the second pass.

4. Second Pass - Confirming Majority Elements:

* Iterate through the array again, counting the occurrences of element1 and element2.
* If the count of either exceeds N/3, they are confirmed as majority elements.

5. Preparing the Answer:

* Check the final counts of element1 and element2.
* If their counts exceed N/3, add them to the answer vector.

6. Output:

* If no majority elements are found, output "No Majority Elements".
* Otherwise, output the majority elements.


## Time and Space Complexity
* Time Complexity: O(N). The array is iterated over twice, making the time complexity linear.
* Space Complexity: O(1). The space used does not depend on the size of the input array, as only a fixed number of variables are used.

## Key Points

* The algorithm efficiently finds the potential majority elements using a clever counting mechanism.
* It ensures that if there are elements meeting the criteria, they will be among the candidates after the first pass.
* The second pass is crucial to confirm whether the candidates actually meet the criteria.
* This solution elegantly combines the principles of majority voting with an efficient two-pass system, ensuring the desired time and space complexity constraints are met.

Finding Majority Element

Q2. Ramu has an array of strings. He want to find a string s such that it is a concatenation of sub-sequence of given array and have unique characters. A sub-sequence of an array is a set of elements that can be obtained by deleting zero or more elements from the array and keeping the order same. Write a program to print the maximum possible length of s.

Question Link -
[Click Here to Solve This Problem](https://codeskiller.codingblocks.com/problems/1506)


## Intuition Behind the Algorithm

The underlying approach is to use recursion to explore all possible combinations of subsequences. Each recursive step decides whether to include or exclude the current string from the array in building the unique string s. The key is to ensure that at each step, the resultant string maintains its uniqueness of characters.


```cpp
#include <iostream>
#include <vector>
#include <climits>

using namespace std;

// Recursive function to find the maximum length of a unique character string
int Fun(vector<string> v, int i, string s) {
 // Base case: When all strings have been considered
 if (i == v.size()) {
 // If length of the string s is greater than 26, it can't be unique
 if (s.length() > 26)
 return 0;

 // Frequency array to check for unique characters in s
 int freq[26] = {0};
 for (int k = 0; k < s.length(); k++) {
 // If character is repeated, return 0
 if (freq[s[k] - 'a'] == 1)
 return 0;
 freq[s[k] - 'a']++;
 }
 // Return the length of s if all characters are unique
 return s.length();
 }

 // Variables to store results of including or excluding the current string
 int op1, op2;
 op1 = op2 = INT_MIN;

 // Include the ith string if it doesn't make the total length exceed 26
 if (s.length() + v[i].length() <= 26) {
 op1 = Fun(v, i + 1, s + v[i]);
 }

 // Exclude the ith string and move to the next index
 op2 = Fun(v, i + 1, s);

 // Return the maximum of including or excluding the ith string
 return max(op1, op2);
}

// Function to start the process and return the result
int UniqueString(vector<string>& v) {
 string s = "";
 return Fun(v, 0, s);
}

int main() {
 vector<string> v;
 int n;
 cin >> n;

 // Reading the array of strings
 for (int i = 0; i < n; i++) {
 string s;
 cin >> s;
 v.push_back(s);
 }

 // Finding and printing the maximum length of unique string
 cout << UniqueString(v) << endl;

 return 0;
}
```

## Code Walkthrough

* Recursive Function Fun: This function takes the vector of strings v, the current index i, and the currently formed string s. It returns the maximum length of a unique character string formed so far.

* Base Case: If i equals the size of v, it checks if s has unique characters and returns its length if unique; otherwise, returns 0.
Frequency Array: It ensures that each character in s appears only once.
* Recursive Calls: Two scenarios are considered:

 * Including the current string: Concatenate v[i] to s and recursively call Fun with i+1.

 * Excluding the current string: Move to the next index without altering s.
* Main Function UniqueString: Initiates the recursive process and returns the result.

## Time and Space Complexity Analysis

* Time Complexity: O(2^n), where n is the number of strings in the array. In the worst case, the algorithm explores two possibilities (include or exclude) for each string.
* Space Complexity: O(n), mainly due to the recursive call stack. The depth of recursion can go up to n, and additional space for the frequency array and temporary strings is constant.

## Key Points of the Algorithm

* Recursion and Backtracking: The core of the algorithm lies in exploring all possible unique string formations using recursion.
* Optimization Checks: The function checks if the total length exceeds 26 (the total number of lowercase alphabets) to prune unnecessary recursive calls.
* Uniqueness Check: The frequency array is crucial for ensuring the uniqueness of characters in the formed string.

## Conclusion and Further Optimizations

The provided solution effectively solves the problem using a backtracking approach. However, there are possibilities for optimization:

* Memoization: To avoid re-computation, storing results of subproblems can significantly improve performance.
* Bitmasking: Instead of using a frequency array, a bitmask can represent the presence of characters, thus reducing space complexity and potentially speeding up the checks for uniqueness.

String With Unique Characters

Q3. In a test Kartik gave students an array of n non-negative integers a1, a2, …, an ,where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). The task is to find two lines, which together with x-axis forms a container, such that the container contains the most water.

Write a program to find the maximum water the container contains.

Question Link - [Click Here to Solve This Problem](https://codeskiller.codingblocks.com/problems/1505)

## Intuition Behind the Algorithm

The "Container with Most Water" problem is an excellent example of a two-pointer approach in algorithm design. The core idea is to maximize the area of water a container can hold, formed by vertical lines and the x-axis. The intuition is to start with the widest possible container and then move the pointers inward, ensuring that at each step, the potential for a larger area is not missed. The algorithm exploits the fact that the area is limited by the shorter line, and hence, moves the pointer at the shorter line inward, aiming to find a taller line that could help in maximizing the area.

```cpp
#include <iostream>
using namespace std;

int main() {
 int n;
 cin >> n; // Reading the number of vertical lines

 // Dynamically allocating array to store the heights of the lines
 int *height = new int[n];

 // Reading the heights of each line
 for (int i = 0; i < n; i++) {
 cin >> height[i];
 }

 int left = 0; // Left pointer starting from the beginning of the array
 int right = n - 1; // Right pointer starting from the end of the array
 int area = 0; // Variable to store the maximum area

 // Loop to find the maximum area
 while (left < right) {
 // Calculating the area for the current pair of lines
 // and updating the maximum area found so far
 area = max(area, min(height[left], height[right]) * (right - left));

 // Moving the pointer of the shorter line towards the center
 if (height[left] < height[right]) {
 left++;
 } else {
 right--;
 }
 }

 cout << area << endl; // Printing the maximum area

 delete[] height; // Freeing the dynamically allocated memory
 return 0;
}
```

## Code Walkthrough

* Initialization: The program begins by reading the number of lines n and then the heights of these lines into an array height.


* Setting Two Pointers: Two pointers, left and right, are initialized at the start and end of the array, representing the current container's width.

* Iterating Through Lines: The algorithm enters a loop where it calculates the area formed between the lines at the left and right pointers and updates the maximum area found so far.

* Area Calculation: min(height[left], height[right]) * (right - left) calculates the current area. It uses the shorter of the two lines to ensure the container's boundaries are correctly represented.

* Pointer Movement: Depending on which line is shorter, the corresponding pointer (left or right) is moved inward to explore potentially larger areas.

* Exit Condition: The loop continues until the left and right pointers meet, indicating that all possible containers have been considered.

## Time and Space Complexity Analysis

* Time Complexity: The algorithm runs in O(n) time. This efficiency is due to the linear traversal of the array with the two pointers, ensuring that each element is considered exactly once.
* Space Complexity: The space complexity is O(1) since the algorithm doesn't use any auxiliary space apart from the input.

## Key Points of the Algorithm

* Two-Pointer Technique: Efficiently explores the solution space by starting with the maximum width and then narrowing down.
* Greedy Choice: By always moving the shorter line, the algorithm makes a greedy choice that ensures no potential larger area is missed.
* Linear Time Complexity: Achieved by avoiding nested loops and exploring the entire array with just a single pass.

## Conclusion

The provided solution is an efficient approach to solving the "Container with Most Water" problem. It elegantly combines the two-pointer technique with a greedy strategy to achieve linear time complexity.

Container With Most Water

Q4. Krishna, a nature lover, loves to explore the winding forest trails in his town. However, he often loses his way and struggles to get back to the starting point. To overcome this problem, Krishna uses an array of positive and negative integers. Whenever he comes across a positive integer k at an index i, he moves forward k steps. Conversely, if he comes across a negative integer (-k), he moves backward k steps.

One day, Krishna found himself lost in the forest and was unable to find his way back to the starting point. He wondered if he could somehow detect a cycle in the array that would help him find his way back. This cycle would start and end at the same index and consist only of either forward or backward movements.

Krishna decided to write a program that could detect such a cycle, taking into account that the array was circular, meaning that the last element's next element was the first element, and the first element's previous element was the last element.

Krishna's program had to determine if there was a cycle in the array that met the following conditions :

* The cycle started and ended at the same index.
* The cycle's length was greater than 1.
* All movements in the cycle followed a single direction, either forward or backward.

If such a cycle existed, Krishna's program had to return 1. Otherwise, it had to return 0.

Question Link - [Click Here to Solve This Problem](https://codeskiller.codingblocks.com/problems/1508)

## Intuition Behind the Algorithm

The core idea behind the algorithm is to determine if a cycle exists in a given array that represents a series of steps (forward or backward). The unique aspect is that this array is treated as circular, implying that traversing beyond its boundaries loops back around. The challenge is to identify if there's a continuous loop that starts and ends at the same point without reversing direction, using a fast and efficient method.

```cpp
#include <iostream>
#include <vector>

using namespace std;

// Helper function to calculate the next index in a circular manner
int next(vector<int> a, int i) {
 return (i + a[i] + a.size()) % a.size();
}

// Function to determine if there is a circular loop in the vector
bool CircularLoop(vector<int> v) {
 int n = v.size(); // Get the size of the vector

 // Iterate through each element in the vector
 for (int i = 0; i < n; i++) {
 int slow = i, fast = i; // Initialize slow and fast pointers

 // Skip the current element if it's 0
 if (v[i] == 0)
 continue;

 // Loop to check for a cycle
 while (v[slow] * v[next(v, slow)] > 0 &&
 v[fast] * v[next(v, fast)] > 0 && 
 v[fast] * v[next(v, next(v, fast))] > 0) {
 slow = next(v, slow); // Move the slow pointer
 fast = next(v, next(v, fast)); // Move the fast pointer twice

 // Check if the slow and fast pointers meet
 if (slow == fast) {
 // Cycle is present, but cycle length should be > 1
 if (slow == next(v, slow))
 break;
 return true; // Cycle detected
 }
 }

 // Resetting the elements to 0 to avoid revisiting
 slow = i;
 int val = v[slow];
 while (val * v[slow] > 0) {
 int x = slow;
 slow = next(v, slow);
 v[x] = 0;
 }
 }

 return false; // No cycle found
}

int main() {
 int n;
 cin >> n; // Read the number of elements

 vector<int> v;
 for (int i = 0; i < n; i++) {
 int x;
 cin >> x; // Read each element into the vector
 v.push_back(x);
 }

 cout << CircularLoop(v) << endl; // Output the result of CircularLoop
 
 return 0;
}
```

## Code Walkthrough

* Function Definition: CircularLoop(vector<int> v) takes an integer vector v representing the steps.

* Initialization: The function starts by determining the size of the vector. It then iterates over each element of the vector using a for-loop.

* Cycle Detection: Two pointers, slow and fast, are used for each position in the array. The slow pointer moves one step at a time, while the fast pointer moves two steps. This is similar to the Floyd’s Cycle detection algorithm used in linked lists.

* Direction Consistency Check: The algorithm ensures that all movements (steps) are in the same direction. This is done by checking the product of consecutive elements; if it’s positive, the direction is consistent.

* Detecting the Loop: If the slow and fast pointers meet (slow == fast), a cycle is detected. However, a cycle's length must be greater than 1, so the algorithm checks if the current position is not the same as the next step.

* Resetting Processed Elements: After exploring each potential cycle starting point, the algorithm resets the elements to zero along the path it just traversed. This avoids rechecking the same path.

* Main Function: It reads the number of elements and the elements themselves, then calls CircularLoop and outputs the result.

## Time and Space Complexity Analysis

* Time Complexity: The algorithm has a time complexity of O(n), where n is the number of elements in the array. Each element is visited at most twice - once by the slow pointer and once by the fast pointer.

* Space Complexity: The space complexity is O(1), as no extra space is used apart from the input array and a few variables for iteration and indexing.

## Key Points of the Algorithm
* Efficiency: The algorithm efficiently finds cycles without examining every possible starting point in detail.
* Cycle Detection: Uses a two-pointer approach to detect cycles.
* Direction Check: Ensures all steps in a cycle follow the same direction.
* Avoids Redundancy: Resets visited elements to zero to prevent reprocessing.

## Conclusion

The presented algorithm is an efficient solution for detecting circular loops in an array with consistent direction. It balances the need for thorough cycle detection with the efficiency of not reprocessing elements.

Array has a Circular Loop or Not??

Q5. The heights of certain Buildings which lie adjacent to each other are given. Light starts falling from left side of the buildings. If there is a building of certain Height, all the buildings to the right side of it having lesser heights cannot see the sun . The task is to find the total number of such buildings that receive light.

Question Link - [Click Here to Solve This Problem](https://codeskiller.codingblocks.com/problems/1602)

## Intuition Behind the Algorithm

The "Sunny Buildings" problem presents a scenario where buildings stand adjacent to each other, and sunlight falls from the left. The challenge is to identify how many buildings are not overshadowed by taller buildings to their left. The core intuition here is to realize that a building will receive sunlight if it is taller than all buildings to its left. This leads to a linear scan from left to right, keeping track of the tallest building encountered so far.

```cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
 // Read the number of test cases
 int t;
 cin >> t;

 // Process each test case
 while(t--) {
 int n; // Number of buildings
 int ans = 0; // Count of buildings receiving sunlight
 int maxh = INT_MIN; // Maximum height encountered so far
 cin >> n;

 // Iterate through each building
 for(int i = 0; i < n; i++) {
 int num; // Height of the current building
 cin >> num;

 // If the current building is taller or equal to the tallest so far,
 // it receives sunlight.
 if(num >= maxh) {
 ans++;
 maxh = num; // Update the tallest building encountered
 }
 }

 // Output the count of buildings receiving sunlight for this test case
 cout << ans << endl;
 }

 return 0;
}
```

## Code Walkthrough

The provided C++ code efficiently solves the problem using a simple linear scan approach.

* Initial Setup: The code begins by reading the number of test cases t. Each test case is processed in the following steps.

* Processing Each Test Case: For each test case, the number of buildings n is read. The variables ans (to store the count of buildings receiving sunlight) and maxh (to keep track of the tallest building encountered so far) are initialized. maxh is set to INT_MIN, representing the smallest possible integer, ensuring that the first building will always be considered as receiving sunlight.

* Iterating Through Buildings: The code then iterates through each building. For each building, its height num is read. If num is greater or equal to maxh, it means this building is taller than all previous buildings and will receive sunlight. ans is incremented, and maxh is updated to num.

* Output: After processing all buildings in a test case, the total count of buildings receiving sunlight (ans) is printed.

## Time and Space Complexity Analysis

* Time Complexity: The solution has a time complexity of O(n) for each test case, where n is the number of buildings. This is because it involves a single linear scan through the array of building heights.

* Space Complexity: The space complexity is O(1), as the algorithm uses a fixed amount of additional memory regardless of the input size.

## Key Points of the Algorithm

* Linear Scan: The algorithm's strength lies in its simplicity and efficiency, accomplished through a straightforward linear scan.
* No Extra Space: It efficiently uses constant extra space.
* Instantaneous Updates: The solution immediately updates the tallest building encountered, ensuring a swift determination of which buildings receive sunlight.

## Conclusion

The provided solution is optimal for the given problem, offering an efficient and straightforward approach to identify buildings that receive sunlight.

Sunny Buildings

Q6. Alice has n candies, where the ith candy is of type candyType[i]. Alice noticed that she started to gain weight, so she visited a doctor.

The doctor advised Alice to only eat n / 2 of the candies she has (n is always even). Alice likes her candies very much, and she wants to eat the maximum number of different types of candies while still following the doctor's advice.

Given the integer array candyType of length n, return the maximum number of different types of candies she can eat if she only eats n / 2 of them.

## Intuition Behind the Algorithm

The "Distribute Candies" problem focuses on maximizing the variety of candies Alice can eat, subject to a dietary restriction. The essence of the solution lies in balancing two constraints: the total number of candies Alice can consume (half of her total candies, `n / 2`), and the variety of candy types available. The algorithm aims to identify the maximum number of unique candy types Alice can enjoy, ensuring diversity in her diet without exceeding the prescribed limit.

```cpp
#include <vector>
#include <unordered_map>
using namespace std;

// Function to find the maximum number of different types of candies Alice can eat
int distributeCandies(vector<int>& candies) {
 // Create an unordered_map to store the frequency of each type of candy
 unordered_map<int, int> m;
 // Variable to keep count of the number of unique candies
 int count = 0;
 
 // Iterate over the candies vector
 for(int i = 0; i < candies.size(); i++) {
 // Check if the candy type is already in the map
 if(m.find(candies[i]) == m.end()) {
 // If not, add the candy type to the map and increment the unique candy count
 m.insert({candies[i], 1});
 count++;
 } else {
 // If the candy type is already in the map, increment its count
 m[candies[i]]++;
 }
 }
 
 // Calculate the maximum number of different types of candies Alice can eat
 // It is the minimum of the number of unique candies and n / 2
 int ans = count < candies.size() / 2 ? count : candies.size() / 2;
 return ans;
}
```

## Code Walkthrough

The C++ solution uses an `unordered_map` to track the frequency of each candy type. This map serves as a counter for different types of candies, ensuring each type is counted only once.

* Initialization: An `unordered_map` (`m`) and a `count` variable are initialized. The map stores candy types and their occurrences, while `count` tracks the number of unique candies.

* Candy Counting Loop: Iterating through the `candies` vector, the algorithm checks if a candy type is already in the map. If not, it adds the new candy type to the map and increments `count`. This step effectively counts unique candy types.

* Calculating the Answer: The final step involves a comparison: if the `count` of unique candies is less than `n / 2`, Alice can eat all unique types. Otherwise, she is limited to `n / 2` types. The `ans` variable is set to the smaller of these two values, representing the maximum variety she can achieve.

## Time and Space Complexity Analysis
* Time Complexity: The algorithm iterates once over the `candies` vector of size n, leading to a time complexity of O(n). The operations inside the loop (map insertion/check) operate in average constant time due to the nature of `unordered_map`.

* Space Complexity: The space complexity is O(n) in the worst case, when all candy types are unique, requiring an entry in the map for each candy.

## Key Points of the Algorithm
* Efficient Counting: Using an `unordered_map` enables efficient counting of unique candy types.
* Balancing Constraints: The algorithm successfully balances the two constraints – the limit on the number of candies and the desire for maximum variety.
* Scalability: The solution scales linearly with the number of candies, making it effective for large datasets.

## Conclusion
The presented solution effectively solves the problem with linear time and space complexity. For further optimization, one might consider early termination of the loop if the count of unique candies reaches `n / 2` before the end of the array, as any additional unique candies wouldn't increase the maximum variety Alice can achieve.

Distribute Candies

Q7. A 'OverHappy' number follows the following criteria :

It is always a positive integer. The integer number is replaced by the sum of the squares of its digits and this process is repeated until the sum equals 1. 
The numbers for which the loop runs endlessly and never reach to the sum of 1 are not OverHappy numbers.

Write a program that print true if n is OverHappy number else print false.

## Intuition Behind the Algorithm

The algorithm is designed to determine whether a given positive integer is an "OverHappy Number." This concept is rooted in a repetitive process where a number is transformed by replacing it with the sum of the squares of its digits. If this iterative process eventually leads to the number 1, the number is deemed "OverHappy." The challenge lies in identifying numbers for which this process endlessly continues without reaching 1, classifying them as not "OverHappy."

```cpp
#include <bits/stdc++.h>
using namespace std;

// Function to update the number to the sum of the squares of its digits
int update(int n) {
 int s = 0;
 while (n > 0) {
 int ld = n % 10; // Extract the last digit
 s += ld * ld; // Add the square of the last digit to the sum
 n /= 10; // Remove the last digit
 }
 return s;
}

// Recursive function to check if a number is an OverHappy number
bool check(unordered_map<int, bool> &m, int n) {
 if (n == 1)
 return true; // Base case: if the number becomes 1, it's OverHappy

 if (m.find(n) != m.end())
 return false; // If the number is already in the map, it's not OverHappy

 m.insert(make_pair(n, true)); // Insert the number into the map
 n = update(n); // Update the number to the sum of the squares of its digits
 return check(m, n); // Recursively check the updated number
}

// Wrapper function to initiate the check for OverHappy number
bool isHappy(int n) {
 unordered_map<int, bool> m; // Map to keep track of numbers encountered

 return check(m, n); // Start the recursive checking process
}

// Main function to take input and output results
int main() {
 int n;
 cin >> n; // Input the number

 bool ans = isHappy(n); // Check if the number is OverHappy

 // Output the result
 if (ans)
 cout << "Over Happy Number" << endl;
 else
 cout << "Not an Over Happy Number" << endl;

 return 0;
}
```

## Code Walkthrough

The C++ code provided employs several functions to solve this problem:

* `update(int n)`: This function takes an integer and returns the sum of the squares of its digits. It repeatedly divides the number by 10 (extracting digits) and accumulates the squares of these digits.

* `check(unordered_map<int, bool> &m, int n)`: A recursive function that uses a hash map to track the numbers encountered during the process. If the number becomes 1, it returns true, indicating the number is "OverHappy." If a number repeats (found in the map), it indicates a cycle, returning false.

* `isHappy(int n)`: This is the main function that initializes the hash map and starts the recursive checking process.

* `main()`: The entry point of the program, where the user inputs a number, and the program outputs whether it is "OverHappy" or not.

## Time and Space Complexity Analysis
* Time Complexity: The time complexity is not straightforward due to the nature of the problem. However, it can be argued that for most practical inputs, the function will resolve in polynomial time since the sum of the squares of the digits decreases rapidly for large numbers.

* Space Complexity: The space complexity primarily depends on the hash map used to store intermediate numbers. In the worst case, this can grow to a size proportional to the number of unique sums generated by the number's digits, which is O(log n) in most cases.

## Key Points of the Algorithm

* Avoiding Infinite Loops: The use of a hash map to track previously seen numbers is crucial in preventing infinite loops for numbers that are not "OverHappy."

* Recursive Approach: The recursive implementation simplifies the process of continually updating a number until a conclusion is reached.

* Efficiency: The algorithm is efficient for numbers that quickly converge to 1. Its performance may vary for larger numbers or those leading to long cycles.

OverHappy Numbers

Move Zeroes

Q9. Ram is very good at mathematics. He was given a number n and was told to find out number of trailing zeroes in n! in logarithmic time. Can you help him?

## Intuition Behind the Algorithm

The problem presented to Ram involves finding the number of trailing zeroes in the factorial of a given number `n`. This task hinges on understanding that trailing zeroes are formed by the product of 2 and 5. However, in factorials, the number of 2s is always more than or equal to the number of 5s. Thus, the problem simplifies to counting the number of 5s in the factorial's prime factorization.

```cpp
#include <iostream>
using namespace std;

// Function to count the number of trailing zeros in n!
int factorial_trailing_zeros(int n) {
 int count_zeros = 0; // Initialize count of trailing zeros to 0

 // Loop to divide n by 5 and add the quotient to count_zeros
 while (n > 0) {
 n = n / 5; // Divide n by 5
 count_zeros += n; // Add the quotient to count_zeros
 }

 return count_zeros; // Return the count of trailing zeros
}

int main() {
 int n;
 cin >> n; // Input the number n

 int ans = factorial_trailing_zeros(n); // Compute the number of trailing zeros
 cout << ans << endl; // Output the result

 return 0;
}
```

## Code Walkthrough

The provided C++ code effectively addresses this problem. The function `factorial_trailing_zeros` takes an integer `n` and initializes `count_zeros` to zero. It then enters a while loop, which continues as long as `n` is greater than zero. Inside the loop, `n` is divided by 5, and this quotient is added to `count_zeros`. This division essentially counts how many times 5 is a factor in numbers from 1 to `n`. The loop iteratively divides `n` by 5 to account for additional factors of 5 in numbers like 25, 125, etc., where 5 appears more than once. Once the loop ends, count_zeros, representing the number of trailing zeroes in `n`!, is returned.

The `main` function reads an integer `n` and uses `factorial_trailing_zeros` to compute the answer, which is then outputted.

 ## Time and Space Complexity Analysis

The time complexity of the algorithm is O(log5(n)). This is because the loop divides n by 5 in each iteration, effectively reducing the problem size logarithmically. The space complexity is O(1), as the algorithm uses a fixed amount of space regardless of the input size.

## Key Points of the Algorithm

* Efficiency in Counting 5s: The algorithm smartly counts the number of times 5 is a factor in the factorial of n, which is the essence of finding trailing zeroes.

* Logarithmic Time Complexity: The approach ensures that the time complexity is logarithmic, making it efficient for large values of n.

* Simplicity and Elegance: The implementation is straightforward and easy to understand, yet powerful in its computation.

## Conclusion

The provided solution is optimal for the given problem. It elegantly solves the problem in logarithmic time, which is a significant improvement over naive methods that might attempt to compute the factorial directly.

Count Zeroes

Q10. Given an integer n, return an array containing n unique integers such that they add up to 0.

## Intuition Behind the Algorithm

The core idea of the "Target Zero" problem is to generate a set of unique integers that sum up to zero. The approach hinges on the mathematical principle that a number and its negative counterpart cancel each other out. The algorithm exploits this by pairing positive and negative integers. When `n` is odd, it includes zero to ensure uniqueness and satisfy the requirement.

```cpp
#include <iostream>
#include <vector>

using namespace std;

// Function to generate a vector of 'n' unique integers that sum up to 0
vector<int> targetzeros(int n) {
 vector<int> v; // Vector to store the result
 int n1 = n / 2.0; // Halving 'n', adjusting for decimal with division by 2.0

 // Loop to add both positive and negative integers to the vector
 for (int i = 1; i <= n1; i++) {
 v.push_back(i); // Add positive integer
 v.push_back(-i); // Add corresponding negative integer
 }

 // If 'n' is odd, add 0 to the vector to maintain the unique count
 if (n % 2 == 1) {
 v.push_back(0);
 }

 return v; // Return the final vector
}

int main() {
 int n;
 cin >> n; // Input for the number of integers
 vector<int> ans = targetzeros(n); // Generate the vector

 // Loop to print the elements of the vector
 for (int i = 0; i < n; i++) {
 cout << ans[i] << " ";
 }
}
```

## Code Walkthrough

* Function Declaration: `targetzeros(int n)` returns a vector of integers.

* Variable Initialization: `vector<int> v` stores the resultant integers. `n1` halves `n`, adjusting for the decimal with division by 2.0.

* Loop for Pairing: The loop runs from 1 to `n1`. For each `i`, the algorithm pushes `i` and `-i` into `v`, ensuring that each number and its negative are included.

* Handling Odd `n`: If `n` is odd (`n % 2 == 1`), the algorithm adds 0 to `v` to maintain the unique count and achieve the zero sum.

* Main Function: Takes input `n`, calls `targetzeros(n)`, and prints the result.


## Time and Space Complexity Analysis

* Time Complexity: O(n), as the loop runs roughly `n/2` times and each operation inside the loop is O(1).

* Space Complexity: O(n), due to the storage of `n` integers in the vector `v`.

## Key Points of the Algorithm

* Balancing Pairs: The algorithm effectively balances positive and negative integers.

* Handling Odd and Even: It smartly accommodates both odd and even values of `n` by adding 0 for odd cases.

* Simplicity and Effectiveness: The approach is straightforward yet efficient in meeting the problem's requirements.

## Conclusion

The "Target Zero" algorithm is a neat solution for generating an array of unique integers summing to zero. It's direct and efficient for the problem at hand.

* Optimization Scope: One might consider optimizing for specific scenarios or constraints if the problem scope changes.
* Alternative Approaches: Exploring different mathematical patterns or using data structures like sets could offer alternative solutions, though they may not necessarily be more efficient than the current approach.

In conclusion, this algorithm stands out for its simplicity and direct approach to solving the given problem.

Target Zero

Explore the secrets to cracking FAANG (Facebook, Amazon, Apple, Netflix, Google) interview questions. Unveil the strategies essential to tackle these coveted tech giants' challenging interview queries and land your dream job!

Move Zeroes

Intuition Behind the Algorithm

Code Walkthrough

Time and Space Complexity Analysis

Key Points of the Algorithm

Conclusion

Library

On this page