Coding Problems
with Java Solutions
Q1. Move Zeros to End (Chocolate Factory)
A chocolate factory packs chocolates into an array of N integers. Find all empty packets (0s) and push them to
the end of the array, maintaining the relative order of non-zero elements.
Example: N=8, arr=[4,5,0,1,9,0,5,0] → Output: 4 5 1 9 5 0 0 0
Java Solution:
import [Link];
public class Q1_MoveZeros {
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int n = [Link]();
int[] arr = new int[n];
for (int i = 0; i < n; i++) arr[i] = [Link]();
int pos = 0; // position to place next non-zero element
for (int i = 0; i < n; i++) {
if (arr[i] != 0) {
arr[pos++] = arr[i];
}
}
// Fill remaining with zeros
while (pos < n) arr[pos++] = 0;
for (int i = 0; i < n; i++) {
[Link](arr[i]);
if (i < n - 1) [Link](" ");
}
[Link]();
}
}
Time: O(n) | Space: O(1)
Q2. Count Sundays (Jack's Favourite Day)
Given the starting day of the month (e.g. 'mon', 'tue', ..., 'sun') and a number of days N, count how many Sundays
fall within those N days.
Example: Start='mon', N=13 → Output: 2
Java Solution:
import [Link];
import [Link];
public class Q2_CountSundays {
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
String startDay = [Link]().toLowerCase();
int n = [Link]();
Map<String, Integer> dayMap = [Link](
"sun", 0, "mon", 1, "tue", 2, "wed", 3,
"thu", 4, "fri", 5, "sat", 6
);
int start = [Link](startDay);
// Days until first Sunday
int daysToSunday = (7 - start) % 7;
int count = 0;
if (daysToSunday == 0) {
count = 1 + (n - 1) / 7;
} else if (daysToSunday < n) {
count = 1 + (n - daysToSunday - 1) / 7;
}
[Link](count);
}
}
Time: O(1) | Space: O(1)
Q3. Count Elements Greater Than All Prior
Given an integer array of size N, count elements whose value is greater than all previous elements. The first
element always counts.
Example: Arr={7,4,8,2,9} → Output: 3 (7, 8, 9)
Java Solution:
import [Link];
public class Q3_CountGreater {
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int n = [Link]();
int[] arr = new int[n];
for (int i = 0; i < n; i++) arr[i] = [Link]();
int count = 1; // first element always counted
int maxSoFar = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > maxSoFar) {
count++;
maxSoFar = arr[i];
}
}
[Link](count);
}
}
Time: O(n) | Space: O(1)
Q4. Maximum Aqua Curtains in a Box
Given a string of 'a' (aqua) and 'b' (black) curtains of length N and a box size L, divide the string into substrings of
length L (last box may be smaller). Find the maximum number of 'a's in any single box.
Example: str='bbbaaababa', L=3 → Boxes: 'bbb','aaa','bab','a' → Output: 3
Java Solution:
import [Link];
public class Q4_MaxAquaCurtains {
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
String str = [Link]();
int L = [Link]();
int n = [Link]();
int maxA = 0;
for (int i = 0; i < n; i += L) {
int end = [Link](i + L, n);
int count = 0;
for (int j = i; j < end; j++) {
if ([Link](j) == 'a') count++;
}
maxA = [Link](maxA, count);
}
[Link](maxA);
}
}
Time: O(n) | Space: O(1)
Q5. Sort by Risk Severity (Airport Security)
Given an array of N integers where each element is 0, 1, or 2 (risk levels), sort the array in ascending order of
risk. This is the Dutch National Flag problem.
Example: N=7, arr=[1,0,2,0,1,0,2] → Output: 0 0 0 1 1 2 2
Java Solution:
import [Link];
public class Q5_SortRiskSeverity {
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int n = [Link]();
int[] arr = new int[n];
for (int i = 0; i < n; i++) arr[i] = [Link]();
// Dutch National Flag Algorithm
int low = 0, mid = 0, high = n - 1;
while (mid <= high) {
if (arr[mid] == 0) {
int tmp = arr[low]; arr[low] = arr[mid]; arr[mid] = tmp;
low++; mid++;
} else if (arr[mid] == 1) {
mid++;
} else {
int tmp = arr[mid]; arr[mid] = arr[high]; arr[high] = tmp;
high--;
}
}
for (int i = 0; i < n; i++) {
[Link](arr[i]);
if (i < n - 1) [Link](" ");
}
[Link]();
}
}
Time: O(n) | Space: O(1)
Q6. Find Odd Occurring Element in O(log n)
Given a sorted array where every element appears an even number of times except one, find the odd occurring
element in O(log n). Equal elements appear in pairs, with at most two consecutive occurrences.
Example: arr=[1,1,2,2,3,3,4,5,5] → Output: 4
Java Solution:
import [Link];
public class Q6_OddOccurring {
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int n = [Link]();
int[] arr = new int[n];
for (int i = 0; i < n; i++) arr[i] = [Link]();
int lo = 0, hi = n - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
// Ensure mid is even index
if (mid % 2 == 1) mid--;
// If pair is intact, single element is to the right
if (arr[mid] == arr[mid + 1]) {
lo = mid + 2;
} else {
hi = mid;
}
}
[Link](arr[lo]);
}
}
Time: O(log n) | Space: O(1)
Q7. Total Handshakes in a Meeting (COVID Story)
Given T test cases, each with N people in a meeting where every pair shakes hands exactly once, compute the
total number of handshakes. Answer = N*(N-1)/2.
Example: N=4 → 4*3/2 = 6 handshakes
Java Solution:
import [Link];
public class Q7_Handshakes {
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int t = [Link]();
while (t-- > 0) {
long n = [Link]();
[Link](n * (n - 1) / 2);
}
}
}
Time: O(T) | Space: O(1)
Q8. Toggle All Bits After MSB (Joseph's Problem)
Given a positive integer N (1 <= N <= 100), convert it to binary, toggle all bits (from MSB to LSB), and print the
resulting positive integer.
Example: N=10 → binary=1010 → toggled=0101=5 → Output: 5
Java Solution:
import [Link];
public class Q8_ToggleBits {
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int n = [Link]();
// Create a mask of all 1s with same bit-length as n
int bits = (int)([Link](n) / [Link](2)) + 1;
int mask = (1 << bits) - 1;
[Link](n ^ mask);
}
}
Time: O(log n) | Space: O(1)
Q9. Product of Digits (Supermarket Pricing)
Given an integer N printed on a product, compute the price by multiplying all its digits.
Example: N=5244 → 5*2*4*4 = 160 → Output: 160
Java Solution:
import [Link];
public class Q9_ProductOfDigits {
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
String n = [Link]();
long product = 1;
for (char c : [Link]()) {
product *= (c - '0');
}
[Link](product);
}
}
Time: O(d) where d = number of digits | Space: O(1)
Q10. Circular Permutation with Constraint (Round Table)
N members sit around a circular table. The President and Prime Minister of India must always sit next to each
other. Find the number of ways P to seat all N members.
Formula: Treat the 2 fixed members as one unit → (N-1)! circular arrangements * 2! internal arrangements = 2*(N-1)!
Example: N=4 → 2 * 3! = 2 * 6 = 12 → Output: 12
Java Solution:
import [Link];
public class Q10_RoundTable {
static final long MOD = 1_000_000_007;
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int n = [Link]();
if (n < 2) { [Link](0); return; }
// 2 * (n-1)!
long result = 2;
for (int i = 2; i <= n - 1; i++) {
result = (result * i) % MOD;
}
[Link](result);
}
}
Time: O(n) | Space: O(1)
Q11. Odd-Even Traffic Fine (Delhi Pollution)
On date D (positive integer), only vehicles with even last-digit (if D is even) or odd last-digit (if D is odd) are
allowed. Others are fined X rupees each. Given N vehicles' last digits, calculate the total fine collected.
Example: N=4, arr={5,2,3,7}, D=12, X=200 → Fined: 5,3,7 → Output: 600
Java Solution:
import [Link];
public class Q11_TrafficFine {
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int n = [Link]();
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = [Link]();
int D = [Link]();
long X = [Link]();
long fine = 0;
boolean evenDate = (D % 2 == 0);
for (int i = 0; i < n; i++) {
boolean evenReg = (a[i] % 2 == 0);
// Violator: odd reg on even date OR even reg on odd date
if (evenDate && !evenReg) fine += X;
else if (!evenDate && evenReg) fine += X;
}
[Link](fine);
}
}
Time: O(n) | Space: O(1)
Q12. Count Subsets with Given Sum
Given T test cases, each with an array of N positive integers and a target sum, count all subsets whose elements
sum equals the target. Print result modulo 10^9+7.
Constraints: 1<=T<=100, 1<=n<=1000, 1<=a[i]<=1000, 1<=sum<=1000
Java Solution:
import [Link];
public class Q12_SubsetSum {
static final int MOD = 1_000_000_007;
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int t = [Link]();
while (t-- > 0) {
int n = [Link]();
int[] arr = new int[n];
for (int i = 0; i < n; i++) arr[i] = [Link]();
int target = [Link]();
// dp[j] = number of subsets with sum j
long[] dp = new long[target + 1];
dp[0] = 1;
for (int x : arr) {
for (int j = target; j >= x; j--) {
dp[j] = (dp[j] + dp[j - x]) % MOD;
}
}
[Link](dp[target]);
}
}
}
Time: O(T*n*sum) | Space: O(sum)
Q13. Book Exchange Derangement (Children's Day)
N students exchange books so that no student gets their own book. Find the number of such possible
permutations (derangements) modulo 10^8+7.
Formula: D(n) = (n-1) * (D(n-1) + D(n-2)), D(1)=0, D(2)=1
Example: N=4 → D(4)=9 → Output: 9
Java Solution:
import [Link];
public class Q13_Derangement {
static final long MOD = 100_000_007;
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int n = [Link]();
if (n == 1) { [Link](0); return; }
if (n == 2) { [Link](1); return; }
long prev2 = 0; // D(1)
long prev1 = 1; // D(2)
long curr = 0;
for (int i = 3; i <= n; i++) {
curr = ((long)(i - 1) * ((prev1 + prev2) % MOD)) % MOD;
prev2 = prev1;
prev1 = curr;
}
[Link](curr);
}
}
Time: O(n) | Space: O(1)
Q14. Max Path Sum Not Divisible by K (Binary Tree)
Given a binary tree with N nodes, find the maximum sum of a root-to-leaf path such that the sum is NOT divisible
by K. Print -1 if no valid path exists.
Input: N nodes, node values, N-1 edges (tree rooted at node 1), and integer K. Example: N=7, values=[3,4,8,2,1,6,10], K=5 →
Output: 21 (path 3->8->10)
Java Solution:
import [Link].*;
public class Q14_MaxPathSumTree {
static List<Integer>[] adj;
static int[] val;
static int K;
static int ans = -1;
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int n = [Link]();
val = new int[n + 1];
adj = new ArrayList[n + 1];
for (int i = 1; i <= n; i++) {
val[i] = [Link]();
adj[i] = new ArrayList<>();
}
for (int i = 0; i < n - 1; i++) {
int u = [Link](), v = [Link]();
adj[u].add(v);
adj[v].add(u);
}
K = [Link]();
dfs(1, 0, 0);
[Link](ans);
}
static void dfs(int node, int parent, int currentSum) {
currentSum += val[node];
boolean isLeaf = true;
for (int child : adj[node]) {
if (child != parent) {
isLeaf = false;
dfs(child, node, currentSum);
}
}
if (isLeaf && currentSum % K != 0) {
ans = [Link](ans, currentSum);
}
}
}
Time: O(N) | Space: O(N)
All solutions are optimized for the given constraints. Edge cases (empty arrays, n=1, no valid path) are handled in each
solution.