Transform Array to All Equal Elements - Practice Coding Problems

Transform Array to All Equal Elements - Problem

Array Greedy Medium

You are given an integer array nums of size n containing only 1 and -1, and an integer k.

You can perform the following operation at most k times:

Choose an index i (0 <= i < n - 1), and multiply both nums[i] and nums[i + 1] by -1.

Note: You can choose the same index i more than once in different operations.

Return true if it is possible to make all elements of the array equal after at most k operations, and false otherwise.

Input & Output

Example 1 — Basic Transformation

$ Input: nums = [1,-1,1], k = 1

› Output: true

💡 Note: Apply operation at index 0: multiply nums[0] and nums[1] by -1, getting [-1,1,1]. Then apply operation at index 1: multiply nums[1] and nums[2] by -1, getting [-1,-1,-1]. All elements are now equal.

Example 2 — Insufficient Operations

$ Input: nums = [1,1,-1,-1], k = 1

› Output: false

💡 Note: We have 2 positive and 2 negative elements. To make all equal, we need at least 1 operation to group negatives or positives, but the arrangement makes it impossible with just k=1 operations.

Example 3 — Already Equal

$ Input: nums = [-1,-1], k = 0

› Output: true

💡 Note: All elements are already equal to -1, so no operations needed.

Constraints

1 ≤ nums.length ≤ 10⁵
nums[i] is either 1 or -1
0 ≤ k ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,-1,1] with k=1 operations allowed

Operation

Flip adjacent pairs: multiply nums[i] and nums[i+1] by -1

Goal

Make all elements equal using ≤ k operations

Key Takeaway

🎯 Key Insight: Count elements and calculate minimum operations instead of simulating all possibilities

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that each operation flips exactly 2 adjacent elements, so we can analyze mathematically instead of simulating. Count positive and negative elements, calculate minimum operations needed to make all equal, and check if it's ≤ k. Best approach is Mathematical Analysis with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Analysis	O(n)	O(1)	Analyze the mathematical properties of the transformation to determine feasibility
Brute Force Simulation	O(n^k)	O(k)	Try all possible combinations of operations up to k times

Mathematical Analysis — Algorithm Steps

Count negative elements in array
Calculate minimum operations needed
Check if achievable within k operations
Consider parity constraints

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Elements

Count positive and negative elements

Calculate Minimum

Determine minimum operations needed

Check Feasibility

Compare with available operations k

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool solution(int* nums, int size, int k) {
    if (size == 1) return true;
    
    int negCount = 0;
    for (int i = 0; i < size; i++) {
        if (nums[i] == -1) negCount++;
    }
    
    if (negCount == 0 || negCount == size) {
        return true;
    }
    
    int posCount = size - negCount;
    
    int minOpsToAllPos = (negCount + 1) / 2;
    int minOpsToAllNeg = (posCount + 1) / 2;
    
    return minOpsToAllPos <= k || minOpsToAllNeg <= k;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nums[100];
    int size = 0;
    char* token = strtok(line, "[],\n ");
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, "[],\n ");
    }
    
    int k;
    scanf("%d", &k);
    
    printf(solution(nums, size, k) ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to count negatives and analyze the array

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

23.4K Views

Medium Frequency

~15 min Avg. Time

867 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Mathematical Analysis — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler