Generate an Array such that the sum of any Subarray is not divisible by its Length
Given an integer N. Then the task is to output an array let’s say A[] of length N such that:
- The sum S, of any subarray, let’s say A[L, R] where (L != R) must not leave the remainder as 0 when dividing by the length of A[L, R]. Formally, Sum(A[L, R])%(length of A[L, R]) != 0.
- A[] must contain all unique elements.
Note: Subarrays must be chosen at least of length equal to 2.
Examples:
Input: N = 3
Output: A[] = {7, 2, 5}
Explanation: There can be three possible subarrays of length at least equal to 2:
- A[1, 2]: The length and sum of subarray is 2 and (7+2) = 9 respectively. We can see that (9%2) != 0
- A[2, 3]: The length and sum of subarray is 2 and (2+5) = 7 respectively. We can see that (7%2) != 0
- A[1, 3]: The length and sum of subarray is 3 and (7+2+5) = 14 respectively. We can see that (14%3) != 0
There is no subarray such that its sum is perfectly divisible by its length. A[] also contains N distinct elements. Therefore, output array A[] is valid.
Input: N = 2
Output: A[] = {2, 1}
Explanation: It can be verified that both conditions are followed by the output array A[].
Approach: Implement the idea below to solve the problem
The problem is observation based and can be solved using those observations. Let us see some observations:
- When N is an even number, we can output a permutation.
- When n is an odd number, we can replace N with N + 1 and again we get another array consisting of N distinct integers.
- Examples:
- N = 7, A[] = {2, 1, 4, 3, 6, 5, 8}
- N = 8, A[] = {2, 1, 4, 3, 6, 5, 8, 7}
General formula:
- N is Odd: A[] = {2, 1, 3, 4, … N-1, N-2, N+1}
- N is Even: A[] = {2, 1, 3, 4, … N, N-1}
Steps were taken to solve the problem:
- If (N is Odd)
- Output {2, 1, 3, 4, … N-1, N-2, N+1} using loop.
- If (N is Even)
- Output {2, 1, 3, 4, … N, N-1} using loop.
Code to implement the approach:
C++
#include <iostream> void GFG( int N) { // Check if N is odd or even if (N % 2 == 1) { // Print elements for the odd N for ( int i = 1; i < N; i += 2) std::cout << i + 1 << " " << i << " " ; std::cout << N + 1 << std::endl; } else { // Print elements for even N for ( int i = 1; i <= N; i += 2) std::cout << i + 1 << " " << i << " " ; } } int main() { // Input int N = 8; // Function call GFG(N); return 0; } |
Java
// Java code to implement the approach // Driver Class public class Main { // Driver Function public static void main(String[] args) { // Input int N = 8 ; // Function call Print_array(N); } // Method to print A[] public static void Print_array( int N) { if (N % 2 == 1 ) { for ( int i = 1 ; i < N; i += 2 ) System.out.print(i + 1 + " " + i + " "); System.out.println(N + 1 ); } else { for ( int i = 1 ; i <= N; i += 2 ) System.out.print(i + 1 + " " + i + " "); } } } |
Python3
# Python code to implement the approach # Method to print A[] def Print_array(N): if N % 2 = = 1 : for i in range ( 1 , N, 2 ): print (i + 1 , i, end = " " ) print (N + 1 ) else : for i in range ( 1 , N + 1 , 2 ): print (i + 1 , i, end = " " ) # Driver function def main(): # Input N = 8 # Function call Print_array(N) if __name__ = = '__main__' : main() # This code is contributed by ragul21 |
C#
using System; class GFG { static void Main( string [] args) { // Input int N = 8; // Function call PrintArray(N); } // Method to print elements based on N static void PrintArray( int N) { // Check if N is odd or even if (N % 2 == 1) { // Print elements for the odd N for ( int i = 1; i < N; i += 2) Console.Write(i + 1 + " " + i + " " ); Console.WriteLine(N + 1); } else { // Print elements for even N for ( int i = 1; i <= N; i += 2) Console.Write(i + 1 + " " + i + " " ); } } } |
Javascript
function GFG(N) { // Check if N is odd or even if (N % 2 === 1) { // Print elements for the odd N for (let i = 1; i < N; i += 2) console.log(i + 1, i); console.log(N + 1); } else { // Print elements for even N for (let i = 1; i <= N; i += 2) console.log(i + 1, i); } } // Input let N = 8; // Function call GFG(N); |
2 1 4 3 6 5 8 7
Time Complexity: O(N)
Auxiliary Space: O(1)